solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看128次
Solving the Rubik's Cube Optimally is NP-complete. (arXiv:1706.06708v1 [cs.CC])
来源于:arXiv
In this paper, we prove that optimally solving an $n \times n \times n$
Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in
square grid graphs. This improves the previous result that optimally solving an
$n \times n \times n$ Rubik's Cube with missing stickers is NP-complete. We
prove this result first for the simpler case of the Rubik's Square---an $n
\times n \times 1$ generalization of the Rubik's Cube---and then proceed with a
similar but more complicated proof for the Rubik's Cube case. 查看全文>>