Solution for the famous Instant Insanity problem

INSTANT INSANITY

Q. You have four colored cubes. Each side of each cube is a single color, and there are four colors: blue (B), red (R), green (G) and yellow (Y) Describing the six faces as front, back, left, right, top, bottom, the cube colors are:

Cube	Front	Back	Left	Right	Top	Bottom
1	R	B	G	Y	B	Y
2	R	G	G	Y	B	B
3	Y	B	R	G	Y	R
4	Y	G	B	R	R	R

The objective is to find ways to stack the four cubes as a vertical column so that each side of the column is showing all four colors. 

ANSWER:

1.      Initial estimate of time required for the task:

As per the requirement we need to find ways to stack the four cubes as a vertical column so that each side of the column is showing all the four colors. Now to find the answer we need to try all the possible ways in which a cube can be placed. As we know there are 24 orientations of each cube (A cube can placed with each of the 6 faces pointing up and for each of these rotate the 4 vertical faces left, front, right and back to the front. The product 6x4 is the number of possible orientations for that cube). Now since there are 4 cubes so total arrangements to check would be 24⁴. Also the cubes can also be stacked in any order giving us 4! Thus the arrangements will be (4! * 24⁴)

2.      Actual time taken for the task:

Given this problem we can easily find out the solution using the computer. However it would be really difficult to try out in reality (to find without the aid of computer). In reality we can find out distinct positions for finding the solutions. Given the cube order, the order of the cubes will not matter. Also the solved puzzle will have 8 orientations as a whole. If we carefully observe the output (output of the program submitted), we can say that there could be one unique solution. How? For the first placed cube, we don't need to check all 24 orientations because any solution would appear 8 times. Why? Since rotating the solution with each of the 4 faces pointing to the front would represent 4 solutions and inverting the stack (the order still remains the same) and then rotating it would produce 4 more solutions. So for the first cube, we can place one face of each of the 3 axes facing up, skipping the other 21 possible orientations. The other three cubes must be checked for all 24 orientations, so the total number of arrangements to check is 3 x 24 x 24 x24 = 41,472. This will give us one solution as shown in the figure 1 (Note: This one solution can be represented in 8 different ways as explained above. Moreover these 8 solutions can be arranged in 24 different ways by changing the order of the 4 cubes.)

Cube	Front	Left	Right	Back
1	R	B	Y	B
2	G	Y	G	R
3	B	G	R	Y
4	Y	R	B	G

FIGURE 1.

Solving 41,472 arrangements (without the aid of computer) would be impractical. Let's try a more efficient way to solve this problem and try to get the solution instantly. This can be done using Graph Theory. Let's see how it is done!

Graph Theoretical Representation

The following steps describe how the colored faces of the cubes can be represented in a graph format to solve the problem very efficiently.

1.      A cube is unfolded and its different sides are described as shown in the figure below.

	BACK
LEFT	TOP	RIGHT
	FRONT
	BOTTOM

                                                          FIGURE 2.

2.      The unfolded version of the four cubes given in the problem is shown below in the figure 3.

FIGURE 3.

3.      Now, we start representing each cube by a graph of the colors that appear on opposite pairs of the faces (as shown in the figure 4).

·         Four nodes stand for the four colors (blue B, red R, green G, and yellow Y) of the problem.

·         Edges are the links between the nodes corresponding to two colors on opposite faces.

·         If a pair of opposite sides has the same color, we draw a loop connecting the node to itself.

·         Because a cube has three pairs of opposite faces, the graph representation for each cube has three edges linking the four nodes, one for each color.

FIGURE 4.

4.      Next step is to combine the four graphs into one representation (as shown in figure 5). This representation shows the color relationship of the 12 pairs of opposite faces of the four cubes. Since as described in the problem that cubes must be arranged in stack eight of the 12 numbered edges give you the colors of each of the column's four sides.  Thus we are neglecting the 4 edges i.e. top and bottom.

                        FIGURE 5.

5.      Next step is to find two sub-graphs from the figure 5. such that each sub-graph use all the four nodes just once and includes all the four edges numbered from 1 to 4. Also, while choosing the sub-graph we need to take care that each node would have only two edges.  These conditions would provide us two sub-graphs with one representing the four front-back pairings, and other representing the four left-right parings. Thus, we are looking for two cycles C1 and C2 which each use all of the cubes (1- 4) and the edges between the same two colors come from different cubes.  For example, on one cycle, if the edge connecting R and G is (1), the label connecting R and G on the other cycle must be different than (1). The two sub-graphs are shown below in figure 6.

FIGURE 6.

6.      Now that we have these two sub-graphs we can arrange the cubes and solve the problem. First we have to look for the edge in the first labeled (1).  Look at the endpoints of this edge. Suppose we go from color Red (R) to color Blue (B) by travelling clockwise along this edge. Stack your first cube so that Red is in front and Blue is in back.  Now, look at the second sub-graph and find edge (1) and note its endpoints Blue and Yellow (Y), so that we travel from Blue, clockwise across edge (1) to Yellow.  Put color Blue at the left and Yellow on the right.  Now, proceed in the same fashion with cubes 2-4.

So we have:

Cube	Front	Left	Right	Back
1	R	B	Y	B
2	G	Y	G	R
3	B	G	R	Y
4	Y	R	B	G

 Thus using Graph theory we can get the unique answer very easily.

3.      Source code of solution:

I have written a code (Cube.java) that successfully finds all the possible ways in which the cubes can be placed to get the required output. Cube.java takes advantage of the computer's speed to check all the (4!*24⁴) arrangements for finding out all the possible solutions with all possible arrangements. For a particular order of cubes we have 8 solutions. Since we can arrange cube in 4! =24 ways, thus the possible ways in which we can arrange the cubes= 192.

OUTPUT:

               Front   Left     Right   Back

Cube 1:   R         B        Y        B

Cube 2:   G         Y        G        R

Cube 3:   B         G        R        Y 

Cube 4:   Y         R        B        G