<p>Here's an extremely heuristic argument that suggests where local maxima may be found.  Let $N_d$ be the number of positions that require exactly $d$ moves to solve.  Each move from such a position takes the cube to distance $d-1$, $d$, or $d+1$; so there are a total of $N_{d-1} + N_d + N_{d+1}$ positions that are accessible.  There are $M$ moves from each position, leading to $M$ new positions; a position at distance $d$ is a local maximum when none of these $M$ positions are at distance $d+1$.  If we take these positions to be drawn uniformly at random from the accessible positions (which, of course, they aren't; this is the heuristic part), we have:</p>

<p>$$
\begin{eqnarray}
X_d &amp;=&amp; P\left[\text{ a given position at }d\text{ is a local max }\right] \\
&amp;=&amp; \left(\frac{N_{d-1} + N_d}{N_{d-1} + N_d + N_{d+1}}\right)^M \\
&amp;=&amp; \left(1 + \frac{N_{d+1}}{N_{d-1} + N_d}\right)^{-M}.
\end{eqnarray}
$$</p>

<p>The expected number of local maxima at distance $d$ is $N_d X_d$.</p>

<p>For the $3 \times 3 \times 3$ cube, the number of moves from a given position is $M=18$, and estimates for $N_d$ are provided at <a href="http://www.cube20.org" rel="nofollow">God's Number is 20</a>.  Using these values, we find the expected number of local maxima to be $N_{16} X_{16} = 0.2$, $N_{17} X_{17} = 9 \times 10^9$, and $N_{18} X_{18} = 1.5 \times 10^{19}$.  So there are unlikely to be any local maxima for $d \le 16$.  At $d=17$, the total number of positions is estimated to be $12 \times 10^{18}$, so one might expect to test a billion positions before finding a local maximum.  Finally, at $d=18$, one expects a local maximum in every twenty positions.</p>

CC BY-SA 2.5
2011-01-16T08:29:03.510Z
Thanks. It is however not clear to me that $N_{d-1}+N_{d}+N_{d+1}$ is the correct number of states accessible from the $N_d$ states of distance $d$. If for example there are local maxima of distance $d-1$ this would seem not to hold. It also seems to break for any state of distance $d$ for which all neighbouring states have distance $d-1$ or $d+1$, since this state cannot be reached in 1 move from any of the states of distance $d$. I have no idea how common or rare these situations will be.
Joe Fitzsimons
CC BY-SA 2.5
2011-01-13T16:50:26.660Z
2011-01-13T16:50:26.660Z
mjqxxxx
<p>Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):</p>

<blockquote>
  <p>If a position exhibits total
  symmetry, it is of necessity a local
  maximum (all except the start).  A
  little thought should make it clear
  why this is the case in the QTM [quarter-turn metric].  For
  the HTM [half-turn metric] it's a bit more subtle but not
  too bad.</p>
  
  <p>...</p>
  
  <p>Such a position is pons asinorum,
  which is distance 12 in QTM and
  distance 6 in HTM (U2D2F2B2L2R2).</p>
</blockquote>

<p>I don't see why this is the case for the half-turn metric; but for
the quarter-turn metric it is clear.  In a position with total symmetry, all neighboring positions must be at the same path length (since all moves are equivalent by symmetry).  So a position with total symmetry must be either a local maximum or a strict local minimum.  But strict local minima cannot exist... there has to be <em>some</em> move that reduces the distance to the solved state, just by the definition of the distance.  The symmetry argument translates to the $n \times n \times n$ cube, as does the example position provided.</p>

CC BY-SA 2.5
2011-01-17T04:49:25.887Z
What a simple argument, this is brilliant!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-18T10:01:07.353Z
Excellent, that's a very nice argument!
Joe Fitzsimons
CC BY-SA 2.5
2011-01-17T04:41:53.903Z
2011-01-17T04:41:53.903Z
mjqxxxx
<p>Peter Shor brought up an interesting point in relation to an attempt to answer an earlier <a href="https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard">question</a> on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take $S_A$ moves to solve the cube from configuration $A$, and either $S_A$ or $S_A - 1$ moves to solve the cube from any position which can be reached in one move from $A$. Now, this isn't necessarily such a problem if $S_A$ is maximum number of moves required to solve the cube in general (<a href="http://www.cube20.org/" rel="nofollow noreferrer">God's Number</a> for that cube), but is definitely a problem if $S_A$ is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the $3 \times 3 \times 3$ cube would be of interest to me.</p>

CC BY-SA 2.5
2011-01-13T18:24:02.520Z
I know Cayley graphs for arbitrary groups can have local maxima. I forget where I saw this result, but I am certain I did see it somewhere. So unless the Rubik's cube group is somehow special, one expects it has local maxima as well.
Peter Shor 
CC BY-SA 2.5
2010-10-22T22:31:53.797Z
Although I do not have an example, I would be surprised if there aren’t, because that seems to imply that we can compute God’s number by just finding one configuration which is a local maximum (this is not a rigorous argument, though).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-22T22:35:31.927Z
@Tsuyoshi Ah, but it may not have been known whether or not there were local maxima until after God's Number was computed! But I agree in that I expect these local maxima do exist. I just don't know for sure, and would be interested to find out.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-22T22:39:43.483Z
@Joe: Yeah, that is exactly what is not rigorous about my argument.  I would be _more rigorously surprised_ :) if it is possible to prove that there are not local maxima without performing the exhaustive search.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-22T22:46:01.453Z
@Tsuyoshi It seems like local maxima cannot occur for very short path lengths, and only seem likely to exist close to God's number, which is why I think it's not so definite that they do exist.
Joe Fitzsimons
<co.combinatorics><puzzles>
Are there local maxima in the number of moves required to solve a Rubik's Cube?
Joe Fitzsimons
# Are there local maxima in the number of moves required to solve a Rubik's Cube?

