## Wednesday, April 02, 2008

### Rubik's cube: 25 moves is enough

Tomas Rokicki has improved the computer-assisted proof of the maximum number of moves that may be needed to solve Rubik's cube. It has been proven that 26 moves were enough; now, 25 moves are enough. Check it out. ;-)

The number 25 is the rigorous upper bound. The actual maximum number of moves may be lower. The most "complex" known configurations require 20 moves to be solved. So the actual correct maximum number of moves is between 20 and 25 moves. Well, I usually needed hundreds. ;-)

Hat tip: arXiv blog

Update: In 2010, the proof was radically improved. It's possible to sort the Rubik's cube in 20 moves.

Technical note: viewing this blog

Some people with some browsers at some operating systems can't view this blog conveniently enough. I am aware of this fact and can reproduce the problems myself. However, a comparison of costs and benefits implies that I don't want to try to reduce the javascripts that are the likely reasons and search for the ultimate cause.

Everyone with such problems is recommended to download Firefox 3 beta 5, released one hour ago for all operating systems - it works smoothly and very quickly - and bookmark the economical feed versions of this blog, including
Many of these links may be combined in self-evident ways and some of them are available under the RSS logos in the sidebar of this blog. Finally, let me emphasize that I am not encouraging anyone to switch to these feeds! It is just a possible solution to reduce some visitors' problems that I would like to keep on considering as client-side problems.

1. I am too dumb to understand the UI of the applet I have to admit.

How do you solve the cube with a few hundred move? Do you follow an algorithm or do you do it by trail an error?

I found the following algorithm useful: First figure out how to do the top level (of course including the colours of the top cubes on the sides). Learn how to do this systematically.

Then you use the fact that that is a coset of the full group: You just ignore the middle and lower level. Once you realise this, all the rest can be done by conjugating the operations of the remaining cubes into this coset: Say you want to flip an edge cube on the bottom: You rotate the whole cube that the bottom is the new top. Then you perform the operation A that flips the edge cube as a cube of the new top. This destroys the new middle and bottom layer. Then you screw the top layer by 9 degrees say and do the inverse of A. This restores the new middle and new bottom and the net effect is that you flipped two edge pieces on the new top which was the old bottom.

Proceed in a similar way for all the remaining operations. Just note that after the top, you first have to do the edges on the middle layer, then the edges on the bottom (as described above) and then the corners on the bottom.

This procedure also shows what is the group of all operations on the cubes including taking the cube apart modulo the legal operations: It's Z2 x Z2 x Z3: The Z2 is the flip of a single edge, the second Z2 is the permutation of two corners and the Z3 is the rotation of a corner by 120 degrees.

2. Dear Robert, in the flash, just click and drag a particular row/layer of the cube and it will rotate. If you click an inch away from the cube, a similar move will rotate the whole cube.

Yes, I've learned a kind of algorithm. More precisely, the first layer is solved spontaneously. But for the 2nd and 3rd layer (the 3rd starts with the middle boxes and ends with the corners), there are standardized sequences of moves that achieve certain goals. I would have very hard time to solve it without these recipes. Lloyd's 115 is complex enough for me. ;-)