6
$\begingroup$

I distinctly remember the news in 2007 about how researchers at Northwestern University had established the upper bound on moves needed to solve a Rubik's Cube at 26. (I haven't been paying attention since, but it's obviously a lot lower now.)

Given: The number of possible states of a proper Rubik's Cube is

$$ 11! \cdot 8! \cdot 3^{8} \cdot 2^{12} = 43,252,003,274,489,856,000 ~~ (4.3252 \times 10^{19}) $$

Using the quarter-turn metric, there are only six (6) possible moves available for any cube at any time (using Singmaster notation):

$$ \text{L, R, U, D, F, and B} $$

Assuming that:

  1. only the quarter-turn metric is used (e.g. $\text{F}2$ is considered two moves, F F),
  2. all moves are in one direction only (e.g. $\text{R'}$ would be accomplished by $\text{R R R}$ [or $\text{R}3$]),
  3. applying a move and subsequently its inverse would be ignored stipulated by (2) above, and also ignoring the same move 4 times (to yield the same original state prior to the 4 moves),

then: a decision tree can be made where each node represents a unique (valid) state. This would be a 6-ary decision tree, with each branch representing each of the 6 basic moves above.

From my CS education, I know that any decision tree with $n$ nodes and $b$ daughter branches per node will have at most $\lceil\textbf{log}_{b} \textbf{n}\rceil$ levels. For states of a Rubik's Cube, this is

$$ \log_{6} (11! \cdot 8! \cdot 3^{8} \cdot 2^{12}) \cong \lceil 24.8473 \rceil = 25 ~\text{levels} $$

What this means is that one can shuffle a Rubik's Cube from any state to any other state (e.g. the solved cube) in not more than 25 moves.

Even though many symmetries and optimizations noted in code20.org show that the max number of moves is lower, my question is regarding the Northwestern Univ. discovery in particular.

Given that

  • the Rubik's Cube was invented in 1974 and publicly introduced in 1980,
  • decision trees in computer science have been around since at least the 1970s, and
  • the Northwestern University research (2007) gave 26 moves as a newly-established upper bound (in agreement with my calculation above),

then my question is:

What took so long?

Is there something lacking in my math above? Or was the complexity of solving the cube not fully understood?

One last side note: I distinctly remember this research announcement in particular as I was teaching a CS lab in grad school at the time, and I discussed this topic with my students. The Northwestern press release seemed to imply that their discovery was a "really big deal", yet the the mathematical analysis seemed obvious to me at the time. Strange...

For the record, I have read the various Rubik's cube questions (and answers) here on math SE (and also CS SE and Stack Overflow), but I couldn't find anything about this topic in particular.

$\endgroup$
  • 1
    $\begingroup$ Your calculation appears to be wrong: for quarter turns in either direction, your link says $26$ moves are required and shows the pattern, while you say $25$ is the maximum needed with quarter turns in one direction. $\endgroup$ – Henry Jan 29 '17 at 18:41
  • $\begingroup$ Simply counting different operation sequences will naturally produce a lower bound, not an upper one. $\endgroup$ – Henning Makholm Jan 29 '17 at 18:41
  • $\begingroup$ Since the same cube configuration is represented by several different nodes, the are more nodes in your tree than configurations of the cube. Therefore it can go deeper. $\endgroup$ – Arthur Jan 29 '17 at 18:52
  • $\begingroup$ @Arthur This is a great question and, if the proposed method doesn't work, I think what you've suggested is probably why. I hope you're considering turning that into an answer! $\endgroup$ – pjs36 Jan 30 '17 at 0:06
  • $\begingroup$ @Arthur: I stipulated that every node in the 6-ary tree is a cube state, not just leaf nodes. Also, given restriction (2) above, there can only be 6 possible child branches (moves) for any given cube state (if I assumed e.g. R and R' to be two distinct moves, then there would be 12 possible moves, 12 daughter branches, and a whole bunch of cycles). I may update the original question (with images) to clarify some points; stay tuned... $\endgroup$ – pr1268 Jan 30 '17 at 0:09
5
$\begingroup$

The nodes in your tree you described are not unique. Sure you can fit 43 quintillion nodes in 25 levels, but because your tree allows for duplicates, you can't be sure that you got all unique positions of the cube.

For example consider the node reached by turning RL compared to the node reached by turning LR.

I think that's what you were getting at with your Rule #3: trying to delete obvious duplicates, but in that case each node no longer has 6 children, therefore you no longer can do $\lceil\log_b n\rceil$. For example how many children does the node reached by RRR have?

FWIW you don't need to define a one-direction-only metric to do this (unfortunately flawed) analysis. In regular half-turn metric, each node will have 18 children. So $\lceil\log_{18} n\rceil=\lceil15.6428\rceil=16$, which is way less than what we know is required, due to so many duplicate nodes being in our tree.

(Credit where credit is due: this is basically @Arthur's answer he gave in the comments.)

$\endgroup$
-1
$\begingroup$

Yes, I've given @timidpueo the credit for answering this, and @Arthur made some great comments, but still I feel a need to clarify the graph topology model I was claiming in reference to solving the Rubik's Cube in 26 or less moves.

First: My question may appear borderline rhetorical (gee, I hope the SE community doesn't kick me out for that!), but I was sincerely curious what took so long for the math to catch up with proving solution move sequences in a finite number of moves.

Second: The topology I had described in the 6-ary tree I mentioned above was substantially lacking in what I had envisioned about 10 years ago (around the time I saw the Northwestern press release). This is mainly carelessness on my part in asking the question above, so I'd like to re-make the claim that the Cube can be solved in 26 moves or less.

Given a (valid) $3 \times 3$ Rubik's Cube, with the same 3 restrictions above in representing a solution, but with the additional restrictions below, I still claim that a solution sequence could be modeled by a 6-ary tree:

  1. With all moves in one direction only, then the decision tree becomes a directed graph. For example, If one were to apply a move $R$ to a cube, then the $R'$ cannot be made simply to return to the original state. (You'd have to make moves $\{R R R\}$ to return to the first state.)

  2. Each node in the 6-ary tree represents one unique state of the cube. This means that there are NO DUPLICATES in the tree. More on that later...

  3. In a theoretical situation where someone considered applying the move sequence $\{R R\}$ twice (returning to the original state), then this represents a philosophical breakdown in what defines solving the Cube. Thus, being a directed graph with each state being unique, then this means that you cannot simply go from $S \rightarrow \{F F\} \rightarrow S' \rightarrow \{F F\} \rightarrow S$. Thus, no cycles, and no duplicate nodes. If you were trying to go from e.g. a solved state to a different state, then using the 6-ary tree model implies that the destination state is the top (root) node.

  4. This also means that the desired (root node) state is arbitrary. My claim is that one can go from any state to any other state in 26 moves (or less), regardless of what those states be. (Of course, most people want to solve the cube, so it goes without reason that the solution state is also the root node.)

  5. If two different solutions were to exist from the same initial state to the same final state, then each would take a different route up the tree, but each intermediate state along each path would be unique from any of the others. But this can't happen! Proof by contradiction: If the same state existed along two different solution paths, then only one solution could exist from that state to the solved state. Inductively, this could be shown all the way down to just two moves, but as I've stated above in (4), that can't happen.

  6. One last point, but a very important one: Despite the limitations I've described, it is still possible to apply a move sequence from any possible state to any other possible state with just the six moves $\{L R F B U D\}$. For those familiar with Singmaster Notation, then think of the counterclockwise "prime" moves, (e.g. $\{L', R', etc.\}$) as the forward move three times, and the inner-layer moves (e.g. $\{.L, etc.\}$) as a combination of $\{L L L R\}$ which accomplishes the same.

A final note: In answering my "What took so long" question, I'm guessing that basing a tree model mathematically to solving the Rubik's Cube took some time to develop properly, and seeing how all the above restrictions in modeling the solution decision tree made things a little complicated, I can now understand why it took a while.

I'd also like to thank the cube20.org web page as it mentions some of the reasons why "God's Number" is only 20 for the complete set of Singmaster moves--but note that their site still mentions 26 moves as a minimum upper bound on solving the Cube using the quarter-turn metric.

Comments are certainly welcome. Thanks!

$\endgroup$
  • 1
    $\begingroup$ I have to agree with Arthur and timidpueo. How can you say that each node in the tree represents a different state of the cube? Applying RRRR gets you to the original state, as do many more complicated moves. You can't just say "ignore those moves", becuase that will reduce the number of nodes in your tree. $\endgroup$ – Deedlit Feb 2 '17 at 13:12
  • 1
    $\begingroup$ Also, your point 8 is false - I'm not following your reasoning at all, but we know that are many ways to get from state A to state B. $\endgroup$ – Deedlit Feb 2 '17 at 13:34
  • $\begingroup$ @Deedlit: Yes, I realize $\{R R R R\}$ will cause a cycle, but refer to #6 above--I claim this can be ignored for philosophical reasons rather than mathematical. Also, my claim for #8 is based on single direction only moves (i.e. face turned clockwise). Still, thanks for the feedback. $\endgroup$ – pr1268 Feb 2 '17 at 13:45
  • 2
    $\begingroup$ Whether you ignore moves for philosophical reasons or mathematical, it doesn't change the fact that ignoring them will reduce the number of nodes in your tree, so you can no longer claim that you have more than 4.3*10^19 nodes after 25 levels. $\endgroup$ – Deedlit Feb 2 '17 at 13:54
  • $\begingroup$ For #8, single direction only doesn't change the fact that you will repeat states. For a simple example, LR is the same as RL. (and, as you point out, you can implement R' by RRR, so for each solution with both directions you can have a solution with one direction.) $\endgroup$ – Deedlit Feb 2 '17 at 13:56

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.