# Solving Rubik's cube in 36 quarter turns

Submitted by silviu on Sat, 01/14/2006 - 12:44.

In this paper we present a method of solving Rubik's cube in 36 quarter turns. The proof have many common facts with other methods presented on the forum. In able to prove our claim we have used the corner and edge permutation analysis done for the first time by Bruce Norskog.

We call the group of corner edge permutations of the cube for CEP and cube group for C. Let N be the normal subgroup that fixes cubies. Then we have a homomorphism hom:C->C/N=CEP such that hom(g)="permtutation of cubies done by g". Let

We will show that all elements g in the cube such that hom(g)=x'*

as following elements of CEP:

-U

-UD*

-UD

-UL*

-UL

Conjugating those elements with symmetries will yield solutions of all elements of CEP of the form x

Now let g be an arbitrary element in the cube. Then we can find a h in the cube 14 quarter long in the cube such that hom(g*h) is in T. Every element u in the cube with hom(u) in T can be solved in 22q or 24q so we get following possibilities:

-g*h*f=id where f is 22q long and hom(f) is in T. Then g=f

-g*h*f=id where f is 24q long and hom(f) is in T. Then

g=f

Let us consider the remaining elements g in the cube with hom(g)=y'*

U U D F' L D' R F' D' F' R' B' U' D' B' R F

U U D B R L D R' D' F' R B L' U F F L

U U D B U' B R L D' B' D B' R D L U' R'

U U D F R L B' L' F R L' B L' D F R F

U U D F U F' R' D R' F U' F R' B' U R' U'

U U D D B' L F' R D R D F F R' U D' L

U U D F U' L' F' U B R D R B L B U' F'

U U D F F D F L U L D' R U R F L F'

U U D D F U D F B R L B R R L L B

U U D D F U D F' B' R L F U U D D F

U U D D F R U' F' U' F D' F' B' U' L F F

I have personally checked that they are at distance 17 in CEP. To show that those elements g in the cube with hom(g)=y'*

-The identity(All but 25 elements solvable in 22q, the other 25 are local maxima 24q long)

-R B U L U F R D L D L' U B U U B' D' R F' U' L B (All solvable in 22q)

Call the last element

-hom(g*h)=

-hom(g*h)=id. Then g*h*f=id and f max 22q and g=f

-hom(g*h)=id. Then g*h*f=id and f is 24q long and g=f

