User:Arjun sunel/Solvability of a 3x3x3 Rubik's Cube State?

From Rosetta Code

Introduction

This article is about the solvability of a 3x3x3 Rubik's Cube. One thing might come in your mind that what is motive behind studying so much about a Rubik's Cube. The reason being that it is one of the most interesting example of Finite Group which we understand by applying moves on the Cube. All the moves of a Rubik's Cube forms a Group. But, in this our concentration is on the problem that if you are given a Cube, how will you determine whether the Cube is solvable or not without actually trying to solve it. Person who are hearing about the Rubik's Cube for the first time need not be disheartened. But, I need help from your side as well in understanding the whole concept. This article requires some of your precious time and a lot of interest from your side, then only you will be able to absorb all the points of the article. I will try my best in making you understand using pictures wherever possible. I will also briefly explain about the evolution of Rubik's Cube, its invention, history etc, but I also suggest you to go through Wikipedia or any online websites if there is any doubt which you think I am unable to explain properly. Suggestions from your side are welcomed.

Rubik's Cube Notations and Properties

1) A Rubik's Cube has 6 faces: Upper  : U Down  : D Left : L Right : R Front : F Back : B

hello world
hello world

2) It consists of a total of 26 cubies.

3) Out of the 26 cubies, 8 are corner cubies, 6 are center cubies and 12 are non-center cubies called edges.

4) Keeping the three axes of the cube fixed, position of centers never gets changed. They only rotate about their axis. However, the positions of edges and corners can be changed.

5) It consists of 54 (9x6) stickers and 6 colors. There are 9 stickers of each color.

6) A Cube is said to be solved if all the stickers of any face consists of a single color.

7) There are two types of moves in Rubik's Cube Solving : Legal and illegal.

Legal Move A legal move is defined as the method of moving a slice of the cube around its perpendicular.

Illegal Move An illegal move consists of taking the pieces apart from the cube, rearrange and place them again in the cube according to the needs. This method is broadly used by most of the frustrated cubers!!!

History

Around 1974, a Hungarian architect named Erno Rubik invented this 3-D puzzle. At that he was working at the Department of Interior Design at the Academy of Applied Arts and Crafts in Budapest. He wanted to teach his students about a 3-D model whose parts move independently, but the system as a whole never falls apart. For this reason, he constructed a 3-D model. One day, he just scrambled the model and tried restoring it. But, he was scratching his head when he was unable to restore it for a long time. That time he realized that, he had accidently given birth to a 3-D puzzle which is today known to us by the name of Rubik's Cube.

hello world

Rubik Cube puzzle became challenge for the people at that time(today as well). But after that, some logical-minded people came and solved it. Soon, the puzzle spread as a viral and the Rubik's Cube became the most selling Puzzle-Toy of the world. Algorithms for solving it kept developing and their optimization continued. Various experiments were held using supercomputers and a God's Number was found. It was founded by a Google team after donating about 35-CPU years of idle computer time. According to their experiment, even if God is given the Rubik's Cube and asked to solve it by using the most efficient algorithm, he would take at most 20 moves in the worst case. The algorithm is known as the God's Algorithm and 20 – the magical number is known as the God's Number.

Frustrated Cuber

But, even after knowing the method for solving the Rubik's Cube, one thing pops up in the mind most of the times. The thing is that if accidently, the Cube slips from your hand and falls on the ground, spreading all the cubies apart on the floor of the room. What will you do now? You will collect all the cubies and try to combine them again (if they are not so badly broken to be thrown into the Trash!!). After combining them all, you will try to solve it. But, you are unable to solve it for a long time even though your best solving time may be 2 or 3 minutes. What can be the reason? May be it is your bad day!!. But, even if it may be your bad day, you should be able to solve it (if you have been solving it for a long time ) after a long struggle of 20-30 minutes or 1 hour. But you are unable to solve it, you are exhausted, frustrated and hence given up the solving of Rubik's Cube using legal moves. You will now try your illegal moves. You will take all the pieces apart and reassemble them into a solved Cube.

Reason For Your Failure

Your failure does not means that you may have forgotten solving the Cube, but there may be other reasons behind the scene. You may be suprised to know that if you separate all the cubies and randomly recombine them to make a Cube, then this Cube is not guaranteed to get solved by using legal moves.

Approaches to Understand Rubik's Cube Solvability

There are 2 approaches to understand the Rubik's Cube solvability:

1) Solvability Understanding Using A Solved Cube 2) Solvability Understanding Using Parity Tests


To better understand the solvability of the Rubik's Cube , lets first start from an already solved Cube.

Solvability Understanding Using A Solved Cube

Case 1: Twist a corner

Suppose, you are holding a solved Cube. Now, pick a corner and twist it clockwise (or anticlockwise) by 120 degree (by removing it out and rotate by 120 degree and put it again in the same place) The cube state so obtained is unsolvable because it is not possible to solve the twisted corner without disturbing the positions of already solved cubies using any legal moves.

