<p>A new <a href="http://arxiv.org/abs/1106.5736">paper</a> 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)$.</p>

<p>Sweet!</p>

<p>One possible next question that their work seems to suggest: is there a <em>fixed</em> 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?</p>

CC BY-SA 3.0
2011-06-29T01:46:30.380Z
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
CC BY-SA 3.0
2011-06-29T19:05:42.303Z
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
CC BY-SA 3.0
2011-06-29T01:12:49.557Z
2011-06-29T16:01:48.653Z
2011-06-29T16:01:48.653Z
Andy Drucker
<p>There could easily be a bug in this, so please let me know if you spot one.</p>

<p>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?"</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

<p>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)$. </p>

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

CC BY-SA 2.5
2010-10-22T19:22:02.733Z
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 
CC BY-SA 2.5
2010-10-22T20:09:15.960Z
@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
CC BY-SA 2.5
2010-10-22T20:13:44.317Z
(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
CC BY-SA 2.5
2010-10-22T21:00:48.953Z
@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 
CC BY-SA 2.5
2010-10-22T21:43:22.403Z
@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
CC BY-SA 2.5
2010-10-22T22:15:20.123Z
@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
CC BY-SA 2.5
2010-10-23T01:29:46.627Z
@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 
CC BY-SA 2.5
2010-10-23T15:23:00.393Z
@Peter: Yes, it should work for approximation. It also seems like it may also work for average-case complexity.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-23T17:37:12.480Z
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ε
CC BY-SA 2.5
2010-10-23T22:03:03.737Z
@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
CC BY-SA 2.5
2010-10-22T16:17:42.980Z
2010-10-22T18:20:31.487Z
2010-10-22T18:20:31.487Z
Joe Fitzsimons
<p><a href="https://arxiv.org/abs/1706.06708" rel="noreferrer">One of my papers</a> was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.</p>

CC BY-SA 3.0
2017-06-22T13:37:07.510Z
Congratulations!!
Jeffε
CC BY-SA 3.0
2017-06-22T04:35:34.140Z
2017-06-22T04:35:34.140Z
Mikhail Rudoy
<p>Consider the obvious $n\times n\times n$ generalization of the <a href="http://en.wikipedia.org/wiki/Rubik%27s_Cube">Rubik's Cube</a>.  Is it NP-hard to compute the <em>shortest</em> sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?</p>

<p>[Some related results are described in <a href="http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-cube.html">my recent blog post</a>.] </p>

CC BY-SA 2.5
2010-08-31T00:28:53.457Z
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
CC BY-SA 2.5
2010-08-31T15:27:59.063Z
Yes.  Any scrambled cube can be solved in O(n^2) turns, using any number of algorithms.
Jeffε
CC BY-SA 2.5
2010-08-31T16:01:03.080Z
Thanks for the information.  Is there any reference?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T12:19:17.767Z
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
CC BY-SA 2.5
2010-09-02T14:58:54.430Z
@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
CC BY-SA 2.5
2010-09-02T15:03:19.903Z
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
CC BY-SA 2.5
2010-09-02T16:19:53.100Z
Yes, that's what I was referring to.
Aaron Sterling
CC BY-SA 2.5
2010-09-03T03:35:33.057Z
@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ε
CC BY-SA 2.5
2010-09-03T03:37:22.123Z
@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ε
CC BY-SA 2.5
2010-09-09T01:39:10.510Z
Do we know that the diameter of the reachable configuration space is $\Theta(n^2)$?
Andy Drucker
CC BY-SA 2.5
2010-09-10T00:20:42.447Z
@Andy: Nice question!  ("What is God's function of n?")
Jeffε
CC BY-SA 2.5
2010-10-04T03:16:14.723Z
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
<cc.complexity-theory><co.combinatorics><np-hardness><open-problem><puzzles>
Is optimally solving the n×n×n Rubik's Cube NP-hard?
Jeffε
# Is optimally solving the n×n×n Rubik's Cube NP-hard?

(Asked by: username_0 on 2010-08-31)

Consider the obvious $n\times n\times n$ generalization of the [Rubik's Cube](http://en.wikipedia.org/wiki/Rubik%27s_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](http://3dpancakes.typepad.com/ernie/2010/06/complexity-of-rubiks-cube.html).]

**Tags:** cc.complexity-theory, co.combinatorics, np-hardness, open-problem, puzzles

> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes.  Any scrambled cube can be solved in O(n^2) turns, using any number of algorithms.  
> **username_1**: Thanks for the information.  Is there any reference?  
> **username_2**: 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.  
> **username_1**: @username_2: 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.  
> **username_1**: 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.  
> **username_2**: Yes, that's what I was referring to.  
> **username_0**: @username_1: 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.  
> **username_0**: @username_1: 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.  
> **username_3**: Do we know that the diameter of the reachable configuration space is $\Theta(n^2)$?  
> **username_0**: @Andy: Nice question!  ("What is God's function of n?")  
> **username_4**: 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.  

---

## 3 answers

### Answer by username_7 on 2017-06-22. Score: 19 | Accepted answer

[One of my papers](https://arxiv.org/abs/1706.06708) was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.

> **Comments:**
> **username_0**: Congratulations!!  

---

### Answer by username_3 on 2011-06-29. Score: 22

A new [paper](http://arxiv.org/abs/1106.5736) 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?

> **Comments:**
> **username_3**: 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.)  
> **username_3**: 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.)  

---

### Answer by username_5 on 2010-10-22. Score: 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).

> **Comments:**
> **username_6**: 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?  
> **username_5**: @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)  
> **username_5**: (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$.  
> **username_6**: @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).  
> **username_5**: @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.  
> **username_5**: @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.  
> **username_6**: @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.  
> **username_5**: @Peter: Yes, it should work for approximation. It also seems like it may also work for average-case complexity.  
> **username_0**: 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?  
> **username_5**: @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.  

---

