Max Morgan

From www.norsemathology.org

Jump to: navigation, search

Contents

Optimizing the Solving of A Rubik's Cube

Authors: Max Morgan

Professor: Dr. Andy Long

Course: MAT 385

Date: 4/21/2021


Introduction


Rubik’s cubes were invented in in 1974 by Ernő Rubik. He wanted to make something to teach his students about movement in 3-dimensional space. Eventually it became a big sensation, and it has even spawned its own type of competition called speedcubing, where people try to solve a Rubik’s cube as fast as they possibly can. The goal of this project is to find out the minimum and maximum amount of moves that must be used for “the beginner method” of solving a Rubik’s cube. First, we must talk about how to solve a Rubik’s cube.

There is a certain way that Rubik’s cube algorithms are written. There are letters which represent a side that should be turned. These letters are:

Letter Side

L Left

R Right

U Top

D Bottom

B Back

F Front

In an algorithm, a letter means that side should be turned clockwise (CW) as if you were facing it. To show a counter-clockwise (CCW) turn you would add an apostrophe (Ex. L = left side CW and L’ = left side CCW). A 2 after a number just means to turn it that way twice. To give you some practice with this if you are going to try this yourself, here is the scrambling algorithm that I used. I had the green side facing me with the white face on top, so your cube should look like this:

Image:Showing Shuffle.jpg


Solving


The first goal of solving a Rubik’s cube is to get a cross. Typically, I go for the white cross so I will be using that in my description, but these algorithms will work no matter which color you use. To make the cross, you should have the white side face up, then any white edge pieces should be lined up with the center color of their counterpart (i.e. if the edge piece is orange and white, move it to the orange side) This can take anywhere from 0-2 moves. Once it is in place, if the white is on the bottom, just do F2. If center color counterpart is on the bottom, then do F’ U’ R U. If there is a white edge piece on the side, then simply move it to the bottom and then repeat the previous steps. Worst case scenario would be if every white edge was on the side and after being moved to the bottom, they would be on the opposite side of the cube and have the color counterpart on the bottom. To make the cross under worst case scenario would take 24 moves. The best-case scenario would be that the cross is already solved which requires 0 moves.

Next, we must solve the white corners. To start this off you will want to flip your Rubik’s cube yellow side face up. Then, you will want to see if a corner is in the column that it belongs in.

Image:Column.jpg

If so, perform this algorithm, R U R’ U’, until the corner is solved. This move will be used many times throughout solving, so keep it in mind. The worst-case scenario is that the corners in the opposite bottom corners with the white facing down. Solving this would take 58 moves. The best-case scenario is all of the corners take one use of that move each, which would be 16 moves.

The next step is to solve the second layer of the cube. Next you will want to move an edge piece on top and line it up with its matching color like this:

Image:Middle Layer.jpg

If the edge piece needs to end up on the right side, then do this algorithm: U (R U R’ U’). Then you rotate the left and do: L’ U’ L. If the edge needs to end up on the left side, then do this algorithm instead: U’ L’ U’ L U and rotate the cube to the right and doing: R U’ R’. If there is an edge piece in the wrong spot, then just do one of those algorithms to get it out of that place. The worst-case scenario is just like the corners, where the edge pieces are in the opposite spots on the cube. This would require moving the edge piece out, moving it to the opposite side, and moving it back in. It would take 40 turns. The best-case scenario would be the if the middle layer is already solved.


For the next step of solving the yellow cross, you can start with four different states. These are the dot, L, line, and cross.

Image:Dot.jpg Image:L.jpg Image:Line.jpg Image:Cross.jpg
				 

Thankfully, these all lead into each other, so it’s easy to remember what to do. If you have the dot, do: F (R U R’ U’) F’. This will lead you to an L. You must turn the L so that it faces the upper left corner. Then, you just repeat the previous algorithm. You are left with the line, which should be horizontal. If it is horizontal, then do the algorithm again and you are left with a cross. The cross must then be corrected so that all the edges are on the correct side. The cross will have 3 states, the opposites are correct, two adjacent edges are correct, and the entire cross is solved. If the opposites are correct, then do this algorithm: R U R’ U R U2 R’. This should leave you with two adjacent edges being correct. The correct sides should be moved to the back and right and the same algorithm should be used. The worst-case scenario is that only the opposites are correct. Including moving the top layer, the number of moves would be 16. The best-case scenario is that the cross is already solved which would require 0 moves.

Finally, we solve the last layer. First, we must get the corners in the correct positions. They most likely won’t end up being in the correct orientation though. You will want to check and see if there are any corners in the right place. If not, do this algorithm: U R U’ L’ U R’ U’ L. When there is one corner in the right spot, turn the cube so that it is in the front right corner and do that algorithm until all corners are in the right spots. The worst scenario requires the algorithm to be done 3 times, which would be 24 moves. The best case is if the corners are already in the right positions which would take 0 moves.

Orienting the corners requires the cube to be flipped yellow side up. Then you should do R U R’ U’ until the corner is oriented properly. Then, to get to the next corner, only turn the bottom layer and repeat this process until the cube is solved. The worst-case scenario requires doing the algorithm 12 times and turning the bottom layer 4 times, so the number of moves would be 52. The best-case scenario is that the cube is solved after the previous step. This leaves us with a range of moves being 16-190 moves. The maximum can be reduced by quite a lot if we just optimize our algorithms a little bit.


Improving


Hopefully, you were able to follow along and solve a Rubik’s cube yourself. Now is when we are able to reduce the number of moves required if we think a little bit. “God’s Number”, which is the amount of moves that any Rubik’s cube can be solved in, is 20. This was found by a group of scientists and many computers. However, nobody is expected to be able to solve any Rubik’s cube in just 20 moves. These improvements won’t get us to 20, but they will get us a bit lower than 190. The first improvement that I can think of is when doing the cross if the edges are on the sides. Instead of turning it to the bottom and then doing the earlier 4 move algorithm, you can just use one turn to put the white on top, then move the top back to the proper orientation. This should only take three moves at most, instead of 5. This reduces the maximum amount of moves by 8.

Solving the corners faster is probably the biggest improvement that I found. If the white corners are on the top layer and the piece is directly above its correct position, then there are three possible states. The white is either facing toward you, to the right, or up. If it is facing you, then the algorithm needed is U R U’ R’. This saves you from having to repeat the original algorithm many times over. If the white is facing to the right, then you just do: R U R’. If the white is facing up, then do: R U2 R’ U’ R U R’. These improvements change the maximum amount of moves from 58 to 40, removing 18 needless moves.

The final improvement to make is a much smaller one. It is when we are trying to form the yellow cross. When you repeat the algorithm going from the L to the line, we do F’ then F. This move back could just be ignored, reducing our maximum number of moves by 2 more. This leads to the maximum number of moves using the beginner method from being 190 to 164. There are other methods of solving a Rubik’s cube which reduce the number of moves by a lot more, but they are a bit too complicated to talk about without being extremely boring.

Personal tools