Discussions on the mathematics of the cube

God's Algorithm out to 14q*

I've computed the count of positions out to 14 quarter turns.

First, positions at exactly the given distance:

 d  mod M + inv         mod M      positions
-- ------------ ------------- --------------
 0            1             1              1
 1            1             1             12
 2            5             5            114
 3           17            25           1068
 4          130           219          10011
 5         1031          1978          93840
 6         9393         18395         878880
 7        86183        171529        8221632
 8       802788       1601725       76843595

God's Algorithm out to 12f*

I just completed exploring all positions of the cube out to depth 12 in the face turn metric.

The first table is the count of positions with exactly the given depth.

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            2            2             18
 2            8            9            243
 3           48           75           3240
 4          509          934          43239
 5         6198        12077         574908
 6        80178       159131        7618438
 7      1053077      2101575      100803036

Twenty-Nine QTM Moves Suffice

With 25,000 QTM cosets proved to have a distance of 25 or less,
we have shown that there are no positions that require 30 or more
quarter turns to solve. All these sets were run on my personal
machines, mostly on a new single i7 920 box.

These sets cover more than 4e16 of the total 4e19 cube positions,
when inverses and symmetries are taken into account, and no new
distance-26 position was found. This indicates that distance-26
positions are extremely rare; I conjecture the known one is the
only distance-26 position.

In order to take the step to a proof of 28, I would need a couple

Inappropriate links

Any inappropriate link (i.e. not math and/or puzzle related) will be deleted. I'd like to keep the forum completely free of ads with the sole exception of ads for books about puzzles, or at least limited to materials appropriate for the site.

For newbies or younger readers:

If you find some of the posts are too difficult to understand please go ahead and ask questions! The people here are willing to help explain things.


Interesting Problem/Puzzle/Game

ok here is the game:
your opponent has a secret number that is 4 digits long. the digits are 0-9 and no digit can be repeated in the number (in other words all 4 numbers are different)
examples: 1234, 1948, 4950
you have to guess the number
when you guess a number: your opponent gives you back 2 numbers (x,y)
number x is the amount of numbers in the right place
number y is the amount of numbers right but in the wrong place
anyone have an algorithm to solve this problem using the 2 numbers given back?

subgroup enumeration

I've been playing around with the Rubik's cube subgroup generated by the turns: (U U' D D' L2 R2 F2 B2) which I refer to as the D4h cube subgroup after the symmetry invariance of the generator set. This, I believe, is the subgroup employed by Kociemba in his two phase algorithm. Anyway, I have performed a partial enumeration of the subgroup and its coset space. I was wondering if anyone might be able to confirm these numbers as a check on my methodology.

Six Face/D4h Coset Enumeration (q turns)
Depth  Cosets     Total
 0         1         1
 1         4         5

Twenty-Five Random Cosets in the Quarter Turn Metric

As the next step in my exploration of the quarter turn metric, after finishing a proof of an upper bound of 30, I decided to run 25 cosets all the way (until I have optimal solutions for all positions). Unlike my runs in the half turn metric in November of 2008, I went ahead and made the search phase run in parallel. In addition, I acquired a newer, faster machine (a Dell Studio XPS with an Intel i7 920 processor).

I decided to run the same 25 cosets I ran for the half turn metric. The results are summarized in the table below.

Sequence             9 10  11  12   13    14     15      16       17        18         19         20         21         22       23

Thirty QTM Moves Suffice

With 10,114 cosets solved in the quarter turn metric, I have shown
that 30 or fewer quarter turns suffice for every Rubik's cube
position. Every coset was shown to have a bound of 25 or less,
except the single coset containing the known distance-26 position.

I also solved every coset exhibiting 4-way, 8-way, and 16-way
symmetry, and each of these also were found to have a bound of
25 or less. Thus, if there is an additional distance-26 or
greater position, it must have symmetry of only 2, 3, or 6, or
no symmetry at all. I believe, based on this, that it is likely
that on other distance-26 positions exist.

Last Layer Optimal Solving

I have run all 8020 symmetrically distinct "last layer" positions of Rubik's Cube with the optimal solver of the Cube Explorer program. All these positions could be solved in 16 face turns or less. I also used the number of positions associated with each of these 8020 symmetry class representatives to determine the precise distribution of distances of all 62208 "last layer" (abbreviated LL) positions. Note that this analysis considers solving the last layer with respect to the already solved first two layers.

I note that Helmstetter (see here) has done a similar analysis previously, but his analysis basically only considers solving the last layer pieces relative to themselves, and does not consider what cases may need an additional move to align the last layer properly with the first two layers. My analysis includes all moves needed to solve the last layer with respect to the first two layers. So Helmstetter considered only 1212 cases (15552 "relative" positions reduced by symmetry and antisymmetry), while I considered 8020 cases (62208 "absolute" positions reduced by symmetry).

Relationship of Duplicate Positions and Non-Trivial Identities

(Reconstructed from the Drupal archives.  Much thanks to Mark for all the work he does in supporting this site.)

This message addresses both the Non-Trivial Identities thread and the Generalizing Dan Hoey's Syllables thread.  I thought that I had a good handle on the relationship between Non-Trivial Identities and Duplicate Positions, but I find a confusing discrepancy.

Consider the following four positions.

     w = F  R' F' R  U  F'    w' = F  U' R' F  R  F'
     x = U  F' L' U  L  U'    x' = U  L' U' L  F  U'
     y = U' R  U  R' F' U     y' = U' F  R  U' R' U
     z = F' U  L  F' L' F     z' = F' L  F  L' U' F

It is the case that w=x=y=z, what I call a duplicate position.  This duplicate position is obviously related to the list of 1440 non-trivial identities from the Non-Trivial Identity Thread.  Therefore, I was thinking that (for example) we would find wx', wy', and wz' in the list of 1440 non-trivial identities.  But we don't, or at least not exactly.  We find wx' and wy', but not wz'.  Why not?