The last problem in the “Games and Puzzles” section comes from a commercial puzzle (though one based on a much older puzzle). It’s cool how these sorts of things pop up- a toy or game comes out and then people analyze it mathematically and find some neat features about it.

**The problem: **Generalized Instant Insanity. This is problem GP15 in the appendix.

**The description: **Given a set Q of cubes, and a set C of colors we paint on the sides of each cube (and where |Q| = |C|) is there a way to arrange the cubes in a stack such that each color in C appears exactly once on each side?

**Example: **The Wikipedia page for the Instant Insanity game has a good description of the game and an example of the solution when Q = 4.

**Reduction: **Roberson and Munro reduce from “Exact Cover”. I don’t think I’ve done this problem, but it’s basically X3C where the sizes of the sets can be any size. (So it’s a trivial reduction from X3C).

They start by designing a graph representation of the puzzle, similar to the one shown on the Wikipedia page. Vertices correspond to colors, an edge connects two vertices if they are on opposite sides of the came cube, and the edges are labeled with the name of the cube. The puzzle has a solution if and only if we can find two edge disjoint cycles that touch each vertex and edge label exactly once. The two cycles correspond to the two sets of opposite faces we can see (since 2 sides of each cube are hidden by the stack). Again, go look at the graphs in the Wikipedia article– they show this pretty nicely.

So, to perform the reduction, we’re given a set S {s_{1}..s_{m}} and a collection T of subsets of S, and need to make a graph (which corresponds to a puzzle). Each element in S will become a vertex in the graph. Each of these vertices will have a self-loop and be labeled ζ_{i} (So each vertex is a different color, and each self-loop is part of a different cube- so each cube has one color on opposite sides).

Each element s_{i} inside a set T_{h} of T will also have a vertex: v_{i,h}. This vertex has an edge with the next largest level s_{j} within T_{h}, wrapping around if we’re at the last element of T_{h}. These edges are labeled ϒ_{h,j}. We also have an edge from s_{j}to v_{h,j} if s_{j} is in T_{h} labeled with δ_{h,j}. We also have 2 copies of self-loops from each v_{h,j} to itself labeled ϒ_{h,j}.

They then add some extra edges to give the graph the properties:

- One of the self-loops from v
_{h,i}to itself has to be in one of the two cycle sets. - If the edge from v
_{h,i}to s_{j}(labeled ϒ_{h,j}) is in the other cycle set, then the edge from s_{j}to v_{h,j}(labeled δ_{h,j}) is also in that cycle set - The ζ
_{i}edge label has to be used, and so will have to be used on an s_{i}vertex the cycle that uses that vertex will also have to have the labels ϒ_{h,j}and δ_{h,j}for some h. - The loops (labeled ζ
_{j}and ϒ_{h,j}) are in one cycle set and the paths (labeled ϒ_{h,j}and δ_{h,j}) are in the other.

With these properties, then solving the puzzle means we have to find h_{1} through h_{m} that correspond to sets T_{h} in T, but also where there is a path ϒ_{h,j}.δ_{h,j} in the graph for each s_{j} in T_{h_i}. We make sure no elements in S are repeated by making sure the puzzle only uses each s_{j} vertex once.

**Difficulty: **8. I glossed over a lot of the construction, especially the definition of a “p-selector”, which is a subgraph that helps set up a lot of the properties above. That definition is very hard for me to follow.