another shot at Rubik's cube

On Monday I wrote that the Rubik's cube can be solved in 26 moves, where a move is defined as a half-turn or a quarter-turn of any face.

I'd forgotten that number, which I got from Wikipedia.

Then I came across this article at MathTrek, claiming 26 moves. The strategy was basically as follows: find the positions from which one could get to the starting position by making only half-turns, and no quarter-turns (call this set S); it turns out that from any of these, one can get to the starting position in 13 moves, and there are about 15,000 of them. Then the remaining items were put into sets such that the members of any such set only differed by half-turns; this roughly means that it's enough to reduce a single member of each set to some member of S. There are 1.4 trillion such sets, which sounds like a lot but is only one part in 30,000 of all the configurations of the cube. It turns out that a member of each such set can be reduced to a member of S in 16 moves, and 13+16 = 29. But the algorithm implied here solves most configurations in 26 moves or less; those that weren't, they solved by a brute-force computation.

Now, this sort of two-stage computation could probably be made better if the two stages were roughly equal in "size", that is, if 15,000 and 1.4 trillion (the product of which is roughly the number of configurations of the Rubik's cube) were equal. This is since the computation time is roughly proportional to the sum of these. If we have the constraint that the product of two numbers x and y is a known constant k, then we can minimize the sum of those numbers by taking x = y = k^1/2. Of course, in the case of the Rubik's cube there might not be some natural class of configurations with size roughly the square root of the total number of configurations.

Similarly, if we had a problem with k possible configurations and a three-stage reduction, you'd ideally want to reduce the number of possible configurations by a factor of k^1/3 at each stage.

But this is probably all useless, because if there were two intermediate subgroups you could reduce to, you'd probably want to take both of them even if you weren't lucky enough to have them at sizes k^1/3 and k^2/3 as would be ideal.