Discussions on the mathematics of the cube

Solving Rubik's cube in 28 face turns

In this paper we prove that Rubiks cube can be solved in at most 28 face turns. The proof uses exactly the same method as Michael Reid used in 1995. The only difference is that we show how to avoid the positions at distance 29. The proof was based on the fact that it takes 12 face turns max to take an arbitrary element of the Rubiks cube group into the group H=< U,D,L2,F2,B2,R2 >. And at most 18 face turns to take an element of H to the identity.

The above method can also be formulated in following way:

Given an arbitrary element g in the cube group we multiply it by an element B^-1 from the right such that gB^-1 is in the group H and the length of B^-1 is at most 12 face turns. Then we multiply gB^-1 by an element A^-1 from the right such that gB^-1A^-1=id --> g=AB. And the length of A is at most 18 face turns.

Optimal solutions for two important subgroups

I have computed optimal solutions for following subgroups of the cube:
Group that fixes cubies


Distance        Nr of pos       Unique wrt M    Unique wrt M + inv

0q              1               1               1
2q              0               0               0			
4q              0               0               0
6q              0               0               0
8q              0               0               0
10q             0               0               0
12q             441             11              8
14q             3944            87              52
16q             32110           708             396

Square One God's Algorithm Computed

I reported this to the most visible Square One guy I could find on the web (Jaap Scherphius), and he sent me here. Yes, I have spent the last year or so computing God's Algorithm for Square One, in the center-flip-count domain, taking advantage of all top/bottom rotational degeneracies available. The table calculation itself is finished, but I am not finished analyzing it yet. I can report that the maximum number of flips required to get back to START is 13, with many shapes (not just square-square) contributing to that number.

The main stumbling block to reporting results at the moment is that I discovered a unexpected position-counting problem, where the shape degeneracy interferes with the 16-fold starting position degeneracy, and which requires me to do a recount on the tables. I will post the results back here in a few days when the recount is finished.

Rubik's cube can be solved in 38 quarter turns max

Silviu recently posted a result where he provides move sequences to solve all positions of the corners with an even corner permutation in 22 quarter turns or less without any net effect on the edges. This, combined with a result by Tomas Rokicki that the edges can be solved in 18 quarter turns or less, allowed Silviu to conclude that Rubik's cube can always be solved in 18+22 = 40 quarter turns or less. I have used a C++ program to verify Silviu's sequences do not exceed 22 quarter turns; and combined with applying "M-symmetry" and inverses to those sequences, correctly solve all even permutation and orientation possibilities for the corners with no net effect on the edges.

Looking at Rokicki's analysis further, one can see that there are relatively few positions in the edges-only case that require more than 16 quarter turns. For the cases of 16 or less quarter turns, the edges can be solved, and then the corners can be solved with Silviu's sequences, in no more than 38 quarter turns. Showing that the other cases in the edges-only analysis of more than 16 quarter turns can be solved in 38 quarter turns or less (including corners) would therefore mean that all positions of Rubik's cube can be solved in 38 quarter turns or less.

Solving Rubik's cube in 40 quarter turns

Recently it has been discovered that the cube restricted to edges can be solved in at most 18 quarter turns. This calculation can be
found at http://www.cubeman.org .This means that given an arbitrary cube in the whole cube group one can solve the edges in at most 18 quarter turns. Once the edges are solved there are 44089920 possibilities for the corners. We prove that each of this configurations can be solved in at most 22 quarter turns. A list of all this configurations expressed in the generators can be found at: http://www.efd.lth.se/~f01sr/ under the link "Data file" (txt document). This list contains only representatives up to M-symmetry+inverse.

Upgraded to php 4.4.1 last (all) night

Your sysadmin was rather adventurous last night. Both Apache and php were upgraded. One of more interesting things admins see is clever hacking attempts. Someone managed to get an executable into the /tmp directory of the server via wget. The program then proceeded to spawn copies of itself in memory. I'm pretty sure it was an attack on drupal so a drupal upgrade may be in the cards. How they managed to run wget on my machine without a login I don't understand. I'll be watching the processes on the server closely...

Let me know if anything is broken.

An analysis of the corner and edge permutations of the 3x3x3 cube

I have generated a distance table using the quarter-turn metric for positions of the Rubik's cube (the standard 3x3x3 cube) where the orientation of the cubies is ignored. That is, the permutation of the corner cubies and the permutation of the edge cubies are considered, but not the orientation of either the edge or corner cubies. This is a set of 8!*12!/2 or 9,656,672,256,000 positions. To the best of my knowledge, this is (now) the largest "subset" of the 3x3x3 cube that this has been done for!

I used symmetry in the corner permutations, so that my programs "only" needed to store values for 984*12!/2 or 235,668,787,200 positions. The "real" size (considering symmetry in both the corner permutations and edge permutations) I found to be 201,181,803,792 positions. So about 17% of the stored positions are redundant with respect to the set of symmetrically distinct positions.

The 4x4x4 centres can be solved in 22 moves

In the yahoo speedcubing forum Chris Hardwick asked a question about analysis of solving the centres of the 4x4x4 cube. I felt that it was an easy thing to look at using my own solving program, so here are the results.

Finding God's Algorithm for the centres only was too hard a task since there are 24!/4!^6 = 3246670537110000 possible centre arrangements. I therefore split it into two stages.

First of all, solving 2 particular opposite centre colours on the 4x4x4 cube, placing them on any 2 opposite faces.

depth 0, positions 6, total 6
depth 1, positions 36, total 42
depth 2, positions 624, total 666

Exhaustive search of the cube space

I have been dabbling with the numbers and here is what I have come up with: Let's assume that Moore's law will hold for another X years. This is not unreasonable following advancements in parallel processor designs, quantum and biological computing. So, in X years according to this model, computers could have the potential computing power of N=2^(X/1.5) times the power of todays computers. If a respectable computer from today could optimally solve (considering the optimal solvers of today) a cube in 30 minutes (1800 seconds)...then a computer from this possible future could solve the cube in about 1800/N seconds. Now, assuming we were to hack away at this until these God computers came about, we would only net the equivalent of twice the computing time on these new computers, or about 36 months. This means that to solve the cube completely by time T in years, we would need to solve around 4.8 billion cubes/second. If we also consider farming this out to other computers of equivalent capabilities and enumerating the reduced cube space of 450541810590509978, then we can solve for a potential time frame on exhaustively searching the cube space.

Antisymmetry and enumeration of LL algorithms

I have been trying to enumerate all LL algorithms, (following Bernard Helmstetter's work) and cannot seem to reduce the 62208 permutations to the 1211 he has come up with. I am unaware of whether or not he used antisymmetry for his reductions. Using GAP and U rotations and reflections I have come up with a total of 8020. Initially considering antisymmetry as well (removing order 2 permutations and the identity from consideration. Note: I did not consider antisymmetric positions with dihedral symmetry or reflections) still does not bring it close to 1211. I was using Martin Schoenert's method in GAP and a very slow algorithm I wrote to determine equivalence classes from conjugation with a group (automorphism) separately with the same results. If anyone would like to see my definitions I will post them.