14
$\begingroup$

In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can strictly be solved in at most 20 Singmaster moves (under the face-turn metric) from Rubik's Cube move group $(G, *)$, where $*$ is the concatenation operation (summarized here: https://en.wikipedia.org/wiki/Rubik%27s_Cube_group ). In 2011, Erik Demaine et. al. (Algorithms for Solving Rubik's Cubes, arXiv:1106.5736v1 ) showed that any ($n \times n \times n$) Rubik's cube can optimally be solved in $\Theta (\frac{n^2}{\log(n)})$ steps, also under the face-turn metric.

Say we restrict ourselves to the simpler quarter-turn metric (only allowing for 90 degree rotations), and set up the following scenario:

We hand a ($n \times n \times n$) Rubik's cube to a robot, and program the robot to execute an random set of 90 degree Singmaster moves in $G$, then stop when the cube is solved. We know that the number of total cube states for a $3\times3\times3$ cube is: $||G|| = (2^{27}.3^{14}.5^3.7^2.11) = 43,252,003,274,489,856,000$ (Turner and Gold 1985, Schonert), and we can therefore use the negative binomial distribution calculate the mean number of random system states we need to sample to find a "finished" cube (call this value $S_3$ for the $3\times3\times3$ cube and $S_n$ for the $n \times n \times n$ cube). However, the robot is performing random quarter-turn moves, not necessarily randomly sampling cube configurations.

What distribution can we expect for the number of random 90 degree Singmaster moves necessary for the robot to complete the cube? I suppose we can calculate an upperbound for the expected mean number of required moves by taking a product of $S_n$ and the mean number of random moves necessary to "mix" the cube (I'm unaware of an estimate for this time), but can we do better? Also, I would guess that the "mixing time" for the cube is much faster than the solution time, making it the case that the initial state of the cube shouldn't matter.

(I'm not entirely opposed to allowing for arbitrary 90 or 180 degree Singmaster moves by the robot, but it just seems simpler to only consider the set of quarter-turn moves.)

Update :: Based on Brendan McKay's answer, which I mostly agree with, I intuitively feel that that the number of steps to find a solution for a ($n \times n \times n$) cube via a random walk on the cube's Cayley graph, should be something like $\Theta (||G|| \log (||G||))$. This intuition is coming from the scaling for the expected coverage time for a random walk on an integer lattice.

From: Jonasson, J., Schramm, O. On the cover time of planar graphs. Electronic Communications in Probability 5, pp. 85 - 90 (2000), we have that the cover time for a $d$-dimensional integer lattice $G$ with $n$ vertices scales as: $\Theta(n^2)$ for $d = 1$, $\Theta(n (\log n)^2)$ for $d = 2$, and $\Theta(n \log n)$ for $d \geq 3$. (hat tip to Andreas Rüdinger for his answer to Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice).

For the Cayley graph of a generalized Rubik's cube, it seems like we're in the limit of the sort of connectivity on an integer lattice that yields $\Theta(n \log n)$ covering times. So I suppose, on average, it should take about half this many steps to find the solved cube configuration?

Obviously this is very very sketchy reasoning, and I hesitate to actually write it down.

$\endgroup$
3
  • 3
    $\begingroup$ The cover time is largely irrelevant here. What you're looking for is the hitting time. I would not expect to see a logarithmic factor here. $\endgroup$ Dec 4, 2012 at 7:10
  • $\begingroup$ How close an answer does your "update" method above give to the answer I offer below, which should be very close? $\endgroup$ May 15, 2017 at 15:07
  • $\begingroup$ What is Theta here ? $\endgroup$ Jan 3 at 17:08

3 Answers 3

11
$\begingroup$

I think the expected time for stumbling across the solution is roughly proportional to the number of configurations. The process you describe is walking randomly on a Cayley graph. The limiting distribution is uniform, so after a large number of steps you will be in approximately a random place and the chance of that being the solution is the reciprocal of the number of vertices (i.e. the number of configurations). If someone expert in rapid mixing of Markov chains comes along, they will tell us if this argument can be made rigorous.

ADDED: This much is certain: Say $N$ is the number of configurations. If you start at a random configuration, then the probability of being at the solution configuration after $i$ steps is exactly $1/N$ for every $i$. However these are not independent events. The expected number of solutions seen in the first $N$ steps is exactly 1, but it does not follow that the expected wait for the first solution is $N$.

$\endgroup$
6
  • $\begingroup$ @Brendan McKay Right I think what you're saying makes good sense. For fun, I certainly would be curious to see a more rigorous argument. $\endgroup$ Dec 3, 2012 at 0:04
  • $\begingroup$ @Brendan McKay Why is the expected number of solutions after $N$ steps, $E[x] = 1$? If we're taking a random walk of a Cayley graph, won't there be a large probability, each step, to revisit a previous state? $\endgroup$ Dec 3, 2012 at 10:25
  • $\begingroup$ @FloatingForest: In Brendan's argument, the expected number of solutions you see on the $i$th step is $1/N$ for all $i$. Then sum over $i$ from $1$ to $N$. Expectation is always linear regardless of whether the variables are correlated. $\endgroup$ Dec 3, 2012 at 18:29
  • $\begingroup$ @Timothy Chow Egged myself :), good point. $\endgroup$ Dec 4, 2012 at 3:50
  • 1
    $\begingroup$ While I haven't tried to prove it rigorously, it seems quite obvious that the RW on rubik's cube is locally transient in the sense that if you look at the expected number of visits to the starting configuration before getting mixed is small (bounded, if you consider $n$ by $n$ by $n$ cubes). This means that the expected number of steps to hit a particular configuration is indeed proportional to the number of configurations. $\endgroup$ Dec 4, 2012 at 7:06
1
$\begingroup$

I don't see how this can be answered without crunching through lots of the data generated in Rokicki et al (RKDD)'s calculation. Also I'd guess (off the top of my head) that the expectation value is infinite.

For a given cube state S, let L(S) be the minimal number of turns needed to solve S. RKDD showed L(S)<=20 for all S. Let S+r denote the cube state reached by performing move r on S. There are three possibilities: 1) L(S+r)=1+L(S), i.e. r has made the cube more disordered than it was; 2) L(S+r)=L(S), i.e. r hasn't "improved" S but hasn't made it worse; 3) L(S+r)=L(S)-1, i.e. the move actually makes progress toward a solution.

It seems pretty likely to me that in the more ordered states, most of the available moves won't make progress, and probably most lose progress (add disorder). Even for L=20 (no more disorder is possible) it wouldn't surprise me if most moves don't make progress. Also, the set of (say) L=19 states that can be reached from an L=20 state might be a small fraction of all the L=19 states, and might have different likelihood (higher or lower) of reaching L=18 on the next move than a random L=19 state would have.

It might be feasible to solve this problem exhaustively for the 2x2x2 cube without too much computer resources. For 3x3x3, if you've got a database that lets you quickly determine L(S) for arbitrary S, then you can do some statistical sampling, but we know that the effort it takes to make such a database (it's a possibly proper superset of what RKDD did) is enormous.

$\endgroup$
0
$\begingroup$

If we fix the axes and the centre-faces, which only rotate on the spot, we're left with 12 "edges cubes" and 8 "vertex cubes". Hold a Rubik's cube in your hand, then disassemble it, and you will see what I mean.

Each "edge cube" can occupy 12 places and has 2 faces, providing for $12!\times 2^{12}$ possibilities.

Each "vertex cube" can occupy 8 places and has 3 faces, providing for $8!\times 3^8$ possibilities.

Therefore ignoring the for all intents and purposes identical, centre squares and orientations of the cube, the cube has 519,024,039,293,878,272,000 possible states. Turner and Gold's result excludes the $\frac{11}{12}$ states of the cube which cannot be reached by rotation - only attainable if the pieces are removed and reassembled!

Using Turner and Gold's result the probability of solving it on any given random move is therefore 1 in 43 billion billion.

Knowing from experience that one rarely returns to the same position by random, it can be deduced that serial correlation will have a minor effect upon the cube's path so its behaviour will closely approximate a simple binomial probability.

$n$ being large, this will approximate a normal distribution so the expected number of moves is given by the probability of solving it zero times in $n$ moves equalling $0.5$.

$0.5=\binom{n}{0}p^0q^n$ where $q=(1-1/43,252,003,274,489,856,000)$

$0.5=(1-1/43,252,003,274,489,856,000)^n$

$n=3×10^{19}$ moves should be a pretty accurate estimate of the expected number of moves to solve it.

$\endgroup$
6
  • 1
    $\begingroup$ 11 out of 12 of your states are roads not taken. $\endgroup$ May 21, 2016 at 22:26
  • $\begingroup$ @GerryMyerson assuming you don't disassemble it! But by my passing there they were worn roughly the same. $\endgroup$ May 21, 2016 at 22:52
  • 2
    $\begingroup$ Depends on what you call simple & intuitive. According to Singmaster's Notes on Rubik's Magic Cube, the total permutation of the edge and vertex cubes must be even, so $12!8!/2$. Then, if you orient all but one of the edges, the remaining one is forced, and similarly for the vertices, so $2^{12}/2$ and $3^8/3$. There's a detailed proof of these assertions in Section 2.4 of Bandelow, Inside Rubik's Cube and Beyond. $\endgroup$ May 22, 2016 at 6:29
  • 1
    $\begingroup$ Yes. Are you familiar with the 15-puzzle? Same thing, on a different scale. If the empty square is in the lower right, the other square must be in an even permutation for the thing to be solvable, so only half of all positions are solvable. $\endgroup$ May 22, 2016 at 13:34
  • 1
    $\begingroup$ @GerryMyerson I see what you did there, with your first comment. $\endgroup$
    – Mark S
    Jul 7, 2018 at 17:32

Your Answer

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

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