cube files
Indexed Cube Lovers Archive
Solving Rubik's cube in 28 face turns
Submitted by silviu on Thu, 12/22/2005 - 20:53.
In this paper we prove that Rubiks cube can be solved in at most 28 face turns. The proof uses exactly the same method as Michael Reid used in 1995. The only difference is that we show how to avoid the positions at distance 29. The proof was based on the fact that it takes 12 face turns max to take an arbitrary element of the Rubiks cube group into the group H=< U,D,L2,F2,B2,R2 >. And at most 18 face turns to take an element of H to the identity.
The above method can also be formulated in following way:
Given an arbitrary element g in the cube group we multiply it by an element B^-1 from the right such that gB^-1 is in the group H and the length of B^-1 is at most 12 face turns. Then we multiply gB^-1 by an element A^-1 from the right such that gB^-1A^-1=id --> g=AB. And the length of A is at most 18 face turns.
We can assume that B has length 12 or 11 or else we have nothing to prove. Clearly B can be written as B=x1*x2*x3*C where C is of length 9 or 8 and x1,x2,x3 are in the set X={U,L,F,B,R,D,U2,L2,F2,B2,R2,D2,U3,L3,F3,B3,R3,D3}. To show that A*B has length 28 face turns or less we divide in following cases:
1. Assume for all the cases below that the element A has has length 18 w.r.t generators {U,D,U3,D3,U2,L2,F2,B2,R2,D2}.
CASE 1
The element A can be written as E*x1^-1 and the length of E is 17 or less. In this case AB=E*x1^-1*x1*x2*x3*C=E*x2*x3*C and the length of A*B is 28 or less. Because length of E is 17 or less by assumption. Length of x2*x3 is 2. And length of C is 8 or 9.
CASE 2
The element A can be written as E*x2^-1*x1^-1 and the length of E is 18 or less. In this case A*B=E*x2^-1*x1^-1*x1*x2*x3*C=E*x3*C and the length of A*B is 28 or less.
CASE 3
The element A can be written as E*x3^-1*x2^-1*x1^-1 and the length of E is 19 or less. In this case A*B=E*x3^-1*x2^-1*x1^-1*x1*x2*x3*C=E*C. And the length of A*B is clearly 28 or less.
2. Assume for all the cases below that the element A has has length 17 w.r.t generators {U,D,U3,D3,U2,L2,F2,B2,R2,D2}.
CASE 1
a) The element A can be written as E*y if x1=z where y,z are any elements in the set {U,U2,U3} and E of length 16 or less. In this case A*B=E*y*z*x2*x3*C. Because y and z are elements in the set {U,U2,U3} then y*z has either length 1 or length 0. And A*B clearly has length 28 or less.
b) The element A can be written as E*y if x1=z where y,z are any elements in the set {D,D2,D3} and E of lenght 16 or less. In this case A*B=E*y*z*x2*x3*C. Beacues y and z are elements in the set {D,D2,D3} then y*z has either length 1 or length 0. And once again A*B has length 28 or less.
c) The element A can be written as E*L2 if x1 is L, L3 or L2 and the length of E is 16 or less. In this case A*B=E*L2*x1*x2*x3*C. And the length of L2*x1 is clearly 1 or 0. In either case the length of A*B is 28 or less.
d) The element A can be written as E*F2 if x1 is F, F3 or F2 and length of E is 16 or less.
e) The element A can be written as E*B2 if x1 is B, B3 or B2 and length of E is 16 or less.
f) The element A can be written as E*R2 if x1 is R, R3 or R2 and length of E is 16 or less.
CASE 2
The element A can be written as E*x1^-1 and the length of E is 17 or less. In this case AB=E*x1^-1*x1*x2*x3*C=E*x2*x3*C and the length of A*B is 28 or less. Because length of E is 17 or less by assumption. Length of x2*x3 is 2. And length of C is 8 or 9.
CASE 3
The element A can be written as E*x2^-1*x1^-1 and the length of E is 18 or less. In this case A*B=E*x2^-1*x1^-1*x1*x2*x3*C=D*x3*C and the length of A*B is 28 or less.
CASE 4
The element A can be written as E*x3^-1*x2^-1*x1^-1 and the length of E is 19 or less. In this case A*B=E*x3^-1*x2^-1*x1^-1*x1*x2*x3*C=E*C. And the length of A*B is clearly 28 or less.
We must now show that we allways have one of the above cases. To prove it for the case when A has length 18 with respect to generators Y={U,D,U3,D3,U2,L2,F2,B2,R2,D2} we compute following:
1. Let S be the set of elements of length 18 w.r.t Y and X the set {U,L,F,B,R,D,U3,L3,F3,B3,R3,D3,U2,L2,F2,B2,R2,D2}.
Build the set S*X i.e. all possible elements of the form s*x where s is in the set S and x in the set X.
2. Take all elements in S*X of length 18 or more and put them in the set S2.
3. Build the set S2*X.
4. Take all elements in S2*X of length 19 or more and put them in the set S3.
5. Build the set S3*X and check that all elements have length 19 or less.
And now for the case when A has length 17 w.r.t the generators Y={U,D,U3,D3,U2,L2,F2,B2,R2,D2}:
1. Let S be the set of elements of length 17 w.r.t Y. For each element s in S do following steps:
a) Build a1=s*U2,a2=s*U,a3=s*U3 and check if at least one of the a1,a2,a3 have length 16 or less. If yes do nothing. If no add s*U,s*U3,s*U2 to the set S2.
b) Build a=s*L2 and check if the length of a is 16 or less. If yes do nothing. If no add s*L,s*L3,s*L2 to the set S2.
c) Build a=s*F2 and check if the length of a is 16 or less. If yes do nothing. If no add s*F,s*F3,s*F2 to the set S2.
d) Build a=s*B2 and check if the length of a is 16 or less. If yes do nothing. If no add s*B,s*B3,s*B2 to the set S2.
e) Build a=s*R2 and check if the length of a is 16 or less. If yes do nothing. If no add s*R,s*R3,s*R2 to the set S2.
f) Build a1=s*D2,a2=s*D,a3=s*D3 and check if the length of at least one of the a1,a2,a3 have length 16 or less. If yes do nothing. If no add s*D,s*D3,s*D2 to the set S2.
2. Take all elements in S2 of length 18 or more and put them in the set S3.
3. Build the set S3*X (X is the same as above).
4. Take all elements in S3*X of length 19 or more and put them in the set S4.
5. Build S4*X and check that all elements have length 19 or less.
GAP was used to find all elements of length 17 and 18 w.r.t Y. This has been done exactly as Michael Reid describes it in cube lovers. GAP was also used to compute the elements in S2 under step 1. We got 8364 elements in S2 when M symmetry is taken into acount. Step 2-5 was done using Cube Explorer.
Thanks to Herbert Kociemba for sharing the Cube Explorer and to Michael Reid for detailed information about how to compute God's algorithm for the group H.
The above method can also be formulated in following way:
Given an arbitrary element g in the cube group we multiply it by an element B^-1 from the right such that gB^-1 is in the group H and the length of B^-1 is at most 12 face turns. Then we multiply gB^-1 by an element A^-1 from the right such that gB^-1A^-1=id --> g=AB. And the length of A is at most 18 face turns.
We can assume that B has length 12 or 11 or else we have nothing to prove. Clearly B can be written as B=x1*x2*x3*C where C is of length 9 or 8 and x1,x2,x3 are in the set X={U,L,F,B,R,D,U2,L2,F2,B2,R2,D2,U3,L3,F3,B3,R3,D3}. To show that A*B has length 28 face turns or less we divide in following cases:
1. Assume for all the cases below that the element A has has length 18 w.r.t generators {U,D,U3,D3,U2,L2,F2,B2,R2,D2}.
CASE 1
The element A can be written as E*x1^-1 and the length of E is 17 or less. In this case AB=E*x1^-1*x1*x2*x3*C=E*x2*x3*C and the length of A*B is 28 or less. Because length of E is 17 or less by assumption. Length of x2*x3 is 2. And length of C is 8 or 9.
CASE 2
The element A can be written as E*x2^-1*x1^-1 and the length of E is 18 or less. In this case A*B=E*x2^-1*x1^-1*x1*x2*x3*C=E*x3*C and the length of A*B is 28 or less.
CASE 3
The element A can be written as E*x3^-1*x2^-1*x1^-1 and the length of E is 19 or less. In this case A*B=E*x3^-1*x2^-1*x1^-1*x1*x2*x3*C=E*C. And the length of A*B is clearly 28 or less.
2. Assume for all the cases below that the element A has has length 17 w.r.t generators {U,D,U3,D3,U2,L2,F2,B2,R2,D2}.
CASE 1
a) The element A can be written as E*y if x1=z where y,z are any elements in the set {U,U2,U3} and E of length 16 or less. In this case A*B=E*y*z*x2*x3*C. Because y and z are elements in the set {U,U2,U3} then y*z has either length 1 or length 0. And A*B clearly has length 28 or less.
b) The element A can be written as E*y if x1=z where y,z are any elements in the set {D,D2,D3} and E of lenght 16 or less. In this case A*B=E*y*z*x2*x3*C. Beacues y and z are elements in the set {D,D2,D3} then y*z has either length 1 or length 0. And once again A*B has length 28 or less.
c) The element A can be written as E*L2 if x1 is L, L3 or L2 and the length of E is 16 or less. In this case A*B=E*L2*x1*x2*x3*C. And the length of L2*x1 is clearly 1 or 0. In either case the length of A*B is 28 or less.
d) The element A can be written as E*F2 if x1 is F, F3 or F2 and length of E is 16 or less.
e) The element A can be written as E*B2 if x1 is B, B3 or B2 and length of E is 16 or less.
f) The element A can be written as E*R2 if x1 is R, R3 or R2 and length of E is 16 or less.
CASE 2
The element A can be written as E*x1^-1 and the length of E is 17 or less. In this case AB=E*x1^-1*x1*x2*x3*C=E*x2*x3*C and the length of A*B is 28 or less. Because length of E is 17 or less by assumption. Length of x2*x3 is 2. And length of C is 8 or 9.
CASE 3
The element A can be written as E*x2^-1*x1^-1 and the length of E is 18 or less. In this case A*B=E*x2^-1*x1^-1*x1*x2*x3*C=D*x3*C and the length of A*B is 28 or less.
CASE 4
The element A can be written as E*x3^-1*x2^-1*x1^-1 and the length of E is 19 or less. In this case A*B=E*x3^-1*x2^-1*x1^-1*x1*x2*x3*C=E*C. And the length of A*B is clearly 28 or less.
We must now show that we allways have one of the above cases. To prove it for the case when A has length 18 with respect to generators Y={U,D,U3,D3,U2,L2,F2,B2,R2,D2} we compute following:
1. Let S be the set of elements of length 18 w.r.t Y and X the set {U,L,F,B,R,D,U3,L3,F3,B3,R3,D3,U2,L2,F2,B2,R2,D2}.
Build the set S*X i.e. all possible elements of the form s*x where s is in the set S and x in the set X.
2. Take all elements in S*X of length 18 or more and put them in the set S2.
3. Build the set S2*X.
4. Take all elements in S2*X of length 19 or more and put them in the set S3.
5. Build the set S3*X and check that all elements have length 19 or less.
And now for the case when A has length 17 w.r.t the generators Y={U,D,U3,D3,U2,L2,F2,B2,R2,D2}:
1. Let S be the set of elements of length 17 w.r.t Y. For each element s in S do following steps:
a) Build a1=s*U2,a2=s*U,a3=s*U3 and check if at least one of the a1,a2,a3 have length 16 or less. If yes do nothing. If no add s*U,s*U3,s*U2 to the set S2.
b) Build a=s*L2 and check if the length of a is 16 or less. If yes do nothing. If no add s*L,s*L3,s*L2 to the set S2.
c) Build a=s*F2 and check if the length of a is 16 or less. If yes do nothing. If no add s*F,s*F3,s*F2 to the set S2.
d) Build a=s*B2 and check if the length of a is 16 or less. If yes do nothing. If no add s*B,s*B3,s*B2 to the set S2.
e) Build a=s*R2 and check if the length of a is 16 or less. If yes do nothing. If no add s*R,s*R3,s*R2 to the set S2.
f) Build a1=s*D2,a2=s*D,a3=s*D3 and check if the length of at least one of the a1,a2,a3 have length 16 or less. If yes do nothing. If no add s*D,s*D3,s*D2 to the set S2.
2. Take all elements in S2 of length 18 or more and put them in the set S3.
3. Build the set S3*X (X is the same as above).
4. Take all elements in S3*X of length 19 or more and put them in the set S4.
5. Build S4*X and check that all elements have length 19 or less.
GAP was used to find all elements of length 17 and 18 w.r.t Y. This has been done exactly as Michael Reid describes it in cube lovers. GAP was also used to compute the elements in S2 under step 1. We got 8364 elements in S2 when M symmetry is taken into acount. Step 2-5 was done using Cube Explorer.
Thanks to Herbert Kociemba for sharing the Cube Explorer and to Michael Reid for detailed information about how to compute God's algorithm for the group H.
