<p>At <a href="http://www.cube20.org/" rel="nofollow noreferrer">God's number is 20</a> site you can find a nice distance/count table:</p>

<p><img src="https://i.sstatic.net/ttPGz.jpg" alt="enter image description here"></p>

<p>"... Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher ...."</p>

<p>According to the table if you pick a random configuration it will be with high probability at distance 17-18 from the solution.</p>

<p>See also D. Joyner's notes <a href="http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf" rel="nofollow noreferrer">Mathematics of the Rubik's cube</a> (and D. Joyner's book "Adventures in Group Theory: Rubik’s Cube, Merlin’s Machine, and Other Mathematical Toys")</p>

CC BY-SA 3.0
2012-05-09T12:52:40.663Z
You are mixing up the diameter with the mixing time.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-09T13:52:52.303Z
@TsuyoshiIto: you're right, I edited it trying to save it.
Marzio De Biasi
CC BY-SA 3.0
2012-05-10T00:58:59.260Z
@MarzioDeBiasi Thanks for the link. Nice to see the data.
Lucas Cook
CC BY-SA 3.0
2012-05-10T08:21:35.170Z
@LucasCook: but as commented by Tsuyoshi I didn't answer your second question. It probably involves applying randomly a generator for the group $G$, but I don't know if it's enough to pick *uniformly* at random a generator (simple random walk) and how many times. Perhaps the question can be generalized to Cayley graphs and re-asked here or on cs.stackexchange.com (I don't think it's research level).
Marzio De Biasi
CC BY-SA 3.0
2012-05-09T09:44:30.917Z
2012-05-09T13:50:02.290Z
2012-05-09T13:50:02.290Z
Marzio De Biasi
<p>I saw a <a href="https://cstheory.stackexchange.com/questions/2395/are-there-local-maxima-in-the-number-of-moves-required-to-solve-a-rubiks-cube">previous question about local maxima</a> for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a Rubik's cube.</p>

<blockquote>
  <ol>
  <li>If I were to pick a (solvable) configuration at random, how far is it
  to the solved state? </li>
  <li>How many random moves does it take to sufficiently scramble the cube?</li>
  </ol>
</blockquote>

<p>For the second question, I'm thinking of it as the <em>mixing time</em>, like for the Diaconis 7 shuffle result for a deck of cards. (Perhaps this is the wrong terminology?)</p>

<p>This is related to another question of mine about <a href="https://cstheory.stackexchange.com/questions/11408/scrambling-a-rubiks-cube-by-an-adversarial-noob">adversarially scrambling a Rubik's cube</a>.</p>

<p><strong><em>Edit</strong>: I accepted Marzio's answer, though I still wonder about the mixing time. Google revealed some results for particular finite groups, but I didn't see anything about Rubik's cube. Maybe one of these is applicable / can be ported over?</em></p>

<co.combinatorics><puzzles>
Shortest paths when randomly scrambling a Rubik's cube
Lucas Cook
# Shortest paths when randomly scrambling a Rubik's cube

(Asked by: username_0 on 2012-05-09)

I saw a [previous question about local maxima](https://cstheory.stackexchange.com/questions/2395/are-there-local-maxima-in-the-number-of-moves-required-to-solve-a-rubiks-cube) for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a Rubik's cube.

> 1. If I were to pick a (solvable) configuration at random, how far is it
>    to the solved state?
> 2. How many random moves does it take to sufficiently scramble the cube?

For the second question, I'm thinking of it as the *mixing time*, like for the Diaconis 7 shuffle result for a deck of cards. (Perhaps this is the wrong terminology?)

This is related to another question of mine about [adversarially scrambling a Rubik's cube](https://cstheory.stackexchange.com/questions/11408/scrambling-a-rubiks-cube-by-an-adversarial-noob).

***Edit***: I accepted Marzio's answer, though I still wonder about the mixing time. Google revealed some results for particular finite groups, but I didn't see anything about Rubik's cube. Maybe one of these is applicable / can be ported over?

**Tags:** co.combinatorics, puzzles


---

## 1 answers

### Answer by username_1 on 2012-05-09. Score: 5 | Accepted answer

At [God's number is 20](http://www.cube20.org/) site you can find a nice distance/count table:

![enter image description here](https://i.sstatic.net/ttPGz.jpg)

"... Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher ...."

According to the table if you pick a random configuration it will be with high probability at distance 17-18 from the solution.

See also D. Joyner's notes [Mathematics of the Rubik's cube](http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf) (and D. Joyner's book "Adventures in Group Theory: Rubik’s Cube, Merlin’s Machine, and Other Mathematical Toys")

> **Comments:**
> **username_2**: You are mixing up the diameter with the mixing time.  
> **username_1**: @TsuyoshiIto: you're right, I edited it trying to save it.  
> **username_0**: @MarzioDeBiasi Thanks for the link. Nice to see the data.  
> **username_1**: @LucasCook: but as commented by Tsuyoshi I didn't answer your second question. It probably involves applying randomly a generator for the group $G$, but I don't know if it's enough to pick *uniformly* at random a generator (simple random walk) and how many times. Perhaps the question can be generalized to Cayley graphs and re-asked here or on cs.stackexchange.com (I don't think it's research level).  

---

