Has the diameter of the Rubik's cube puzzle been established yet? ...
Later a number of variations on the original 3x3x3 puzzle appeared, including 4x4x4, 5x5x5, and 2x2x2. It must be quite easy to find the diameter of the last example --- does anybody know what it is?
for the 4x4x4 and larger puzzles, the graph is not vertex transitive, at least not in a natural way. this is because the set of positions is naturally identified with a coset space, H \ G , with a right action of G , the group of (legally obtainable) permutations of the cubies. this of course is true for the 2x2x2 and 3x3x3 cubes, but in those cases, the subgroup H of permutations that preserve the solved state is a normal subgroup of G , so it is safe to identify the set of positions with a group, namely H \ G . this means that there is a difference between asking for the diameter of the graph, which is max d(v, w) , the maximum being over all pairs of vertices (v, w) , and asking for the maximal possible distance from the solved state, which is max d(v_0, v_1) , over all possible vertices v_1 , where v_0 is the vertex for the solved position. mike