This post is about a mathematical puzzle and not the current state of daily affairs. The puzzle consists of four cubes, with faces colored in four colors:
If you want to make your own, you can print out the nets below and fold.
The goal is to stack the four cubes together so that each of the four long faces of the 4 x 1 x 1 tower show all four colors.
According to Jerry Slocum, this puzzle goes back to 1900 when Frederick A. Schossow marketed a version of it under the name Katzenjammer Puzzle. Katzenjammer is German for hangover…
It has since appeared in many variations. Its latest incarnation under the current name Instant Insanity was discovered by Frank Armbruster and has been marketed by Parker Brothers since 1967.
We will solve he puzzle using graph theory. Each cube will get encoded in a graph. To do so, we use as vertices the colors (yellow, orange, purple, and green), and connect two colors by an edge if the two colors occur on opposite faces of the cube. Thus we obtain for each colored cube a graph with four vertices (colors) and three edges (opposite faces).
Before we continue, let’s see why these arbitrary looking graphs contains all the information about the cubes that is necessary to play the puzzle: If the graph of a cube is given, we know all colors of pairs of opposite faces for that cube. Using a blank cube, we can first color the front and back face with a pair of these colors. It doesn’t matter which color we pick for the front, because we could turn the cube over. Using a second edge of the graph, we then color the left and right face with the two colors of the end points of the edge. Again it doesn’t matter which color we use for the left side, because there is a rotation fixing front and back that flips left and right. Finally, there are two possibilities remaining for coloring the top and bottom face of the cube. These lead to truly differently colored cubes, but both are equivalent for solving the puzzle, as the top and bottom colors of the tower don’t matter for the puzzle.
Coming back to solving the puzzle, we combine the four graphs we have created for each cube into a single graph with multiple edges. The edges are now labeled from 1 through 4 to indicate from which cube they come. How does this graph help us to solve the puzzle?
Suppose we have stacked the cubes together so that both the front and back side of the tower show all four difference colors. The four front and back sides of each cube represent each an edge in our graph, which we give a direction so that they always point to the color of the back edge. Let’s mark these edges say blue. Thus we get four blue edges that begin at four different colors and end at four different colors. As there are just four colors, each vertex has an edge ending and an edge beginning there. This means that following the blue edges, we have found a doubly Hamiltonian circuit – a cycle or collection of cycles that pass through all four vertices (colors) of the graph, and uses edges with each of the four labels (cubes).
Vice versa, any such path can be used to stack the cubes so that front and back side of the tower show all four colors.
Next we will show that any such system of circuits must go once around the square marked by the four colors.
If this were not the case, it would decompose into several components of lengths 1+3, 1+1+2, or 2+2.
While in each case there are Hamiltonian circuits, none of them are doubly Hamiltonian.
Thus we only need to look for Hamiltonian paths that go around the square, and can ignore the loops at orange and green as well as the diagonal connection from purple to orange.
Consider the top and bottom edge, which both have an edge labeled 4. As each edge label can only occur once, one of these two edges must use an edge with a label other than 4. We make a case distinction: First, let’s assume the bottom edge uses label 3. Necessarily then, the right edge then must use label 2, the left edge label 1, and the top edge label 4, and we get the Hamiltonian path marked red.
Now let’s assume that the top edge is using label 1. Thus we have to use for the left either label 2 or 3, and the other label 3 or two for the right edge. Either choice leaves us with label 4 for the bottom edge. One of the choices is the path marked blue, the other one has labels 2 and 3 exchanged in the left and right connections. Thus there are only three different possible Hamiltonian paths.
To finally solve the puzzle completely, we will need to take care of the left and right faces of our tower. By associating a directed edge for each cube from every left face to every right face, we get a second doubly Hamiltonian path in our graph.
This second path must be edge disjoint with the first, as we cannot use a pair of opposite faces of the same cube twice.
As the second and third of our three Hamiltonian paths are not disjoint, one of the paths we seek must be the red path. This uses edge 2 on the right hand side, so that the second Hamiltonian path can only be the blue one. They are indeed edge disjoint, and thus solve the puzzle.