## Twenty-Two Moves Suffice

Submitted by rokicki on Tue, 08/12/2008 - 20:27.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

Submitted by rokicki on Fri, 06/13/2008 - 16:07.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

Submitted by StefanPochmann on Fri, 05/02/2008 - 14:52.http://stefan-pochmann.info/hume/

Cheers!

Stefan

## Complete Search of Subgroup Defined by Edge Cubies

Submitted by Richard Korf on Fri, 05/02/2008 - 12:11.0 1

1 18

2 243

3 3240

4 42807

5 555866

6 7070103

7 87801812

8 1050559626

## Twenty-Three Moves Suffice

Submitted by rokicki on Tue, 04/29/2008 - 13:45.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

Submitted by Bruce Norskog on Sat, 04/05/2008 - 19:39.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

Submitted by Herbert Kociemba on Thu, 04/03/2008 - 11:28.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

Submitted by mdlazreg on Wed, 04/02/2008 - 02:17.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?

Submitted by Jerry Bryan on Thu, 03/27/2008 - 11:26.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.

## Twenty-Five Moves Suffice

Submitted by rokicki on Thu, 03/20/2008 - 14:26.I have finally finished a draft version of a paper detailing the technique and result:

http://tomas.rokicki.com/rubik25.pdf

The technique uses the coset solver I have described previously here (over the past two years)

but I have also made it faster, and also gotten a new machine that is faster and has more memory to run these cosets more quickly.

In the end, it required about 4,000 cosets to be solved to prove a bound of 25.

By solved, I mean an upper bound on the largest distance in that coset was found;