40
$\begingroup$

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?

[Some related results are described in my recent blog post.]

Improve this question
$\endgroup$
12
  • 5
    $\begingroup$ I guess that the input is given as six n×n grids made of {1, …, 6}. Is the problem in NP? Is there an easy polynomial upper bound on the number of moves in the n×n×n version of Rubik’s cube? $\endgroup$
    – Tsuyoshi Ito
    Aug 31, 2010 at 0:28
  • 1
    $\begingroup$ Thanks for the information. Is there any reference? $\endgroup$
    – Tsuyoshi Ito
    Aug 31, 2010 at 16:01
  • 1
    $\begingroup$ Does the problem get any easier if it's relaxed to "Given a configuration, produce a solution that takes at most God's Number(n,n,n) of moves"? That's what the Rubik's solution algorithm did. They didn't look for shortest because it would have taken too long. $\endgroup$
    – Aaron Sterling
    Sep 2, 2010 at 12:19
  • 1
    $\begingroup$ Do we know that the diameter of the reachable configuration space is $\Theta(n^2)$? $\endgroup$
    – Andy Drucker
    Sep 9, 2010 at 1:39
  • 1
    $\begingroup$ @Andy: Nice question! ("What is God's function of n?") $\endgroup$
    – Jeffε
    Sep 10, 2010 at 0:20

3 Answers 3

Reset to default
17
$\begingroup$

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Congratulations!! $\endgroup$
    – Jeffε
    Jun 22, 2017 at 13:37
21
$\begingroup$

A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, and shows $\mathsf{NP}$-hardness for optimally solving what you might call "partially-colored" cubes. It also shows that the $n \times n \times n$ cube's configuration space has diameter $\Theta(n^2/\log n)$.

Sweet!

One possible next question that their work seems to suggest: is there a fixed family of partially-colored $n \times n \times n$ cubes, one for each value of $n$, such that optimally solving from a given configuration is $\mathsf{NP}$-hard?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ OK, and one more question: what's the complexity of determining whether two nonstandard colorings of the $n \times n \times n$ cube are equivalent? (Two cases to consider: complete or partial colorings.) $\endgroup$
    – Andy Drucker
    Jun 29, 2011 at 1:46
  • $\begingroup$ Alright, one more question and then I'll stop: is there an explicit sequence of configurations that require $\Omega(n^2/\log n)$ moves to solve? (The paper uses a counting argument for its lower bound.) $\endgroup$
    – Andy Drucker
    Jun 29, 2011 at 19:05
9
$\begingroup$

There could easily be a bug in this, so please let me know if you spot one.

It seems that the answer is no, or at least that this problem is contained within NP. The reasoning behind this is very simple. The idea is to build up from another question: "Can you get between configuration A and configuration B in S steps or less?"

Clearly this new question is in NP, because there is an $O(n^2)$ algorithm to solve the cube from any solvable configuration, and so going via the solved state it takes only $O(n^2)$ to go between any two configurations. Since there is only a polynomial number of moves, the set of moves to go between two configurations can be used as a witness for this new question.

Now, firstly, if we pick configuration B to be the solved state, we have a problem which asks whether it is possible to solve the cube in $S$ steps or less, which is contained within NP.

Now lets pick a different configuration for B, which I'll call $B_{hard}$ which takes $n_{hard} \approx n^2$ steps to solve. Now if we ask whether it is possible to get between configuration A and $B_{hard}$ in $S'$ steps or less, we again have a problem in NP with a sequence of moves as the witness. However, since we know $B_{hard}$ takes $n_{hard}$ steps to solve, we know that if it is possible to go between A and $B_{hard}$ in $S'$ steps, then it requires at least $n_{hard} - S'$ steps to solve the $n \times n \times n$ cube from configuration A.

Thus we have witnesses for both an lower bound of $n_{hard} - S'$ steps and a lower bound of $S$ steps to solve from configuration A. If we now pick $S_0$ as the minimum number of moves required to solve the cube starting with configuration A, then if we pick the lower and upper bounds to be equal (i.e. $S' = n_{hard} - S_0$ and $S = S_0$), then we have a witness that this solution is optimal (comprised of the witnesses of the two NP problems associated with the bounds).

Lastly, we need a way to generate $B_{hard}$. We probably need the hardest possible configuration, but since I don't know how to find that, I suggest simply rotating every second plane one time about the x-axis, and then every fourth plane (keeping the central plane fixed) one time about the z-axis. I believe this leads to a state which requires $O(n^2)$ steps to solve.

Thus, I don't have a full constructive proof, but any optimal solution taking less than $n_{hard}$ clearly has a witness. Unfortunately, of course, to capture all possible configurations you would need $n_{hard} = \mbox{God's number}(n)$.

EDIT: The regularity of the Superflip configuration makes it seem likely that generating $B_{hard}$ for $n_{hard} = \mbox{God's number}(n)$ might be relatively easy (i.e. in P).

Improve this answer
$\endgroup$
10
  • $\begingroup$ Neat idea. However, doesn't this assume that the shortest path between two points that are far apart can be taken to go through any other point. That's clearly true for points on spheres (if you're flying from the North pole to the South pole, you might as well fly by way of Tahiti), but is there any reason it should be true for configurations of Rubik's cubes? $\endgroup$
    – Peter Shor
    Oct 22, 2010 at 19:22
  • $\begingroup$ @Peter Shor: Hi Peter, I didn't mean to imply that going through $B_{hard}$ from A to the solution was the shortest path. In fact this approach shouldn't work in that case. The idea is that if it takes at least $n_{hard}$ steps to get from $B_{hard}$ to the solved configuration, then if we go from $A$ to the solution via $B_{hard}$ we have to go further away from the solved configuration, before going back. (contd) $\endgroup$
    – Joe Fitzsimons
    Oct 22, 2010 at 20:09
  • $\begingroup$ (contd.) I assume A is easier to solve than $B_{hard}$ (less steps). Since we know that it takes at least $n_{hard}$ steps to solve from $B_{hard}$, and we know we can get to $B_{hard}$ in at most $n_{hard}$ steps from A, then we have $n_{hard}-S' \leq S_0 \leq n_{hard} + S'$. I was using this to get an lower bound on $S_0$, while solving directly gives an upper bound on $S_0$. $\endgroup$
    – Joe Fitzsimons
    Oct 22, 2010 at 20:13
  • 2
    $\begingroup$ @Joe: You misunderstood me. I think your approach only works well if there is a relatively short path from B$_\mathrm{hard}$ to the solution which passes through A. I don't know whether this is true for the Rubik's cube (so I'm not saying your approach doesn't work, just that there's more stuff that needs to be proved). $\endgroup$
    – Peter Shor
    Oct 22, 2010 at 21:00
  • 2
    $\begingroup$ @Joe: don't worry about posting half-thought-out answers. I've done the same thing (and I'm not the only one). And I'm not convinced this approach is completely worthless. I do expect it won't work to show computing the exact distance is not NP-hard, but maybe it could say something about approximating it. $\endgroup$
    – Peter Shor
    Oct 23, 2010 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.