cube files
Indexed Cube Lovers Archive
Complete Search of Subgroup Defined by Edge Cubies
Submitted by Richard Korf on Fri, 05/02/2008 - 12:11.I recently completed a complete breadth-first search of the subgroup of the 3x3x3 cube defined only by the edge cubies. In other words, think of a cube where all the corner cubies are indistinguishable, and a state is defined only by the edge cubies. It took about 35 days on a dual-processor workstation, with three terabytes of disk storage. This was done without any use of symmetries. Here's the number of unique states at each depth:
0 1
1 18
2 243
3 3240
4 42807
5 555866
6 7070103
7 87801812
8 1050559626
0 1
1 18
2 243
3 3240
4 42807
5 555866
6 7070103
7 87801812
8 1050559626
» 9 comments | read more
Twenty-Three Moves Suffice
Submitted by rokicki on Tue, 04/29/2008 - 13:45.After solving more than 200,000 cosets, we have been able to show that every position of Rubik's cube can be solved in 23 or fewer face turns.
The key contribution for this new result was 7.8 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks, using idle time on the render farm that was used for pictures such as Spider-Man 3 and Surf's Up.
No distance 21 positions were found in this search, despite solving a total of more than four million billion cube positions.
The same techniques for the proof of twenty-five moves were used, just on many more computers.
The key contribution for this new result was 7.8 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks, using idle time on the render farm that was used for pictures such as Spider-Man 3 and Surf's Up.
No distance 21 positions were found in this search, despite solving a total of more than four million billion cube positions.
The same techniques for the proof of twenty-five moves were used, just on many more computers.
» 41 comments | read more
Blockbuilding analyses
Submitted by Bruce Norskog on Sat, 04/05/2008 - 19:39.I've done a few more analyses that may be of some interest to the speedcubing community. I'm guessing the first two may have been done before. Such an analysis has been talked about on speedcubing forums (such as in this thread http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13163), but I haven't located any actual results. I'll be happy to give credit for any prior result, if I'm made aware of it.
The goal in these analyses is to build a 2x2x2 sub-block from a scrambled cube state. These analyses do not consider choosing the easiest of eight possible such blocks, but rather one such block is picked, and the distance distribution for all possible scrambles is determined for building that block. Only the three edges and the one corner for that block need to be considered. There are 10560 edge configurations and 24 corner configurations, for a total of 253440 positions. The analysis was carried out in both FTM and QTM.
» 14 comments | read more
Some thoughts about a proof, that 24 moves suffice
Submitted by Herbert Kociemba on Thu, 04/03/2008 - 11:28.I thought about the number of cosets of H=<U,D,R2,L2,F2,B2> we need to
compute to show, that 24 moves suffice.
It is not difficult to show that the number of cosets needes for 24 moves is
at most 64430, provided that we get a maximum of 20 moves in each coset (which
is quite realistic).
» 7 comments | read more
Non trivial identities
Submitted by mdlazreg on Wed, 04/02/2008 - 02:17.As you know there is a recurrent formula based on the cube trivial identities that holds true up to level 5 in QTM. It breaks at level 6:
P[0] = 1
P[1] = 12
P[2] = 114
P[3] = 1,068
P[4] = 10,011
P[5] = 93,840
P[6] < 879,624
The real number at level 6 is 878,880 which is 744 shorter than what the formula predicts.
This discrepancy is obviously caused by some identities other than the trivial ones.
Does anyone have the list of all those identities?
The only ones I know about are the ones listed in Jaap's website:
P[0] = 1
P[1] = 12
P[2] = 114
P[3] = 1,068
P[4] = 10,011
P[5] = 93,840
P[6] < 879,624
The real number at level 6 is 878,880 which is 744 shorter than what the formula predicts.
This discrepancy is obviously caused by some identities other than the trivial ones.
Does anyone have the list of all those identities?
The only ones I know about are the ones listed in Jaap's website:
» 45 comments | read more
How Close Are We to God's Algorithm?
Submitted by Jerry Bryan on Thu, 03/27/2008 - 11:26.Tom Rokicki's message about 25 moves as a new upper limit in the face turn metric got me to thinking about how close we might be to God's Algorithm.
First, I think a distinction must be made that I really hadn't thought about very much. It occurs to me that Tom's method or something akin to it might eventually be able to determine the diameter of the cube group in the face turn metric without actually enumerating the complete God's algorithm. Which is to say, Tom's method is a near-optimal solver for cosets. Generally speaking, it doesn't determine optional solutions and it doesn't determine solutions for individual positions. But that's ok for determining the diameter. If Tom's program could reduce the overall upper limit for the diameter down to some N and if at least one position could be found for which the optional solution required N moves, then the diameter would be proven to be N. And the best candidate we have for N right now is 20. So I think it's possible or even likely that the diameter problem will be solved before the full God's Algorithm problem will be solved. That possibility hadn't occurred to me until recently.
First, I think a distinction must be made that I really hadn't thought about very much. It occurs to me that Tom's method or something akin to it might eventually be able to determine the diameter of the cube group in the face turn metric without actually enumerating the complete God's algorithm. Which is to say, Tom's method is a near-optimal solver for cosets. Generally speaking, it doesn't determine optional solutions and it doesn't determine solutions for individual positions. But that's ok for determining the diameter. If Tom's program could reduce the overall upper limit for the diameter down to some N and if at least one position could be found for which the optional solution required N moves, then the diameter would be proven to be N. And the best candidate we have for N right now is 20. So I think it's possible or even likely that the diameter problem will be solved before the full God's Algorithm problem will be solved. That possibility hadn't occurred to me until recently.
» 11 comments | read more
Twenty-Five Moves Suffice
Submitted by rokicki on Thu, 03/20/2008 - 14:26.On March the 3rd I finally finished the last coset required to prove that 25 moves suffice.
I have finally finished a draft version of a paper detailing the technique and result:
http://tomas.rokicki.com/rubik25.pdf
The technique uses the coset solver I have described previously here (over the past two years)
but I have also made it faster, and also gotten a new machine that is faster and has more memory to run these cosets more quickly.
In the end, it required about 4,000 cosets to be solved to prove a bound of 25.
By solved, I mean an upper bound on the largest distance in that coset was found;
I have finally finished a draft version of a paper detailing the technique and result:
http://tomas.rokicki.com/rubik25.pdf
The technique uses the coset solver I have described previously here (over the past two years)
but I have also made it faster, and also gotten a new machine that is faster and has more memory to run these cosets more quickly.
In the end, it required about 4,000 cosets to be solved to prove a bound of 25.
By solved, I mean an upper bound on the largest distance in that coset was found;
» 20 comments | read more
Prime numbers and Rubik cube
Submitted by mdlazreg on Fri, 03/07/2008 - 20:32.The most fascinating thing about prime numbers is how to predict one.
For example in the following list:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
only 2, 5, 7, 11, 13, 17 and 19 are prime numbers.
Now if we look at the Rubik cube's positions, we can also count them, something like:
U D F B L R U' D' F' B' L' R' UU UD UF UB UL UR UU' UD' UF' UB' UL' UR'....
Similar to the prime number concept we can come up with the prime cube position concept. So in the above list UU' is not a prime position.
In prime numbers theory, the following theorem has been proved:
P(x)~x/ln(x) where P(x) is the prime numbers counting function.
For example in the following list:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
only 2, 5, 7, 11, 13, 17 and 19 are prime numbers.
Now if we look at the Rubik cube's positions, we can also count them, something like:
U D F B L R U' D' F' B' L' R' UU UD UF UB UL UR UU' UD' UF' UB' UL' UR'....
Similar to the prime number concept we can come up with the prime cube position concept. So in the above list UU' is not a prime position.
In prime numbers theory, the following theorem has been proved:
P(x)~x/ln(x) where P(x) is the prime numbers counting function.
» 17 comments | read more
2 questions
Submitted by mdlazreg on Thu, 02/21/2008 - 02:02.Hi,
I am asking for help to understand the second phase of the 2-phases algorithm. I do understand the first phase.
My question is once we bring the scrambled cube to a position in the G1 = subgroup, how is this position taken to the Identity?
Kociemba says the following in his website:
In phase 2 the algorithm restores the cube in the subgroup G1, using only moves of this subgroup. It restores the permutation of the 8 corners, the permutation of the 8 edges of the U-face and D-face and the permutation of the 4 UD-slice edges. The heuristic function h2(a,b,c) only estimates the number of moves that are necessary to reach the goal state, because there are too many different elements in G1.
I am asking for help to understand the second phase of the 2-phases algorithm. I do understand the first phase.
My question is once we bring the scrambled cube to a position in the G1 =
Kociemba says the following in his website:
In phase 2 the algorithm restores the cube in the subgroup G1, using only moves of this subgroup. It restores the permutation of the 8 corners, the permutation of the 8 edges of the U-face and D-face and the permutation of the 4 UD-slice edges. The heuristic function h2(a,b,c) only estimates the number of moves that are necessary to reach the goal state, because there are too many different elements in G1.
» 7 comments | read more
Some "F2L" computer analyses
Submitted by Bruce Norskog on Tue, 02/19/2008 - 22:18.I have done some "restricted" God's algorithm calculations for solving two layers of Rubik's Cube, given that the four edges of the face layer are already solved. I say it's a "restricted" calculation because it only considers certain moves or sequences of moves. For convenience, I will consider the two layers to be solved are the bottom layer (generally referred to as the D layer), and the layer above that (typically referred to by speedcubers as the E layer).
Given that four edges of the D layer are taken to be solved, the remaining four edges being considered (those that belong in the E layer) must be distributed among 8 possible edge locations. So the number of configurations for those four edges is 8*7*6*5*(24) = 26880 (including orientations). The four corner cubies being considered (those that belong in the D layer) have 8*7*6*5*(34) = 136080 configurations (including orientations). This makes for a total of 26880*136080 = 3,657,830,400 configurations.
» 6 comments | read more
