http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube "It is not known how many moves is the maximum number required to solve any instance of the Rubik's cube. This number is also known as the diameter of the Cayley graph. An algorithm that solves a cube in the minimum number of moves is known as 'God's algorithm'." ... "A summary of the current state of knowledge is as follows: There exist positions that need 20 face turns (superflip). There exists an algorithm that can always solve in 29 face turns. There exist positions that need 26 quarter turns, and there is an algorithm that can always solve in 42 quarter turns." On Fri, 7 Jul 2006 dasimov@earthlink.net wrote:

Rich asks:

<< Has the diameter of the Rubik's cube puzzle been established yet? We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk. We can search for edge positions by generating random positions and using the exact distance algorithm to guide a hill-climb away from the start position. But this is only heuristic.

...

...

This is asking, given the usual 6 generators of the group G of all Rubik cube positions (say, holding the armature fixed), what is the maximum over all g in G of [the smallest size of a word in those generators that represents g].

A question stemming from ignorance: Are there results in this area which can specialize to answer Rich's question about G (or at least shed light on it) ?

--Dan

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun