16
$\begingroup$

The upper bound for the number of moves required to solve a regular Rubik's cube has been shown to be 20.

Two questions come to mind:

  1. Does this result have more general significance?

  2. What are the most pressing issue with regards to Rubik's cube (or generalizations) or its group?

  • 7
    http://www.math.harvard.edu/~jjchen/docs/Group%20Theory%20and%20the%20Rubik's%20Cube.pdf here's a pretty good paper on the Rubik's Cube Group, for reference2011-03-01
  • 0
    @Eugene: Nice reference, thanks!2011-03-01

2 Answers 2

5

There are some really advanced algorithms (such like Fridrich method) which can get you to like 30-40 moves solving sequence. It is the fastest, and the best times were obtained using this method. Of course, it involves memorising many algorithms.

Proving that the Rubik's cube can be solved in 20 moves is more like a theoretical result. It's just like fixed point existence theorems: you know it's there, but you cannot find it explicitly. As far as I know, the result was obtained using brute force with powerful computers. An algorithm for solving the cube in 20 moves does not exist.

Edit: I meant an algorithm that can be applied by a human when solving Rubik's cube, not a computer.

  • 0
    Sure it does. Breadth-first search will always find the shortest solution for any such "twisty" (as my friend puts it) puzzle. But it's not exactly fast and would also require enormous amounts of memory.2011-04-10
  • 2
    When solving Rubik's cubes in tournaments, you get 15 seconds to inspect the cube. That's not anywhere near enough time to figure out a God's Algorithm for the scramble, which is why everyone just uses Fridrich or Petrus or other 'easier' methods.2011-11-25
1

A question that I believe remains unanswered is

Starting from the solved position, how many Singmaster moves must be done such that each of the $43252003274489856000$ configurations are roughly equally likely to occur?

That is,

What is the Markov chain mixing time on the Cayley graph of the Rubik's Cube Group with generators $\langle F, F', F^2, B, B', B^2, L, L', L^2, U, U', U^2, D, D', D^2\rangle$?

We can formalize this as the variation distance mixing time, e.g. finding the smallest $t$ such that $|\Pr(X_t \in A) - \pi(A)| \leq 1/4$ for all words of length $t$ or less and for all subsets $A$ of the Rubik's Cube group $G$.

It is in this context that Diaconis and Bayer showed that $7$ dovetail shuffles is sufficient to mix up a deck of 52 playing cards.