40

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.]

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Jeffε
  • 23,129
  • 10
  • 96
  • 163
  • 5
    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? – Tsuyoshi Ito Aug 31 '10 at 00:28
  • Yes. Any scrambled cube can be solved in O(n^2) turns, using any number of algorithms. – Jeffε Aug 31 '10 at 15:27
  • 1
    Thanks for the information. Is there any reference? – Tsuyoshi Ito Aug 31 '10 at 16:01
  • 1
    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. – Aaron Sterling Sep 02 '10 at 12:19
  • @Aaron Sterling: Which algorithm are you referring to by “Rubik’s solution algorithm”? Your claim is correct if you are referring to the recent result by Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge, but I would hesitate to call their computation “Rubik’s solution algorithm” for several reasons. – Tsuyoshi Ito Sep 02 '10 at 14:58
  • As a general comment about this question, note that there are several ways to define the number of moves (or, more precisely, what counts as a single move) even for the 3×3×3 cube. – Tsuyoshi Ito Sep 02 '10 at 15:03
  • Yes, that's what I was referring to. – Aaron Sterling Sep 02 '10 at 16:19
  • @Tsuyoshi Ito: Yes, there are several definitions of "number of moves". I'd be happy with a poly-time algorithm or NP-hardness proof for ANY reasonable definition. – Jeffε Sep 03 '10 at 03:35
  • @Tsuyoshi Ito: Any published algorithm for the 5x5x5 cube generalizes immediately to larger cubes. All published cube-solving algorithms work in stages, where each stage uses O(1) turns to place O(1) cubelets in the right position and orientation. – Jeffε Sep 03 '10 at 03:37
  • 1
    Do we know that the diameter of the reachable configuration space is $\Theta(n^2)$? – Andy Drucker Sep 09 '10 at 01:39
  • 1
    @Andy: Nice question! ("What is God's function of n?") – Jeffε Sep 10 '10 at 00:20
  • The fact that determining the worst-case number of moves needed (a.k.a. God's number = 20 for 3x3x3 cube) was not solved without computer assistance gives weak circumstantial evidence against polynomial-time solvability. – Warren Schudy Oct 04 '10 at 03:16

3 Answers3

21

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?

Andy Drucker
  • 4,634
  • 23
  • 33
  • 1
    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.) – Andy Drucker Jun 29 '11 at 01:46
  • 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.) – Andy Drucker Jun 29 '11 at 19:05
17

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

Mikhail Rudoy
  • 2,768
  • 13
  • 24
9

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).

Joe Fitzsimons
  • 13,675
  • 47
  • 91
  • 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? – Peter Shor Oct 22 '10 at 19:22
  • @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) – Joe Fitzsimons Oct 22 '10 at 20:09
  • (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$. – Joe Fitzsimons Oct 22 '10 at 20:13
  • 2
    @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). – Peter Shor Oct 22 '10 at 21:00
  • @Peter: Ah, I see your point. Sorry for being a bit slow on the uptake. This would of course then mean that there is a problem with this approach for local maxima in path length, so there is certainly more to be proved. If there are no local maxima then this approach should work, but their presence would mean that something more is required. Sorry, I couldn't help posting a half thought out answer given that this question had gone unanswered for so long. – Joe Fitzsimons Oct 22 '10 at 21:43
  • @Peter: It occurs to me that the approach as is must fail in general, since in the case of the the $3 \times 3 \times 3$ cube there is more than one configuration which takes the maximum number of moves (20) to solve. Thus a single $B_{hard}$ doesn't suffice. – Joe Fitzsimons Oct 22 '10 at 22:15
  • 2
    @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. – Peter Shor Oct 23 '10 at 01:29
  • @Peter: Yes, it should work for approximation. It also seems like it may also work for average-case complexity. – Joe Fitzsimons Oct 23 '10 at 15:23
  • I'm confused. You seem to be arguing that (the decision version) of my problem is in NP, not that it isn't NP-hard. But membership in NP is obvious: To prove that there is a sequence of at most $s$ moves that solves a given scrambled cube, just show me the sequence. Analogous questions about other reconfiguration puzzles, like the generalized 15-puzzle, are NP-hard; why doesn't your argument apply to them? What am I missing here? – Jeffε Oct 23 '10 at 17:37
  • @JeffE: Certainly the problem "Can you solve the cube starting from configuration A in less than S steps?" is in NP, as you point out. What I was trying to show was that it was likely that a different (related) question "Is S the minimum number of moves to solve the cube from configuration A?" was also likely in NP. As Peter has pointed out above, this argument would only work under certain assumptions, which may not actually be true for the cube either. – Joe Fitzsimons Oct 23 '10 at 22:03