Discussions on the mathematics of the cube

algorithm for generating permutations for the rubik cube


let's say I want to distribute permutation checking over say 10 computers.
so if there are a total of n permutations the first machine will check n/10.
the second will check from n/10 to 2n/10
third will check from 2n/10 to 3n/10.
and so forth.
the algorithm that generates permtuations needs to generate the ith permutation in O(1)
so that I can efficiently start each machine's work.
what algos for generating permtuations do you know that can do this ?


Second largest coset solved yet of actual Rubik's positions

After solving the trivial coset [All positions that have the same orientation as the START position] published here Largest coset solved yet of actual Rubik's positions
I went ahead and calculated the full distribution of the flipped coset [All positions that have the same orientation as Reid's position (The only known 26q*)].

Depth         Trivial coset           Flipped coset
0                         1                       0
1                         4                       0
2                        10                       0

basic algorithms and schreier sims ?

hi, where can I find a comprehensive exposition with explanations and examples, the kind of stuff that you can really learn from ?
I'm trying to implement this for solving the cube, it's a hobby project of mine.

I've noticed that another approach(if I use some basic algos like http://www.ryanheise.com/cube/beginner.html ) would be to pattern match the cube and "hardcode" all the cases of ryan heise and this would also yield a solution.

I'm a begginer with the cube, I almost solved it in reality and would like to write code to solve it.

(I have already set up an opengl simulation and

UF and RBL generate the whole cube group

The two simple generators UF and RBL (without any rotations) generate the whole cube group.

It's surprising to me that these two very simple generators suffice.

It's easy to see no shorter set of generators (expressed in face turns) suffice because you need at least five faces.

Presentation for Rubik's cube

I just found a recent post by "secondmouse" on sci.math that deserves a wider audience. I'll quote it here in full.
I found the following short presentation for the
miniature 2x2x2 Rubik's cube of order 3674160:

    < a,b,c | a^4 = b^4 = c^4 = 1,
                 ababa = babab,
                 bcbcb = cbcbc,
                 abcba = bcbac,
                 bcacb = cacba,
                 cabac = abacb,
                 (ac)^2 (ab)^3 (cb)^2 = 1 >

See the following link for more info as to why

1,000,000 cubes optimally solved in both QTM and FTM

I have solved all 1,000,000 random cube positions from the earlier article now in both QTM and HTM. Here is the resulting grid:
    12h 13h 14h  15h   16h    17h    18h   19h     sum
15q   1   1   3    2     -      -      -     -       7
16q   -   2  18   48    35      -      -     -     103
17q   -   3  23  143   347    354      -     -     870
18q   -   5  40  305  1713   4520   2034     -    8617
19q   -   1  40  505  5190  29711  33363   474   69284
20q   -   2  39  674  9932 100164 212466  7213  330490
21q   -   -   9  345  7697 104052 301668 16371  430142
22q   -   -   -   41  1533  28173 120449  9720  159916

Largest coset solved yet of actual Rubik's positions

Using Tom Rokicki's coset solver as well as his optimal solver I managed to do a full analysis of the corner and edge permutations of all the 3x3x3 cube positions that have the orientation in the solved state.

Here is the distribution table:
0              1
1              4
2             10
3             36
4            123
5            368
6           1336
7           4928
8          16839
9          63920
10        257888
11       1019992
12       4317941
13      20240924
14     102343680
15     568081384
16    3458261494
17   22676234692
18  153062896516

Positions with the same distance in both QTM and FTM

Does anyone know the number of positions that have the same distance in both QTM and FTM metrics? These are positions similar to:
do nothing                                      (0q* , 0f*)
U                                               (1q* , 1f*) 
U R                                             (2q* , 2f*) 
F B U D R L F B U D R L 	                (12q*, 12f*)
F B U D R L F' B' U' D' R' L' 	                (12q*, 12f*)
F' B' R' L' F B U D R' L' U' D'  	        (12q*, 12f*) 
F B R' L' F B U' D' R L U' D'  	                (12q*, 12f*)
F U F' R B U D' L' D' R U R L' F' D' B L' B'  	(18q*, 18f*)

Rubik Xcode Project

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

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*: 33868
No 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).