Case 2: Flip an edge

Suppose, you are holding a solved Cube. Now pick any edge and flip it (by removing it out, flip and put it again in the same place). The cube state so obtained is unsolvable it is not possible to solve the edge without disturbing the positions of already solved cubies using any legal moves.

Case 3: Swap JUST Two Edges

Suppose, you are holding a solved Cube. Now pick any two edges and just swap them. The cube state so obtained is unsolvable because it is not possible to swap JUST Two Edges without swapping something else as well.

Case 4: Swap JUST Two Corners

Suppose, you are holding a solved Cube. Now pick any two corners and just swap them. The cube state so obtained unsolvable because it is not possible to swap JUST Two Corners without something else being swapped as well.

From the first method, we get only some idea of what can be the unsolvable states of a Rubik's Cube, but it does not tells us that if we are given an unsolved Rubik's Cube, then how to determine whether it is solvable or not. To understand this, we requires the second method which is Parity Test.

Solvability Understanding Using Parity Tests

For a 3x3x3, we can determine whether its solvability by using 3 types of Parity Checking: 1) Permutation Parity Test 2) Corner-Orientation Parity Test 3) Edge-Orientation Parity Test

Permutation Parity Test

Consider the list of numbers A: 1 , 2 , 3 , 4 , 5 ( list A)

Now, we rearrange the numbers to get a new list B : 2 , 4 , 1 , 3 , 5

Now, how will you find the minimum number of swaps required among the elements of list B to convert it into the list A. We can do this by finding the number of inversions among the elements of the list B. So, let us first understand what is inversion.

Inversion: Pair (a,b) where a and b are elements of a list forms an inversion if b>a but the b is positioned earlier than a.

So, there are total 3 inversions in the above list B. They are (1,2), (1,4) , (3,4)

3 inversions means that we require 3 swaps in list B to get back to list A. These three swaps are (1,4) , (1,2) and (3,4) respectively.

Every cube state reachable by legal moves requires even number of swaps.


Visualization of the rotation of the face

A cube state is said to pass the Permutation Parity Test, if the total number of swaps in that state is even. It means that the total number of corner swaps and the total number of edge swaps are both either even or both odd.

In order to check for the Permutation Parity Test, first assign unique numbers to all the 20 non-center cubies. Now,we can write four sequences:two for corners and two for edges.

a) Corner sequences: The length of these sequence will be 8 in worst case, since there are 8 corner pieces in a Cube. Sequence A consists of the current positions of the corners. Sequence B consists of the positions where the corners are ought to be in a solved Cube.

Let, n1 = Number of inversions in list B

b) Edge sequences: The length of these sequence will be 12 in worst, since there are 12 edge pieces in a Cube.

Sequence C consists of the current positions of the edges. Sequence D consists of the positions where the edges are ought to be in a solved Cube.

n2 = Number of inversions in sequence D

So, Total number of inversions, n = n1+n2

if n = even , then the Cube state passes the permutation parity test if n=odd, then the Cube state fails the permutation parity test and hence the Cube state is unsolvable. Example: Consider a Cube in the initial state as

Rotate the upper face anticlockwise by 90 degree to make the cube look like the figure :

Since, there is no change in other cubies other than that of upper face, we will only consider the swaps among the upper face cubies in determining whether it will pass the permutation parity test or not. Imagine that we are seeing from the top of the cube, then the changes in the state of upper face will look like this:

Corners C1 C2 C3 C4
Initial State 1 2 3 4
Finale State 4 1 2 3

Total number of inversions for corners are 3 : (2,4), (3,4) , (1,4)


Edges E1 E2 E3 E4
Initial State 1 2 3 4
Finale State 4 1 2 3

Total number of inversions for edges are also 3 : (2,4), (3,4) , (1,4)

Hence, total number of swaps = total number of inversions = 3+3 = 6 which is even Therefore, our initial Cube state passes the Permutation Parity Test.

Corner Parity Test

There are 8 corners in a Rubik's Cube and since each corner will belong either to the top face or the bottom, it will have one of its three stickers matching with the color of the top face or the bottom face.

Since, there are three stickers in a corner, it means that it can be three possible orientations.

Correctly-oriented: Let the color of the top face be X and the color of the bottom face be Y. A corner is said to be correctly-oriented if its X or Y color is facing either up or down, otherwise it is not correctly -oriented.

Now, we will assign some values to the orientations of a corner.

Let C be a corner, 'a' denotes that the corner is oriented correctly 'b' denotes that the corner is oriented clockwise 'c' denotes that the corner is oriented anti-clockwise.


Let, V(C, O) = value of corner C in orientation O

Therefore, V(C , a) = 0 V(C , b) = 1 V(C , c) = 2

A Rubik's Cube state is said to pass the Corner-Parity Test, if the sum of the values of all the corner-orientations in that state is completely divisible by 3.

hello world

Example: In this figure, only one corner is oriented and it is oriented in the clockwise direction.We know that V(C,b)=1 and and 1 is not divisible by 3. So, it fails the corner-parity test and hence the given Cubic state is not solvable.

It should be noted that the rotation of top and bottom faces do not affect the orientation of the corners and hence do no affect the values of the corner-orientation and thus do not affect the solvability of the Rubik's Cube.

But, if the other four slices Front, Back, Left and Right are rotated by 90 degrees, then they will cause two corners to be rotated clockwise and two corners to be rotated anti-clockwise.

So, the total change in the corner-orientation value, d = 2*V(C,b) + 28V(C,c) = 2*1+2*2 = 6 And since d is divisible by 3, therefore the legal moves changes one solvable state to another solvable state.


Edge Parity Test

Correctly-oriented edge: An edge in any position is said to be correctly-oriented if by using rotations of only four faces LEFT, RIGHT, TOP and BOTTOM, we can get into the correct position. If after applying such rotations, we get the edge flipped, then the edge is not correctly-oriented.

It should be noted that rotation of the above four faces does not change the orientation of the edges. But, we have two more faces. They are FRONT and BACK. Rotation of these two faces by 90 degrees, flips all the four edges on that face.

Let, E denotes the edge in consideration 'd' denotes that the edge is correctly-oriented 'e' denotes that the edge is not correctly-oriented V(E,o) = value of Edge E in orientation o


We have, V(E, d) = 0 V(E, e) = 1

Now, A Rubik's Cube state is said to pass the Edge-Parity Test if the value of all the Edge-orientations is even.

Since, LEFT, RIGHT, TOP and BOTTOM flips zero edges while rotation of FRONT and BACK by 90 degrees flips 4 edges. So, any legal move will change the edge-orientation value only by an even number which is divisible by 2. Hence, a legal move will change the Rubik's Cube state from one solvable state to another solvable state and from one unsolvable state to another unsolvable state.

How to compute edge-orientation?

Since, there are 20 edges in a Rubik's Cube. We can check one by one for all the 20 edges by the following procedure. a) Pick an edge and initialize n=0.

b) Try to bring the edge in the position where it ought to be in a solved Cube by using only four faces LEFT, RIGHT, TOP and BOTTOM and also take notes of the moves you make.

c) When the edge is in the correct position, check whether the edge is correctly-oriented or not. If the edge is not correctly-oriented, then increment the value of n by 1, else move to the next step.

d) Using your notes, reverse the moves. After applying the algorithm, check whether all the 20 edges have been checked. If yes, then go to step e) else go to step a).

e) Check whether n=total number of flips is divisible by 2 or not. If yes, then the Cube state passes the Edge-Parity-Test, otherwise it fails and we can say that this Cube-State is not solvable.

Rubik's Cube Solvability:

If the given Rubik's Cubic State passes all the 3 Parity Tests, then we can say that the Cube is solvable else it is unsolvable.

Some RapidFire Examples:


Examples Permutation Parity Test Corner Parity Test Edge Parity Test
1 Fail Fail Fail
2 Pass Fail Pass
3 Pass Pass Fail
4 Fail Pass Fail
5 Fail Fail Pass
6 Pass Pass Pass
7 Fail Pass Pass
8 Pass Fail Fail
9 Pass Pass Pass


Beware Of Broken Cube

We have heard “Beware of Dogs” in our everyday life, but if you are a Rubik Cube solver then you must be “Beware of Broken Cube”. The reason is that if by chance all the cubies gets separated, then after recombining them, then there is only a 1 in 12 chances that you will be able to solve it. So, for most of newbies it will be, “Broken Cube, Broken Heart”.

From the Permutation Parity Test, we find that only even permutations passes this test. Also, since half of the total permutations are even and the rest half are odd, it means that only half of the permutation passes this test.

From the Corner Parity Test, we find that each corner has only 3 possible orientations at any given position. Also, only those Cubis states whose corner-orientation value is divisible by 3 passes the test, it means that only one-third of all the possible corner-orientations passes this test.

From the Edge-Parity Test, we find that each edge has only 2 possible orientations at any given position. Also, we know that any face-rotation changes the edge-orientation value by an even number, it means that if we flip an edge at its given position then it will change the edge-orientation value either from odd to even or even to odd. Therefore, only half of all the possible edge-orientations passes the test.


Hence, the total number of Solvable Rubik Cube states = (1/2)*(1/3)*(1/2)*(Total possible states) = (Total possible states)/12

Probability that a random Cubic State is solvable = 1/12

Trick To Solve An Unsolvable Cube!!!

Please don't disclose this trick and keep it with yourself. The trick is that we can remove the cubies apart and recombine in such a way that the cube is solved. But, these are all illegal moves!!!!

References