Discussions on the mathematics of the cube

Fifteen Puzzle MTM

I wrote a fifteen puzzle simulation back in 2010 which I recently went back to and updated before submitting it as freeware to the Apple App Store.

Playing around, I then plugged my model into my coset solver framework and performed a states at depth enumeration in the multi-tile metric out to depth 23:

XV Puzzle Enumerator Client(bdm.local)

XV Coset Solver
	Fixed tokens in subgroup: 0, 1, 2, 3, 4, 8, 12, 15.
	518,918,400 cosets of size 20,160

Cosets solved since launch: 165,364,141
Average time per coset: 0:00:00.001

Server Status:
XV Puzzle Enumerator Server
Enumeration to depth: 23

Snapshot: Thursday, June 12, 2014 at 11:11:29 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     3                    6 
   2                    11                   18 
   3                    29                   54 
   4                    87                  162 
   5                   253                  486 
   6                   752                1,457 
   7                 2,213                4,334 
   8                 6,379               12,568 
   9                18,205               36,046 
  10                51,785              102,801 
  11               145,489              289,534 
  12               405,728              808,623 
  13             1,118,586            2,231,878 
  14             3,043,537            6,076,994 
  15             8,153,139           16,288,752 
  16            21,464,200           42,897,301 
  17            55,475,870          110,898,278 
  18           140,272,410          280,452,246 
  19           346,202,190          692,243,746 
  20           831,610,844        1,662,949,961 
  21         1,938,788,875        3,877,105,392 
  22         4,370,165,315        8,739,560,829 
  23         9,490,811,983       18,980,345,944 

 Sum        17,207,737,884       34,412,307,411 

518,918,400 of 518,918,400 cosets solved

27 QTM Moves Suffice

Every position of the Rubik's Cube can be solved in at most
27 quarter turns.

This work was supported in part by an allocation of computing time
from the Ohio Supercomputer Center. It was also supported by
computer time from Kent State University's College of Arts and
Sciences. In order to obtain this new result, 25,000 cosets of
the subgroup U,F2,R2,D,B2,L2 were solved to completion, and
34,000,000 cosets were solved to show a bound of 26. No new
positions at a distance of 26 or 25 were found in the solution
of all of these cosets.

Twenty-Eight QTM Moves Suffice

Every position of the Rubik's Cube can be solved in at most
28 quarter turns. The hardest position known in the quarter-turn
metric requires only 26 moves, so this upper bound is probably
not tight.

This new upper bound was found with the generous donation of
computer time from Kent State University's College of Arts and
Sciences. In order to obtain this new result, 7,000 cosets of
the subgroup U,F2,R2,D,B2,L2 were solved to completion. Each
coset took approximately an hour on a 6-core Intel CPU. No new
positions at a distance of 26 or 25 were found in the solution
of all of these cosets.

2x2x2 Cube

I recently added the 2x2x2 cube to my Virtual Rubik app. Playing around with the code I threw together a breadth first god's algorithm calculation using anti-symmetry reduction. This is old stuff but I thought I would post the results just the same.

2x2x2 States At Depth
Depth   Reduced(Oh+)       States
 0             1             1
 1             1             6
 2             3            27
 3             4           120
 4            13           534
 5            35         2,256
 6           126         8,969
 7           398        33,058
 8         1,301       114,149
 9         3,952       360,508
10        10,086       930,588
11        14,658     1,350,852
12         8,619       782,536
13         1,091        90,280
14             8           276
15             0             0

Group Order: 3,674,160

Antipodes:
  1 R R U R F R' U R R U' F U' F' U'

  2 R R U R R F' U R F' R F' U R' F'

  3 R R U R' U F U' R F R' U' R U R

  4 R R U F F R' U' R F' R F' U U F

  5 R R U R' F R R U' R F R' U R R

  6 R R U R R U F U' R F' U R U' R

  7 R R U R R U' R F' U R' U R U U

  8 R U R R F' R F R U' F' U R U' F

Old Domain Names now restored

Hi Everybody,

I've re-activated the old domain names cubezzz.dyndns.org and cubezzz.homelinux.org so all the old links to the Domain of the Cube forum should be working now.

Now that I've thought about it more it actually feels good to get the original URL working again.

You can all thank Tom for coaxing me into it. I still wish dyndns.org could have helped us more, but I guess you get what you pay for.

Mark

Domain name changed (again)

Hi folks,

I'm reverting back to http://cubezzz.dyndns.org/drupal

The other URLs should also work but this one is the canonical URL for the cube forum.

Note that it should also be possible to access the forum directly via http://204.225.123.154

Mark

All 164,604,041,664 Symmetric Positions Solved, QTM

Perhaps the most amazing feat of computer cubing was Silviu Radu and Herbert Kociemba's optimally solving all 164,604,041,664 positions in the half-turn metric back in 2006. Computers were much slower and had much less memory back then, and handling so many different subgroups can be tricky. Radu used GAP to help with the complexity of the group theory, and Michael Reid's optimal solver to provide the fundamental solving algorithms, and Kociemba used his Cube Explorer optimal solver to handle both the smaller subgroups and the positions left over after Radu's subgroup solver ran.

Symmetries and coset actions (Nintendo Ten Billion Barrel tumbler puzzle)

Jaap Scherphuis suggested that I post this result here, and it seems very relevant to the discussions taking place about symmetries in Cube solutions.

I recently calculated a solution for the Nintendo Ten Billion barrel puzzle that solves any position within 38 moves. Forgive the chatty presentation there - though there are GAP files linked, there is very little actual mathematics included in that blog post. This would be a more appropriate place to discuss the details. As far as I know, this is the first result of its kind for this puzzle, but I'm very convinced I missed a far better result.

Classification of the symmetries and antisymmetries of Rubik's cube

In 2005, Mike Godfrey and me computed the number of of essentially different cubes regarding the 48 symmetries of the cube (group M) and the inversion, see here for details.
We used the Lemma of Burnside to find this number. Since then I wondered if it would be possible to confirm this number by explicitly analyzing all possible symmetries/antisymmetries of the cube.

Solving the 4x4x4 in 57 moves(OBTM)

According to my computation, the 4x4x4 cube can be solved no more than 57 moves.
The solving algorithm is based on tsai's 8-step method which can be found here: link

The only modification is that I merged step 3 & step 4 to one step.

For some reasons, the algorithm cannot be defined to the conversions between subsets, but can be defined to the conversions between sets:
S0: <U R F D L B Uw Rw Fw Dw Lw Bw>
step 1 =>
S1: <U R F D L B> * <U R F D L B Uw2 Rw Fw2 Dw2 Lw Bw2>
step 2 =>
S2: <U R F D L B> * <U R2 F D L2 B Uw2 Rw2 Fw2 Dw2 Lw2 Bw2>
step 3 & step4 =>
S3: <U R F D L B>
3x3x3 solver =>
S4: Solved State