Discussions on the mathematics of the cube

Puzzle about the Cube: Coloring the Cayley Graph

Here's an easy puzzle for Rubik's Cube: What's the chromatic number of the Cayley graph for the quarter turn metric?

Here's a slightly harder puzzle: What's the chromatic number of the Cayley graph for the half turn metric? If you can't figure it out, can you figure out an upper bound? A lower bound?

This was discussed on speedsolving.com before, but I think it's a good enough puzzle to present here as well.

God's Algorithm out to 15q*

I've finally managed to compute God's Algorithm out to 15q*. This took longer than I expected; I had difficulties using multiple cores because occasionally the memory consumption of the concurrently-calculated cosets would exceed my physical RAM; even though this was rare, it happened frequently enough to completely stall the computation. Also, the way memory was allocated and freed led to pretty intense memory fragmentation.

In any case, it is finally done; here are the results. First we have positions at exactly that depth:

 d   mod M + inv          mod M       positions

Numerical formula

I wrote a program that counts cube positions by taking into account only the identities of length 4 and the identities of length 12. The results of this program are in the second column below:

 d                  positions I4     positions I4&I12   positions  ALL
--                  ------------     ----------------   --------------

 0                             1                    1                1                        
 1                            12                   12               12                       
 2                           114                  114              114

Drupal database corrupted

Sorry folks, I've been very busy lately and I just noticed the mysql database was badly corrupted on Sept. 6th, 2009. The database is updated daily, but all the backups on Sept. 6th and after are unusable. I think the only post lost was Tom Rokicki's.

I try my best to make sure everything is working but this one slipped through the cracks. Somehow the mysql database ballooned in size to over 2 gigabytes. After that happened the subsequent databases were not backed up correctly.

It would be a good idea for any posts to be buffered in some way before uploading to the forum, especially long ones.

Watermelon Rubik's Cube

I trust that I may be forgiven for being slightly off topic. After all, a watermelon Rubik's cube is not very mathematical. But still, it's an interesting concept.

http://www.watermelon.org/FeaturedRecipe.asp

I am in no way connected with the National Watermelon Promotion Board.

FTM Antipodes of the Edge Group

I have done my own independent breadth-first search of the edge group using the face-turn metric. I used symmetry/antisymmetry equivalence classes to reduce the number of elements in the search space. I confirm the "Unique mod M+inv" values for this group/metric that Rokicki reported in 2004.

I reduced the "coordinate space" for the search to 5022205*2048=10285475840 elements by using symmetry/antisymmetry equivalence classes of the edge permutation group. (This gives a much more compact overall coordinate space than using an edge orientation sym-coordinate, at a cost of more time required to calculate representative elements. This allowed me to keep track of reached equivalence classes with a ~1.3 GB bitvector in RAM and 5022205 KB disk files to keep track of distances.)

God's Algorithm out to 13f*

Just finished running out to a distance of 13 in the face turn metric.

First, the positions at exactly that distance:

 d   mod M + inv          mod M       positions
-- ------------- -------------- ---------------
 0             1              1               1
 1             2              2              18
 2             8              9             243
 3            48             75            3240
 4           509            934           43239
 5          6198          12077          574908
 6         80178         159131         7618438
 7       1053077        2101575       100803036

God's Algorithm out to 14q*

I've computed the count of positions out to 14 quarter turns.

First, positions at exactly the given distance:

 d  mod M + inv         mod M      positions
-- ------------ ------------- --------------
 0            1             1              1
 1            1             1             12
 2            5             5            114
 3           17            25           1068
 4          130           219          10011
 5         1031          1978          93840
 6         9393         18395         878880
 7        86183        171529        8221632
 8       802788       1601725       76843595

God's Algorithm out to 12f*

I just completed exploring all positions of the cube out to depth 12 in the face turn metric.

The first table is the count of positions with exactly the given depth.

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            2            2             18
 2            8            9            243
 3           48           75           3240
 4          509          934          43239
 5         6198        12077         574908
 6        80178       159131        7618438
 7      1053077      2101575      100803036

Twenty-Nine QTM Moves Suffice

With 25,000 QTM cosets proved to have a distance of 25 or less,
we have shown that there are no positions that require 30 or more
quarter turns to solve. All these sets were run on my personal
machines, mostly on a new single i7 920 box.

These sets cover more than 4e16 of the total 4e19 cube positions,
when inverses and symmetries are taken into account, and no new
distance-26 position was found. This indicates that distance-26
positions are extremely rare; I conjecture the known one is the
only distance-26 position.

In order to take the step to a proof of 28, I would need a couple