FTM Antipodes of the Edge Group
Submitted by Bruce Norskog on Tue, 07/21/2009 - 11:23.I have done my own independent breadth-first search of the edge group using the face-turn metric. I used symmetry/antisymmetry equivalence classes to reduce the number of elements in the search space. I confirm the "Unique mod M+inv" values for this group/metric that Rokicki reported in 2004.
I reduced the "coordinate space" for the search to 5022205*2048=10285475840 elements by using symmetry/antisymmetry equivalence classes of the edge permutation group. (This gives a much more compact overall coordinate space than using an edge orientation sym-coordinate, at a cost of more time required to calculate representative elements. This allowed me to keep track of reached equivalence classes with a ~1.3 GB bitvector in RAM and 5022205 KB disk files to keep track of distances.)
God's Algorithm out to 13f*
Submitted by rokicki on Wed, 07/15/2009 - 14:51.First, the positions at exactly that distance:
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
God's Algorithm out to 14q*
Submitted by rokicki on Wed, 06/24/2009 - 09:48.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*
Submitted by rokicki on Tue, 06/23/2009 - 10:22.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
Submitted by rokicki on Mon, 06/15/2009 - 20:35.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
Submitted by cubex on Sun, 05/10/2009 - 21:00.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
Submitted by dukerox7593 on Sun, 05/03/2009 - 22:32.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
Submitted by B MacKenzie on Sun, 04/12/2009 - 15:07.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
Submitted by rokicki on Sun, 03/01/2009 - 13:42.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
Submitted by rokicki on Thu, 02/19/2009 - 00:17.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.