The proof is finished. Now some information about how the solution files are stored. Let m be in M(symmetry group). We have not stored solutions for two elemenents x and y having same corner edge permutation (i.e. having hom(x)=hom(y) ) with hom(m

I want to thank my advisor Gert Almkvist for much inspiration and help. My second advisor Victor Ufnarovski who patiently helped me correct a lot of errors. My family for supporting me. Of course i thank Bruce Norskog for the very hard work he have done on the corner edge permutation analysis. I thank Michael Reid for his solver that i used to show that the 24q positions are local maxima. I thank my cousin in law Daniel Grad who helped with some own made programs. Further i thank the people who contributed to the development of GAP and the people at Lunarc at Lunds University of Sweden for their computers that i used and especially to Per-Anders Wernberg for helping me start quickly.

We call the group of corner edge permutations of the cube for CEP and cube group for C. Let N be the normal subgroup that fixes cubies. Then we have a homomorphism hom:C->C/N=CEP such that hom(g)="permtutation of cubies done by g". Let

**a**be the unique antipode in CEP. Every element in CEP can be written as x***a**. Where x is an element requiring at most 18 quarter turns according to Norskog's analysis. There are 220 elements at distance 17 and 1 element at distance 18. So we could say that all elements of CEP except 220+1 elements can be written as x'***a**where x' is an element requiring at most 16 quarter turns.We will show that all elements g in the cube such that hom(g)=x'*

**a**where x' is some element in CEP requiring 16 quarter turns can be solved in 36q or less. In order to do that we have computed solutions for all elements in the cube group having the same permutation of cubiesas following elements of CEP:

-U

^{2}***a**(All but 14 elements solvable in 22q, the other 14 are local maxima 24q long)-UD*

**a**(All solvable in 22q)-UD

^{-1}***a**(All solvable in 22q)-UL*

**a**(All solvable in 22q)-UL

^{-1}***a**(All solvable in 22q)Conjugating those elements with symmetries will yield solutions of all elements of CEP of the form x

_{1}*x_{2}***a**where x_{1},x_{2}is in the set X={U,L,F,B,R,D,U^{-1},L^{-1},F^{-1},B^{-1},R^{-1},D^{-1}}. Let T be the set {x_{1}*x_{2}***a**|x_{1},x_{2}in hom(X)}. One verifies that**a**is a symmetry i.e.**a**is in the group hom(M). So T is in fact equal to {**a***x_{1}*x_{2}|x_{1},x_{2}in hom(X)} that is because**a**^{-1}*x_{1}*x_{2}***a**=x_{1}'*x_{2}'. Here x_{1},x_{2},x_{1}',x_{2}' are in hom(X). Every element g' of CEP except 220+1 can be written as g'=t*y where t is in T and y is at most 14 quarters long.Now let g be an arbitrary element in the cube. Then we can find a h in the cube 14 quarter long in the cube such that hom(g*h) is in T. Every element u in the cube with hom(u) in T can be solved in 22q or 24q so we get following possibilities:

-g*h*f=id where f is 22q long and hom(f) is in T. Then g=f

^{-1}*h^{-1}has maximal length 14+22q.-g*h*f=id where f is 24q long and hom(f) is in T. Then

g=f

^{-1}*h^{-1}. Let h^{-1}=x_{1}*el. Where x_{1}is a generator and el an element of length max 13. Because f^{-1}is a local maxima it can be writte as d*x_{1}^{-1}where d has length 23. Then g=f^{-1}*h^{-1}=d*x_{1}^{-1}*x_{1}*el. Since d is of length 23 and el of length 13 we have that g is max 36q long.Let us consider the remaining elements g in the cube with hom(g)=y'*

**a**where y' is 17q or 18q. Bruce Norskog has kindly sent me the unique M elements in CEP that are 17q long:U U D F' L D' R F' D' F' R' B' U' D' B' R F

U U D B R L D R' D' F' R B L' U F F L

U U D B U' B R L D' B' D B' R D L U' R'

U U D F R L B' L' F R L' B L' D F R F

U U D F U F' R' D R' F U' F R' B' U R' U'

U U D D B' L F' R D R D F F R' U D' L

U U D F U' L' F' U B R D R B L B U' F'

U U D F F D F L U L D' R U R F L F'

U U D D F U D F B R L B R R L L B

U U D D F U D F' B' R L F U U D D F

U U D D F R U' F' U' F D' F' B' U' L F F

I have personally checked that they are at distance 17 in CEP. To show that those elements g in the cube with hom(g)=y'*

**a**(y' 17q long) are 36q long max we have computed solutions of all elements having following corner edge permutations:-The identity(All but 25 elements solvable in 22q, the other 25 are local maxima 24q long)

-R B U L U F R D L D L' U B U U B' D' R F' U' L B (All solvable in 22q)

Call the last element

**b**. Let S be the set of unique hom(M) elements above(distance 17 elements) and the antipode. One can verify that all elements in S**a**={s***a**| s in S} can be written either as**b***z or as id*z where z is 14 quarter long max. So if we have an element g in the cube such that hom(g)=y'***a**(y' 17q or 18q) then there exists a h in the cube such hom(g*h)=**b**or id and h 13q long. We get following cases:-hom(g*h)=

**b**. Then g*h*f=id and f max 22q and g=f^{-1}*h^{-1}is 22+14q long max.-hom(g*h)=id. Then g*h*f=id and f max 22q and g=f

^{-1}*h^{-1}is 22+14q long max.-hom(g*h)=id. Then g*h*f=id and f is 24q long and g=f

^{-1}*h^{-1}. Then we write h^{-1}as x_{1}*el where el is some element 13q long max and x1 is a generator. Because f^{-1}is a local maxima it can be written as d*x_{1}with d 23q long and thus g=d*x_{1}*x_{1}^{-1}*el=d*el which is 23+13q long max.The proof is finished. Now some information about how the solution files are stored. Let m be in M(symmetry group). We have not stored solutions for two elemenents x and y having same corner edge permutation (i.e. having hom(x)=hom(y) ) with hom(m

^{-1}*x*m)=hom(y) or hom(m^{-1}*x^{-1}*m)=hom(y). The solutions can be found at my home page http://users.student.lth.se/f01sr/ .I want to thank my advisor Gert Almkvist for much inspiration and help. My second advisor Victor Ufnarovski who patiently helped me correct a lot of errors. My family for supporting me. Of course i thank Bruce Norskog for the very hard work he have done on the corner edge permutation analysis. I thank Michael Reid for his solver that i used to show that the 24q positions are local maxima. I thank my cousin in law Daniel Grad who helped with some own made programs. Further i thank the people who contributed to the development of GAP and the people at Lunarc at Lunds University of Sweden for their computers that i used and especially to Per-Anders Wernberg for helping me start quickly.