(Asked by: username_0 on 2010-10-22)

username_1brought up an interesting point in relation to an attempt to answer an earlier [question](https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard) on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take $S\_A$ moves to solve the cube from configuration $A$, and either $S\_A$ or $S\_A - 1$ moves to solve the cube from any position which can be reached in one move from $A$. Now, this isn't necessarily such a problem if $S\_A$ is maximum number of moves required to solve the cube in general ([God's Number](http://www.cube20.org/) for that cube), but is definitely a problem if $S\_A$ is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the $3 \times 3 \times 3$ cube would be of interest to me.

**Tags:** co.combinatorics, puzzles

> **Comments:**
> **username_2**: Although I do not have an example, I would be surprised if there aren’t, because that seems to imply that we can compute God’s number by just finding one configuration which is a local maximum (this is not a rigorous argument, though).  
> **username_0**: @Tsuyoshi Ah, but it may not have been known whether or not there were local maxima until after God's Number was computed! But I agree in that I expect these local maxima do exist. I just don't know for sure, and would be interested to find out.  
> **username_2**: @Joe: Yeah, that is exactly what is not rigorous about my argument.  I would be _more rigorously surprised_ :) if it is possible to prove that there are not local maxima without performing the exhaustive search.  
> **username_0**: @Tsuyoshi It seems like local maxima cannot occur for very short path lengths, and only seem likely to exist close to God's number, which is why I think it's not so definite that they do exist.  
> **username_1**: I know Cayley graphs for arbitrary groups can have local maxima. I forget where I saw this result, but I am certain I did see it somewhere. So unless the Rubik's cube group is somehow special, one expects it has local maxima as well.  

---

## 2 answers

### Answer by username_3 on 2011-01-17. Score: 10 | Accepted answer

Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):

> If a position exhibits total
> symmetry, it is of necessity a local
> maximum (all except the start). A
> little thought should make it clear
> why this is the case in the QTM [quarter-turn metric]. For
> the HTM [half-turn metric] it's a bit more subtle but not
> too bad.
>
> ...
>
> Such a position is pons asinorum,
> which is distance 12 in QTM and
> distance 6 in HTM (U2D2F2B2L2R2).

I don't see why this is the case for the half-turn metric; but for
the quarter-turn metric it is clear. In a position with total symmetry, all neighboring positions must be at the same path length (since all moves are equivalent by symmetry). So a position with total symmetry must be either a local maximum or a strict local minimum. But strict local minima cannot exist... there has to be *some* move that reduces the distance to the solved state, just by the definition of the distance. The symmetry argument translates to the $n \times n \times n$ cube, as does the example position provided.

> **Comments:**
> **username_4**: What a simple argument, this is brilliant!  
> **username_0**: Excellent, that's a very nice argument!  

---

### Answer by username_3 on 2011-01-13. Score: 2

Here's an extremely heuristic argument that suggests where local maxima may be found. Let $N\_d$ be the number of positions that require exactly $d$ moves to solve. Each move from such a position takes the cube to distance $d-1$, $d$, or $d+1$; so there are a total of $N\_{d-1} + N\_d + N\_{d+1}$ positions that are accessible. There are $M$ moves from each position, leading to $M$ new positions; a position at distance $d$ is a local maximum when none of these $M$ positions are at distance $d+1$. If we take these positions to be drawn uniformly at random from the accessible positions (which, of course, they aren't; this is the heuristic part), we have:

$$
\begin{eqnarray}
X\_d &=& P\left[\text{ a given position at }d\text{ is a local max }\right] \\
&=& \left(\frac{N\_{d-1} + N\_d}{N\_{d-1} + N\_d + N\_{d+1}}\right)^M \\
&=& \left(1 + \frac{N\_{d+1}}{N\_{d-1} + N\_d}\right)^{-M}.
\end{eqnarray}
$$

The expected number of local maxima at distance $d$ is $N\_d X\_d$.

For the $3 \times 3 \times 3$ cube, the number of moves from a given position is $M=18$, and estimates for $N\_d$ are provided at [God's Number is 20](http://www.cube20.org). Using these values, we find the expected number of local maxima to be $N\_{16} X\_{16} = 0.2$, $N\_{17} X\_{17} = 9 \times 10^9$, and $N\_{18} X\_{18} = 1.5 \times 10^{19}$. So there are unlikely to be any local maxima for $d \le 16$. At $d=17$, the total number of positions is estimated to be $12 \times 10^{18}$, so one might expect to test a billion positions before finding a local maximum. Finally, at $d=18$, one expects a local maximum in every twenty positions.

> **Comments:**
> **username_0**: Thanks. It is however not clear to me that $N_{d-1}+N_{d}+N_{d+1}$ is the correct number of states accessible from the $N_d$ states of distance $d$. If for example there are local maxima of distance $d-1$ this would seem not to hold. It also seems to break for any state of distance $d$ for which all neighbouring states have distance $d-1$ or $d+1$, since this state cannot be reached in 1 move from any of the states of distance $d$. I have no idea how common or rare these situations will be.  

---

