Abstract Confusions

Complexity is not a cause of confusion. It is a result of it.

Instant Insanity – A Graph Theoretic Wonder

Instant insanity is one the many games involving sound mathematical principles. In particular it involves graph theory to solve. One of the mathematics most powerful tool – representation theory is used. As you are aware of, what looks like a strange problem is transformed into totally a unrelated problem in another field because of the hidden relations / transformations. Often these relations transform into a treasure trove of knowledge and excitement.

Instant Insanity – A Game with Cubes

Like the rubik cube, instant insanity is also a game involving cube. You will have four cubes, the six sides of the cubes are colored with four colors (say green, yellow, red and blue). Note, every cube has six faces but only four colors to color them. All four colors will be present in a cube. This means one or two color has to repeat.

image

Now, solution for the puzzle is to arrange all four cubes in a single stack ( 4 \times 1 \times 1 ) with no two colors next to next, i.e., in arranged stack all four colors should be present. The problem looks simple at first, and like anyone else, you will be tempted to use trail and error. The brute force method has close to 41,472 arrangements to try.

Graph Theoretical Representation

To begin the graph theory transformation, let us flatten the cubes into plane and label each cube with familiar 1, 2, 3 and 4.

image

The front and back long sides will be considered as one set, as will the left and right long sides. Since this arrangement is assumed to provide a solution, the set of front and back faces consists of two square faces of each color. If the colors are represented by vertices, and the relationship of “opposite” on a given cube is represented by an edge connecting the vertices representing the opposite colors, the graphical representation is a graph with four vertices and four edges, with multiple edges and loops possibly appearing. One such transformation is given below.

image

Solving Instant Insanity

Once all four cubes are transformed like this, we would have a graph like below. The vertices are already colored, make sure you label the edges with the cube number they belong to. You could see the edges of final graph are labeled as 1, 2, 3 and 4.

image

Now the solution of the puzzle is reduced into a problem of finding a clique in graph, the clique should be a regular graph with degree 2. We would  need to find two such cliques. One for the  arrangement in the front side and one more for back side.

image

Use these two graphs to solve instant insanity. The first sub-graph instructs us how to arrange the first set of opposing faces of the 4 \times 1 \times 1 column. The second sub-graph instructs how to arrange the second column of opposing faces to complete the puzzle.

One response to “Instant Insanity – A Graph Theoretic Wonder

  1. Edward Vogel September 24, 2013 at 6:19 PM

    Could there be a graph theoretic approach to the finding the 240 solutions to the SOMA cube puzzle?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: