Discussions on the mathematics of the cube

Upgraded to apache 2.2.9 and php 4.4.9

Did another long overdue upgrade with apache and php. There's tons of new exploits so it has to be done. We were down for about an hour. Looks like everything still works :)


Twenty-Two Moves Suffice

With a total of 1.28 million cosets solved, we have shown that every position of Rubik's cube can be solved in 22 or fewer face turns.

This required approximately 50 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks.

No distance 21 positions were found in this search, despite solving a total of more than twenty-five million billion cube positions.

There is a short article in New Scientist (August 9th edition) on this problem and this result.

The same techniques for the proof of twenty-five moves were used, just on many more computers.

I have found 310 cosets with an upper bound of 18, and about 82,000 with an upper bound of 19 (or less); all the rest have an upper bound of 20 or less.

Supergroup knowledge

What is known about the supergroup? (That is, the normal cube but with oriented
center facelets.) Have any computer explorations been performed? Any "hard"
positions known? Any coset explorations?

I know Jaap has a supergroup solver embedded in a Java applet. Does anyone else have
any programs?

A start might be an optimal solution length distribution that take a solved cube to a
solved cube, but just change the center facelet twists. But maybe an optimal solver
for the supergroup would just be too slow.

My diploma thesis - Human method evaluator

Recently I finished my diploma thesis. It's about Hume, a program I wrote for evaluating human solving methods for twisty puzzles. The main goal is to let the user describe a method in a minimal way so that new method ideas can be tested quickly and with ease. The program fills in all the dirty work. So far it's less powerful than I'd like it to be, but I'm happy with what I got from it so far, and I'm happy with my thesis (my professor liked it very much, too, which made me even happier). The thesis is online now, the program will follow soon:


Complete Search of Subgroup Defined by Edge Cubies

I recently completed a complete breadth-first search of the subgroup of the 3x3x3 cube defined only by the edge cubies. In other words, think of a cube where all the corner cubies are indistinguishable, and a state is defined only by the edge cubies. It took about 35 days on a dual-processor workstation, with three terabytes of disk storage. This was done without any use of symmetries. Here's the number of unique states at each depth:

0 1
1 18
2 243
3 3240
4 42807
5 555866
6 7070103
7 87801812
8 1050559626

Twenty-Three Moves Suffice

After solving more than 200,000 cosets, we have been able to show that every position of Rubik's cube can be solved in 23 or fewer face turns.

The key contribution for this new result was 7.8 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks, using idle time on the render farm that was used for pictures such as Spider-Man 3 and Surf's Up.

No distance 21 positions were found in this search, despite solving a total of more than four million billion cube positions.

The same techniques for the proof of twenty-five moves were used, just on many more computers.

Blockbuilding analyses

I've done a few more analyses that may be of some interest to the speedcubing community. I'm guessing the first two may have been done before. Such an analysis has been talked about on speedcubing forums (such as in this thread http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13163), but I haven't located any actual results. I'll be happy to give credit for any prior result, if I'm made aware of it.

The goal in these analyses is to build a 2x2x2 sub-block from a scrambled cube state. These analyses do not consider choosing the easiest of eight possible such blocks, but rather one such block is picked, and the distance distribution for all possible scrambles is determined for building that block. Only the three edges and the one corner for that block need to be considered. There are 10560 edge configurations and 24 corner configurations, for a total of 253440 positions. The analysis was carried out in both FTM and QTM.

Some thoughts about a proof, that 24 moves suffice

I thought about the number of cosets of H=<U,D,R2,L2,F2,B2> we need to compute to show, that 24 moves suffice.
It is not difficult to show that the number of cosets needes for 24 moves is at most 64430, provided that we get a maximum of 20 moves in each coset (which is quite realistic).

Non trivial identities

As you know there is a recurrent formula based on the cube trivial identities that holds true up to level 5 in QTM. It breaks at level 6:

P[0] = 1
P[1] = 12
P[2] = 114
P[3] = 1,068
P[4] = 10,011
P[5] = 93,840
P[6] < 879,624

The real number at level 6 is 878,880 which is 744 shorter than what the formula predicts.

This discrepancy is obviously caused by some identities other than the trivial ones.

Does anyone have the list of all those identities?

The only ones I know about are the ones listed in Jaap's website:

How Close Are We to God's Algorithm?

Tom Rokicki's message about 25 moves as a new upper limit in the face turn metric got me to thinking about how close we might be to God's Algorithm.

First, I think a distinction must be made that I really hadn't thought about very much. It occurs to me that Tom's method or something akin to it might eventually be able to determine the diameter of the cube group in the face turn metric without actually enumerating the complete God's algorithm. Which is to say, Tom's method is a near-optimal solver for cosets. Generally speaking, it doesn't determine optional solutions and it doesn't determine solutions for individual positions. But that's ok for determining the diameter. If Tom's program could reduce the overall upper limit for the diameter down to some N and if at least one position could be found for which the optional solution required N moves, then the diameter would be proven to be N. And the best candidate we have for N right now is 20. So I think it's possible or even likely that the diameter problem will be solved before the full God's Algorithm problem will be solved. That possibility hadn't occurred to me until recently.