22
$\begingroup$

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question 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 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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tsuyoshi Ito Oct 22 '10 at 22:31
  • $\begingroup$ @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. $\endgroup$ – Joe Fitzsimons Oct 22 '10 at 22:35
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 22 '10 at 22:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Joe Fitzsimons Oct 22 '10 at 22:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Shor Jan 13 '11 at 18:24
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What a simple argument, this is brilliant! $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 17 '11 at 4:49
  • $\begingroup$ Excellent, that's a very nice argument! $\endgroup$ – Joe Fitzsimons Jan 18 '11 at 10:01
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Jan 16 '11 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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