Instant Insanity

Four cubes, each of whose six faces is painted with one of four colours, are given. The solver is asked to stack them on top of one another so that each of the four long sides of the resulting tower shows each of the four colours exactly once. The name Instant Insanity is the 1967 trade name of Parker Brothers for what was previously known as The Tantalizer and, earlier still, the Katzenjammer puzzle. For a commercially reasonable choice of face-colours the puzzle is notoriously difficult by hand — a random stack satisfies the constraint with probability below one in a thousand — but yields immediately to a graph-theoretic argument, and yields even more quickly to a constraint-programming encoding.

Each cube has $24$ rotational orientations, so the brute-force search space is $24^4 = 331\,776$ configurations, a handful of which are valid. Under any reasonable symmetry reduction the search space collapses to a few hundred; under the graph-theoretic formulation it collapses to the problem of finding two edge-disjoint 2-regular subgraphs in a four-vertex multigraph on twelve edges.

Rules and the classical instance

Each cube’s colouring is specified by three pairs of opposite faces. The Parker Brothers instance fixes the four cubes as in Figure 5.1: cube $1$ has opposite-face pairs (green, white), (blue, white), (blue, red); cube $2$ has (blue, blue), (green, white), (red, green); cube $3$ has (red, white), (red, green), (blue, white); and cube $4$ has (red, red), (green, white), (blue, red). Each cube is rendered as a cross-shaped net (top; left, front, right, back; bottom). Opposite faces of the cube correspond to top/bottom, left/right and front/back in the net.

*The four cubes of the classical Instant Insanity instance, shown as cross nets. Opposite faces of each cube sit at top/bottom, left/right and front/back of its net.*

A stack of the four cubes is a choice of one of the twenty-four rotational orientations for each cube, placing them in order $1, 2, 3, 4$ from bottom to top. A stack is a solution if, on each of the four visible sides (front, back, left, right) of the stack, the four colours appear exactly once.

The programming model

The encoding is crisper than one might expect. For each cube we do not need to carry the top and bottom face-colours: they are irrelevant to the stack’s visible sides. It suffices to enumerate the $24$ (front, back, left, right) 4-tuples for each cube and treat them as allowed assignments in a table constraint.

Variables

For each cube $i \in \{1, 2, 3, 4\}$ and each side $s \in \{\mathrm{F}, \mathrm{B}, \mathrm{L}, \mathrm{R}\}$ , introduce an integer variable $c_{i, s} \in \{0, 1, 2, 3\}$ representing the colour (indexed $0$ = red, $1$ = green, $2$ = blue, $3$ = white) of cube $i$ ’s face $s$ .

Per-cube orientation constraint

For each cube $i$ , enumerate the distinct 4-tuples $(c_{i, \mathrm{F}}, c_{i, \mathrm{B}}, c_{i, \mathrm{L}}, c_{i, \mathrm{R}})$ arising over the $24$ rotations and add a table constraint requiring one of them be chosen. In CP-SAT this is $\texttt{AddAllowedAssignments}$ .

Per-side all-different constraint

For each side $s$ , the four visible colours $c_{1, s}, c_{2, s}, c_{3, s}, c_{4, s}$ must be all different: $\operatorname{AllDifferent}(c_{1, s}, c_{2, s}, c_{3, s}, c_{4, s}).$

That is the entire model. No separate variables for the $24$ orientations are needed; the allowed-assignments table projects the rotational freedom onto the four variables that matter.

A solver in forty lines

from ortools.sat.python import cp_model

R, G, B, W = 0, 1, 2, 3
CUBES = [
    [(G,W), (B,W), (B,R)],
    [(B,B), (G,W), (R,G)],
    [(R,W), (R,G), (B,W)],
    [(R,R), (G,W), (B,R)],
]

def orients(cube):
    """24 rotations: (top,bot,left,right,front,back)."""
    (a,b),(c,d),(e,f) = cube
    return [
        (a,b,c,d,e,f),(a,b,e,f,d,c),
        (a,b,d,c,f,e),(a,b,f,e,c,d),
        (b,a,d,c,e,f),(b,a,e,f,c,d),
        (b,a,c,d,f,e),(b,a,f,e,d,c),
        (c,d,b,a,e,f),(c,d,a,b,f,e),
        (c,d,e,f,a,b),(c,d,f,e,b,a),
        (d,c,a,b,e,f),(d,c,e,f,b,a),
        (d,c,b,a,f,e),(d,c,f,e,a,b),
        (e,f,a,b,c,d),(e,f,c,d,b,a),
        (e,f,b,a,d,c),(e,f,d,c,a,b),
        (f,e,d,c,b,a),(f,e,b,a,c,d),
        (f,e,c,d,a,b),(f,e,a,b,d,c),
    ]

