Discussions on the mathematics of the cube

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.

Mark

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?

Drupal database problem

Folks, I'm in the middle of fighting with the drupal database. While trying to add the ability to contact the admin I managed to mess up the database in some way. As a result I'm reverting the database back to 5 am this morning and anything added after that won't show up.

I'm going to add in the ability for anonymous users to read all the posts and comments but they won't be able to post. A new drupal is in the cards but the problem is transferring all the info from the old drupal to the new is rather difficult.

I'm going to try to add in the lost posts later tonight. Sorry for the trouble everyone, but I'm still learning the idiosyncrasies of drupal. Turning on the menu module was the cause of the trouble and I won't be touching that particular part again :-/

Thirty-One QTM Moves Suffice

As of last Tuesday, with 1200 QTM cosets solved, all at a distance of 25 except two at 24, I've been able to show that 31 moves suffices in the QTM to solve every cube position.

Surprised by the dearth of 26s (none found out of more than 20 trillion positions solved), I decided to take a cue from Radu (and others) and explore the symmetrical positions. In the past few days I've run about 500 cosets with 16-way, 8-way, and 4-way symmetry and have not found any distance-26 positions other than the one that is known.

This is in contrast to the face turn metric, where distance-20 positions pop up much more frequently.

100,000 cubes optimally solved

Using my brandnew Core i7 920 CPU machine (Vista 64 bit with 6 GB of RAM) I solved 100,000 random cubes optimally with a rate of about 4-5 cubes / minute. So the computation took less than two weeks. I got the following results:
14f*:     18
15f*:    197
16f*:   2710
17f*:  26673
18f*:  67099
19f*:   3303
No 20f* cube was encountered. According to Toms results this indeed would be very unlikely and for 100000 cubes the probability should be less than 10-6. The 95% confidence interval for the probability of 18f* is about 0.671 ±0.003, for 17f* 0.267 ±0.003 for 19f* 0.033 ±0.001 and for 16f* 0.027 ±0.001.