cube files
Indexed Cube Lovers Archive
Rubik Xcode Project
Submitted by B MacKenzie on Fri, 01/29/2010 - 19:46.I have put together some source code demonstrating my approach to modeling the Rubik's cube puzzle. I have made an attempt to make the code clear, understandable and well commented. The language is Objective C and makes much use of the Mac OS Foundation and Application kit class libraries. So it is pretty Mac specific although C++ programmers may wish to browse the source files for ideas. Although the syntax is different, as object oriented languages C++ and Objective C bear many similarities.
Those interested may download the Rubik Xcode Project from my web site.
1,000,000 cubes optimally solved
Submitted by rokicki on Sat, 01/23/2010 - 20:57.Using my relatively new Core i7 920 CPU machine (Linux 64-bit with 12GB of RAM) I solved 1,000,000 random cubes optimally at a rate of about 20 cubes per minute. The computation took about four weeks (I also used a few other slower boxes to do some of them). I got the following results:
12f*: 1 13f*: 14 14f*: 172 15f*: 2063 16f*: 26448 17f*: 267027 18f*: 670407 19f*: 33868No 20f* cube was encountered, which is as expected. No symmetrical or anti-symmetrical positions were encountered.
These results are very close to Kociemba's results for 100,000 cubes; much closer to his overall predictions than those extrapolated from the 250 cosets I ran completely. This seems to indicate that running random cubes may be a more effective way to get a distribution estimate than by running many fewer random cosets (but which contain collectively many more individual positions).
» 4 comments | read more
Void cube diameter at least 20 (face turn metric)
Submitted by rokicki on Tue, 01/19/2010 - 20:15.The void cube is the 3x3 without centers. For every legal 3x3 void position, there are 12 possible ways the centers can be inserted to yield a legal 3x3 cube position. (Pick any of the six colors for the top, then pick one of the adjacent four colors for the front; half of the time the result will have the wrong axis parity).
The "superflip" void position has a distance of 20. This can be shown by computing the optimal solution for all 12 axis insertions in the 3x3 cube; this yields only three unique positions (mod M), and all three have a distance of 20.
U1F1U2F1L2B1U2F1L3R3F2D1R2U2L2B1F3L1F2D1 (20f*) //superflip
The "superflip" void position has a distance of 20. This can be shown by computing the optimal solution for all 12 axis insertions in the 3x3 cube; this yields only three unique positions (mod M), and all three have a distance of 20.
U1F1U2F1L2B1U2F1L3R3F2D1R2U2L2B1F3L1F2D1 (20f*) //superflip
» 11 comments | read more
An analysis of the corner and edge orientations of the 3x3x3 cube
Submitted by mdlazreg on Wed, 01/13/2010 - 13:49.An analysis of the corner and edge permutations of the 3x3x3 cube has already been done by Bruce Norskog. His results for the quarter-turn metric are:
Distance Positions -------- --------- 0q 1 1q 12 2q 114 3q 1,068 4q 10,011 5q 93,840 6q 877,956 7q 8,197,896 8q 76,405,543 9q 710,142,108 10q 6,565,779,580 11q 59,762,006,092 12q 506,821,901,799
» 24 comments | read more
An interesting conjugate class
Submitted by mdlazreg on Fri, 01/01/2010 - 11:51.As you know the number of conjugate classes of the cube is 81120.
Unfortunately as far as I know there is no fast way to calculate the optimal distances distribution for a chosen conjugacy class. The only way is to search for the optimal distance of each position one by one. That is what I did for the following conjugacy class:
CE x CC : 1_1_1_1_1_1_1_1_4 x 1_1_1_1_4
which has 495*6*2^3*70*6*3^3 = 269438400 positions and which include the 12 cube generators.
I did this search however only for one orientation which reduced the number to 495*6*70*6 = 1247400 positions. Here is the optimal distribution:
Unfortunately as far as I know there is no fast way to calculate the optimal distances distribution for a chosen conjugacy class. The only way is to search for the optimal distance of each position one by one. That is what I did for the following conjugacy class:
CE x CC : 1_1_1_1_1_1_1_1_4 x 1_1_1_1_4
which has 495*6*2^3*70*6*3^3 = 269438400 positions and which include the 12 cube generators.
I did this search however only for one orientation which reduced the number to 495*6*70*6 = 1247400 positions. Here is the optimal distribution:
» 4 comments | read more
New estimate for 20f*: 300,000,000
Submitted by rokicki on Sat, 11/28/2009 - 15:15.Over the past few weeks I've run 250 random cosets of the Kociemba
group, each with 19,508,428,800 positions, out to completion,
calculating an optimal solution to all. This is a total of
4,877,107,200,000 positions, almost all unique modulo M+inv.
I ran these to try to get a better estimate of the total count of
20f* positions and also to compare the overall histogram of
position depths against my previous work to calculate the exact
count of 13f* positions, and Kociemba's recent experiment to
optimally solve a one hundred thousand random cube positions.
Of these 250 random cosets, 232 had absolutely no distance-20
» 8 comments | read more
Syllables and Graphs
Submitted by Jerry Bryan on Sat, 11/14/2009 - 14:27.I've been reading a little bit about graph theory, and I wish I knew more about it. So pardon what may perhaps be a bit of naiveté about graphs on my part.
I suspect that everyone who reads this forum is familiar with Cayley graphs and how they relate to Rubik's cube space. One of the best references in this regard may be found at http://www.jaapsch.net/puzzles/cayley.htm I also suspect who everyone reads this forum is familiar with the concept of doing a breadth first search while storing all the results as a way of investigating a space such as the Cayley graph for Rubik's cube.
» 7 comments | read more
Fast solver for arbitrary target groups
Submitted by mdlazreg on Thu, 11/12/2009 - 09:06.As you know one of the breakthrough of cube computing is Silviu's successful depth calculation of all symmetrical positions. This breakthrough used a two phase algorithm that has the symmetrical positions as its target group. Regular solvers will simply stop once they hit the position they want to solve but Silviu's idea is to never stop until all positions in the target group are hit... This way of solving is very fast and it is what Rokiki has used to calculate the "group that fixes the edges".
My question is can this be applied to arbitrary target groups whose elements share something in common? for example let's say my target group is some conjugacy class of the cube.
My question is can this be applied to arbitrary target groups whose elements share something in common? for example let's say my target group is some conjugacy class of the cube.
» 10 comments | read more
DFS
Submitted by mdlazreg on Sun, 11/01/2009 - 18:22.I modified kociemba's optimal solver so that it calculates the depth of sequences in a Depth-first search manner.
The moves order I used is URFDLBU'R'F'D'L'B'.
Here are the initial results after an hour or so of running :
The moves order I used is URFDLBU'R'F'D'L'B'.
Here are the initial results after an hour or so of running :
./optiqtm
initializing memory.
initializing tables.........................................................
loading pruning table (538 MB) from disk................
U
-1 UU
--2 UUR
---3 UURU
----4 UURUU
-----5 UURUUR
------6 UURUURU
-------7 UURUURUU
--------8 UURUURUUR
---------9 UURUURUURU
----------10 UURUURUURUU
-----------11 UURUURUURUUR
------------12 UURUURUURUURU
-------------13 UURUURUURUURUU
-------------14 UURUURUURUURUUR
---------------15 UURUURUURUURUURU
----------------16 UURUURUURUURUURUU
---------------15 UURUURUURUURUURUR
---------------15 UURUURUURUURUURUF
---------------15 UURUURUURUURUURUD
---------------15 UURUURUURUURUURUL
-----------------17 UURUURUURUURUURULU
----------------16 UURUURUURUURUURULR
----------------16 UURUURUURUURUURULF
------------------18 UURUURUURUURUURULFU
-----------------17 UURUURUURUURUURULFR
-----------------17 UURUURUURUURUURULFF
-----------------17 UURUURUURUURUURULFD
-----------------17 UURUURUURUURUURULFL
-----------------17 UURUURUURUURUURULFB
-------------------19 UURUURUURUURUURULFBU
------------------18 UURUURUURUURUURULFBR
------------------18 UURUURUURUURUURULFBF
------------------18 UURUURUURUURUURULFBD
--------------------20 UURUURUURUURUURULFBDU
-------------------19 UURUURUURUURUURULFBDR
-------------------19 UURUURUURUURUURULFBDF
-------------------19 UURUURUURUURUURULFBDD
-------------------19 UURUURUURUURUURULFBDL
-------------------19 UURUURUURUURUURULFBDB
-------------------19 UURUURUURUURUURULFBDU'
-------------------19 UURUURUURUURUURULFBDR'
-------------------19 UURUURUURUURUURULFBDF'
-------------------19 UURUURUURUURUURULFBDL'
-------------------19 UURUURUURUURUURULFBDB'
-------------------19 UURUURUURUURUURULFBL
------------------18 UURUURUURUURUURULFBB
------------------18 UURUURUURUURUURULFBU'
------------------18 UURUURUURUURUURULFBR'
--------------------20 UURUURUURUURUURULFBR'U
-------------------19 UURUURUURUURUURULFBR'F
-------------------19 UURUURUURUURUURULFBR'D
-------------------19 UURUURUURUURUURULFBR'L
-------------------19 UURUURUURUURUURULFBR'B
---------------------21 UURUURUURUURUURULFBR'BU
--------------------20 UURUURUURUURUURULFBR'BR
--------------------20 UURUURUURUURUURULFBR'BF
--------------------20 UURUURUURUURUURULFBR'BD
--------------------20 UURUURUURUURUURULFBR'BL
--------------------20 UURUURUURUURUURULFBR'BB
--------------------20 UURUURUURUURUURULFBR'BU'
--------------------20 UURUURUURUURUURULFBR'BR'
--------------------20 UURUURUURUURUURULFBR'BF'
--------------------20 UURUURUURUURUURULFBR'BD'
--------------------20 UURUURUURUURUURULFBR'BL'
--------------------20 UURUURUURUURUURULFBR'U'
-------------------19 UURUURUURUURUURULFBR'R'
-------------------19 UURUURUURUURUURULFBR'F'
-------------------19 UURUURUURUURUURULFBR'D'
-------------------19 UURUURUURUURUURULFBR'L'
-------------------19 UURUURUURUURUURULFBR'B'
-------------------19 UURUURUURUURUURULFBF'
------------------18 UURUURUURUURUURULFBD'
------------------18 UURUURUURUURUURULFBL'
--------------------20 UURUURUURUURUURULFBL'U
-------------------19 UURUURUURUURUURULFBL'R
-------------------19 UURUURUURUURUURULFBL'F
---------------------21 UURUURUURUURUURULFBL'FU
--------------------20 UURUURUURUURUURULFBL'FR
--------------------20 UURUURUURUURUURULFBL'FF
--------------------20 UURUURUURUURUURULFBL'FD
--------------------20 UURUURUURUURUURULFBL'FL
--------------------20 UURUURUURUURUURULFBL'FB
--------------------20 UURUURUURUURUURULFBL'FU'
----------------------22 UURUURUURUURUURULFBL'FU'U
---------------------21 UURUURUURUURUURULFBL'FU'R
---------------------21 UURUURUURUURUURULFBL'FU'F
---------------------21 UURUURUURUURUURULFBL'FU'D
---------------------21 UURUURUURUURUURULFBL'FU'L
---------------------21 UURUURUURUURUURULFBL'FU'B
---------------------21 UURUURUURUURUURULFBL'FU'U'
---------------------21 UURUURUURUURUURULFBL'FU'R'
---------------------21 UURUURUURUURUURULFBL'FU'F'
---------------------21 UURUURUURUURUURULFBL'FU'D'
---------------------21 UURUURUURUURUURULFBL'FU'L'
---------------------21 UURUURUURUURUURULFBL'FU'B'
---------------------21 UURUURUURUURUURULFBL'FR'
--------------------20 UURUURUURUURUURULFBL'FD'
--------------------20 UURUURUURUURUURULFBL'FL'
--------------------20 UURUURUURUURUURULFBL'FB'
--------------------20 UURUURUURUURUURULFBL'D
---------------------21 UURUURUURUURUURULFBL'DU
--------------------20 UURUURUURUURUURULFBL'DR
--------------------20 UURUURUURUURUURULFBL'DF
--------------------20 UURUURUURUURUURULFBL'DD
--------------------20 UURUURUURUURUURULFBL'DL
--------------------20 UURUURUURUURUURULFBL'DB
--------------------20 UURUURUURUURUURULFBL'DU'
--------------------20 UURUURUURUURUURULFBL'DR'
--------------------20 UURUURUURUURUURULFBL'DF'
--------------------20 UURUURUURUURUURULFBL'DL'
--------------------20 UURUURUURUURUURULFBL'DB'
--------------------20 UURUURUURUURUURULFBL'B
-------------------19 UURUURUURUURUURULFBL'U'
-------------------19 UURUURUURUURUURULFBL'R'
-------------------19 UURUURUURUURUURULFBL'F'
-------------------19 UURUURUURUURUURULFBL'D'
-------------------19 UURUURUURUURUURULFBL'L'
-------------------19 UURUURUURUURUURULFBL'B'
-------------------19 UURUURUURUURUURULFU'
-----------------17 UURUURUURUURUURULFR'
-----------------17 UURUURUURUURUURULFD'
-----------------17 UURUURUURUURUURULFL'
-------------------19 UURUURUURUURUURULFL'U
------------------18 UURUURUURUURUURULFL'R
------------------18 UURUURUURUURUURULFL'F
--------------------20 UURUURUURUURUURULFL'FU
-------------------19 UURUURUURUURUURULFL'FR
-------------------19 UURUURUURUURUURULFL'FF
-------------------19 UURUURUURUURUURULFL'FD
-------------------19 UURUURUURUURUURULFL'FL
---------------------21 UURUURUURUURUURULFL'FLU
--------------------20 UURUURUURUURUURULFL'FLR
--------------------20 UURUURUURUURUURULFL'FLF
--------------------20 UURUURUURUURUURULFL'FLD
--------------------20 UURUURUURUURUURULFL'FLL
--------------------20 UURUURUURUURUURULFL'FLB
--------------------20 UURUURUURUURUURULFL'FLU'
--------------------20 UURUURUURUURUURULFL'FLR'
--------------------20 UURUURUURUURUURULFL'FLF'
--------------------20 UURUURUURUURUURULFL'FLD'
--------------------20 UURUURUURUURUURULFL'FLB'
--------------------20 UURUURUURUURUURULFL'FB
-------------------19 UURUURUURUURUURULFL'FU'
-------------------19 UURUURUURUURUURULFL'FR'
-------------------19 UURUURUURUURUURULFL'FD'
-------------------19 UURUURUURUURUURULFL'FL'
-------------------19 UURUURUURUURUURULFL'FB'
-------------------19 UURUURUURUURUURULFL'D
------------------18 UURUURUURUURUURULFL'B
------------------18 UURUURUURUURUURULFL'U'
------------------18 UURUURUURUURUURULFL'R'
------------------18 UURUURUURUURUURULFL'F'
------------------18 UURUURUURUURUURULFL'D'
------------------18 UURUURUURUURUURULFL'L'
------------------18 UURUURUURUURUURULFL'B'
------------------18 UURUURUURUURUURULFB'
-----------------17 UURUURUURUURUURULD
------------------18 UURUURUURUURUURULDU
-----------------17 UURUURUURUURUURULDR
-------------------19 UURUURUURUURUURULDRU
--------------------20 UURUURUURUURUURULDRUU
-------------------19 UURUURUURUURUURULDRUR
-------------------19 UURUURUURUURUURULDRUF
-------------------19 UURUURUURUURUURULDRUD
-------------------19 UURUURUURUURUURULDRUL
-------------------19 UURUURUURUURUURULDRUB
-------------------19 UURUURUURUURUURULDRUR'
-------------------19 UURUURUURUURUURULDRUF'
-------------------19 UURUURUURUURUURULDRUD'
-------------------19 UURUURUURUURUURULDRUL'
-------------------19 UURUURUURUURUURULDRUB'
-------------------19 UURUURUURUURUURULDRR
------------------18 UURUURUURUURUURULDRF
------------------18 UURUURUURUURUURULDRD
------------------18 UURUURUURUURUURULDRL
------------------18 UURUURUURUURUURULDRB
------------------18 UURUURUURUURUURULDRU'
------------------18 UURUURUURUURUURULDRF'
------------------18 UURUURUURUURUURULDRD'
------------------18 UURUURUURUURUURULDRL'
------------------18 UURUURUURUURUURULDRB'
------------------18 UURUURUURUURUURULDF
-----------------17 UURUURUURUURUURULDD
-----------------17 UURUURUURUURUURULDL
-----------------17 UURUURUURUURUURULDB
-----------------17 UURUURUURUURUURULDU'
-----------------17 UURUURUURUURUURULDR'
-----------------17 UURUURUURUURUURULDF'
-------------------19 UURUURUURUURUURULDF'U
------------------18 UURUURUURUURUURULDF'R
» 3 comments | read more
Commutator elements of the cube
Submitted by mdlazreg on Sat, 10/31/2009 - 18:35.I was wondering if the number of commutator elements of the cube is known?
Commutator elements are of the form ABA'B' where A and B are some sequences.
It seems that the subgroup generated by the commutator elements is half the size of the cube, but is it the case that every element of the commutator subgroup is a commutator element? if not how many are they and how far they are from solved?
Commutator elements are of the form ABA'B' where A and B are some sequences.
It seems that the subgroup generated by the commutator elements is half the size of the cube, but is it the case that every element of the commutator subgroup is a commutator element? if not how many are they and how far they are from solved?