def solve():
    m = cp_model.CpModel()
    fr = [m.NewIntVar(0, 3, "") for _ in range(4)]
    bk = [m.NewIntVar(0, 3, "") for _ in range(4)]
    lf = [m.NewIntVar(0, 3, "") for _ in range(4)]
    rg = [m.NewIntVar(0, 3, "") for _ in range(4)]
    for i in range(4):
        seen, tuples = set(), []
        for (t,bo,l,r,f,b) in orients(CUBES[i]):
            tup = (f, b, l, r)
            if tup in seen: continue
            seen.add(tup)
            tuples.append(list(tup))
        m.AddAllowedAssignments(
            [fr[i], bk[i], lf[i], rg[i]], tuples)
    for side in (fr, bk, lf, rg):
        m.AddAllDifferent(side)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [(s.Value(fr[i]), s.Value(bk[i]),
             s.Value(lf[i]), s.Value(rg[i]))
            for i in range(4)]

The model solves in about $20$ milliseconds. The solution found is shown in Figure 5.2: each column is a cube, each row a side.

*A solution. Each column is one cube; each row is one of the four visible sides of the stack (F = front, B = back, L = left, R = right). Each row shows all four colours exactly once.*

The graph-theoretic interpretation

The elegant hand-solvable argument for Instant Insanity, classical since F. de Carteblanche’s Eureka note of $1947$ , runs as follows. Build a multigraph on four vertices (one per colour): R, G, B, W. For each cube, and for each of its three pairs of opposite faces, draw one edge joining the two pair-colours and label it with the cube number. The result is a four-vertex multigraph with exactly twelve labelled edges, three per cube, as in Figure 5.3. Pairs where both opposite faces carry the same colour become self-loops.

The Instant Insanity multigraph. Vertices are the four colours; each cube contributes three edges, one per pair of opposite faces. Edges are coloured by cube and labelled with the cube number; self-loops record pairs of equal colour (here cube $2$ has a blue-blue pair and cube $4$ a red-red pair).

In this multigraph, each orientation of a cube selects one of its three edges as its front-back edge (the pair occupying the front and back faces) and another as its left-right edge (the pair occupying left and right faces). A valid stack therefore corresponds to choosing, from the twelve edges, two edge-disjoint subgraphs $H_{\mathrm{FB}}$ and $H_{\mathrm{LR}}$ such that

each of the four cubes contributes exactly one edge to $H_{\mathrm{FB}}$ and one edge to $H_{\mathrm{LR}}$ ;
in each subgraph, every vertex has degree $2$ (each colour appears exactly twice among the subgraph’s edges — once on the front and once on the back in $H_{\mathrm{FB}}$ , once on the left and once on the right in $H_{\mathrm{LR}}$ ).

Each $H$ is therefore a $2$ -regular spanning subgraph on the four-colour vertex set, i.e. a disjoint union of cycles covering all four vertices. Searching the four-vertex multigraph for two such edge-disjoint $2$ -factors is a matter of moments by hand and is the clean combinatorial core that CP-SAT rediscovers through table constraints and $\operatorname{AllDifferent}$ .

Sources. The puzzle is of late-nineteenth-century origin, popularised in the 1940s as The Tantalizer and marketed by Parker Brothers from 1967 under the trade name Instant Insanity. The graph-theoretic solution was first published by F. de Carteblanche (a collective pseudonym of four Cambridge mathematicians) in Eureka volume 9 ( $1947$ ), pages 9–11, and is the canonical treatment in Wilson’s Introduction to Graph Theory and Gardner’s The Unexpected Hanging. The generalisation to $n$ cubes in $n$ colours is NP-complete (Garey and Johnson, $1979$ , problem GT50), by reduction from not-all-equal 3-SAT; for $n = 4$ the problem remains trivial for CP-SAT, which solves it in a fraction of the time the graph-theoretic argument takes to describe.