Fetching the paper…

Reading the bibliography…

2017

Solving the Rubik's Cube Optimally is NP-complete

Demaine, Erik D., Eisenstat, Sarah, Rudoy, Mikhail

Original
PDF
Post on X

Understand

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.

Solving the Rubik's Cube Optimally is NP-complete · Around

Built on

Hamilton paths in grid graphs
Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter · 1982
Earlier work this paper cites.
Can computers routinely discover mathematical proofs?
Stephen A. Cook · 1984
Earlier work this paper cites.
The ( n 2 − 1 ) (n^{2}-1) -puzzle and related relocation problems
Daniel Ratner and Manfred Warmuth · 1990
Earlier work this paper cites.

Similar

A survey of NP-complete puzzles
Graham Kendall, Andrew J. Parkes, and Kristian Spoerer · 2008
Cited alongside, same era.
Move count metrics for big cubes - standards and preferences
Cride5 · 2010
Cited alongside, same era.

Then

Is optimally solving the n × \times n × \times n Rubik’s Cube NP-hard?
Jeff Erickson · 2010
Later among the works it cites.
Algorithms for solving Rubik’s Cubes
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow · 2011
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…