Discussions on the mathematics of the cube

Site URL changed

I was forced to update the URL of the site this morning. http://dyndns.org saw fit to shut down access from the homelinux.org domain and I had to scramble to switch the site over to the allowed free domain name.

The new URL is http://cubezzz.dyndns.org/drupal

Note that the numeric ip address will also work as I can't guarantee they won't make it necessary to switch to another service in the future as free services tend to disappear.

Let me know at cubexyz at gmail dot com if anything is broken.

Please update your links accordingly.

The Fifteen Puzzle can be solved in 43 "moves"

Of course, it had been previously proved that some positions of the Fifteen Puzzle require 80 moves to solve, but in that work it was assumed that a move only affects one tile at a time. Since people commonly slide up to 3 tiles in the same row or column at once, it seems natural to count such an action as a single move. With this way of counting, which we call the "multi-tile metric," the maximum number of required moves is only 43, and of the 16!/2 = 10,461,394,944,000 valid configurations of the puzzle, there are only 16 antipodes, i.e., positions that actually require 43 moves.

The 16 antipodes include two positions that are mirror-symmetric to themselves. These two positions are those that are obtained by transposing the rows and columns with respect to either diagonal. The other antipodes consist of 7 pairs of positions that are mirror-symmetric with the other. These 14 positions also include 4 pairs of neighboring positions. So only 8 of the antipodes are "strict" antipodes having the property that any move gets you one move closer to the solved state.

Cross-Check Patterns

By applying the 24 rotation symmetries to the corner facelets of the cube one may generate the Cross Pretty Pattern Group. These patterns may be arranged into five conjugate classes: the identity cube, six order two 6-cross patterns, eight order 3 6-cross patterns, six order 4 4-cross patterns and three order 2 4-cross patterns.

By applying the 24 Th symmetries to the edge facelets of the cube one may generate the Check (or Checkerboard ) Pretty Pattern Group. These patterns may be arranged into six conjugate classes: the identity cube, pons asinorum, eight order three 6-check patterns, eight order six 6-check patterns, three order two 4-check patterns and three order two 2-check patterns.

Banning gmail

We are getting tons of bogus accounts from bots using gmail as an email address so I decided to ban signups from using gmail. Old accounts already using gmail will still work. If anyone really wants to get an account using a gmail email address send me an email explaining why you want to join (so I know it's not bot).

Send messages to the admin via cubexyz at gmail dot com


M_R,D Group

Under the God's Algorithm Calculations link to the right of this page there is the following:
        Analysis of the  Group

     Level         Number of      Time       Branching
                   Positions                  Factor

       0               1           0 s          --
       1               4           0 s           4
       2              10           0 s           2.5
       3              24           0 s           2.4
       4              58           0 s           2.416
       5             140           2 s           2.414

Small subgroups and cosets

Hello all, I am making a program to scan subgroups and coset groups of Rubik's cube. For testing purposes, I scanned the square subgroup. It appeared that the corner coordinate of the square subgoup always satisfies a multiple of four antisymmetries (half of which are symmetries). Below follow the results. I computed modulo counts for all 420 antisymmetry subgroups, of which I choose six to display.
Square group table for FTM:
Level   |        | SO     | GO     | inv    | SO+inv | GO+inv |
    0   |      1 |      1 |      1 |      1 |      1 |      1 |

Cubic Symmetry Cycle Representations

In responding to comments to a previous post it became of interest to represent cube states and cubic symmetry elements as facelet permutations in disjoint cycle form appropriate for GAP. I wrote a routine to dump facelet representations in disjoint cycle form and produced a table of the cubic symmetry group in cycle notation. It occured to me that this table might be of use to readers of this forum.

I number the cube facelets in the order they occur in the Singmaster-Reid identity configuration string:

     12 34 56 78 90 12 34 56 78 90 12 34 567 890 123 456 789 012 345 678

The Up facelet of the Up-Front cubie is numbered 1 on through to the Right facelet of the Down-Back-Right cubie which is numbered 48. With this numbering the face turns are represented by the permutations:

God's Algorithm out to 15f*

Yeah, I know this is kind of late, but as promised (or threatened) I have finished my 15f* calculation and here are the results, first positions at exactly that distance (adding a few minor numbers):
 d  (mod M + inv)*     mod M + inv       mod M             positions
--- --------------- ---------------- ---------------- -----------------
 0                1                1                1                 1
 1                2                2                2                18
 2                8                8                9               243
 3               48               48               75              3240
 4              517              509              934             43239
 5             6359             6198            12077            574908
 6            81541            80178           159131           7618438
 7          1067047          1053077          2101575         100803036
 8         14034826         13890036         27762103        1332343288
 9        184907170        183339529        366611212       17596479795
10       2437753739       2419418798       4838564147      232248063316
11      32135500721      31909900767      63818720716     3063288809012
12     423434369503     420569653153     841134600018    40374425656248
13    5575030719304    5538068321152   11076115427897   531653418284628
14   73286135656774   72805484795034  145610854487909  6989320578825358
15  957963000510751  951720657137855 1903440582318440 91365146187124313

Slice turn metric, anyone?

Anyone got a reasonable upper or lower bound for slice turn metric? (Clearly, the 20 result gives us a trivial upper bound of 20.) Lower bounds? Here are position count results; these are the easy ones. I'm hoping this table will magically extend itself. First table is exact count at that level:
dist mod M+inv       mod M     positions
 0           1           1             1
 1           4           4            27
 2          13          19           501
 3         150         236          9175
 4        1920        3642        164900
 5       31341       61457       2912447

God's Number is 20

Every position of Rubik's Cube™ can be solved in twenty moves or less.

With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves.

This was a joint effort between Morley Davidson, John Dethridge,
Herbert Kociemba, and Tomas Rokicki.

More details are posted at http://cube20.org/.