lxii. Instant Insanity

Problem (Parker Brothers, 1967). Four cubes have faces coloured with four colours. Stack them in a column so that each of the four long sides shows all four colours. There are $24^4=331776$ ways to orient the cubes (41 472 up to rotating the whole column), but a graph turns it into a pencil-and-paper puzzle.

Graph method. Make a multigraph on the colours: for every cube draw its three opposite-face pairs as edges labelled by the cube (a pair of equal colours is a loop). A solution corresponds to two edge-disjoint subgraphs, each using exactly one edge of every cube and having every colour of degree exactly 2 (loops count 2): one for the front/back pair of each cube, one for left/right.

Fact	Value
orientations of one cube	24 (6 choices of the front face $\times$ 4 rotations)
graph choices per cube	6 ordered pairs of opposite-face pairs
$n$ cubes, $n$ colours	same method; deciding solvability is NP-complete (Robertson and Munro, 1978)
if every colour appears exactly 6 times in total	the third (unused) pairs also form a 2-regular subgraph, so solutions come in groups of 3 subgraphs

Example (faces listed as front, back, left, right, top, bottom; opposite pairs are positions 1-2, 3-4, 5-6):

Cube	Faces	Opposite pairs	Front/back pair	Left/right pair
1	R R G R R W	RR, GR, RW	GR	RW
2	W B B B G G	WB, BB, GG	WB	GG
3	W B G G R W	WB, GG, RW	WB	RW
4	W W B B G R	WW, BB, GR	GR	BB

The front/back subgraph is the two 2-cycles G–R (cubes 1, 4) and W–B (cubes 2, 3); orienting them gives fronts G, W, B, R and backs R, B, W, G. The left/right subgraph is the 2-cycle R–W (cubes 1, 3) and the loops G (cube 2) and B (cube 4); lefts R, G, W, B and rights W, G, R, B. This is the only solution up to symmetry.

using Cube = array<int, 6>;                          // front, back, left, right, top, bottom: pairs (0,1), (2,3), (4,5)
 
// Graph method: returns for each cube the opposite pair used as front/back and the one used as left/right,
// or empty if the column cannot show all colours on every side. n cubes, colours 0..n-1.
vector<pair<int, int>> instantInsanity(const vector<Cube>& cubes) {
    int n = sz(cubes);
    auto regular = [&](const vector<int>& pick) {    // every colour has degree 2 in the chosen edges
        vector<int> deg(n, 0);
        for (int i = 0; i < n; i++) deg[cubes[i][2 * pick[i]]]++, deg[cubes[i][2 * pick[i] + 1]]++;
        return count(all(deg), 2) == n;
    };
    vector<vector<int>> factors; vector<int> pick(n);
    for (ll code = 0, tot = llround(pow(3, n)); code < tot; code++) {
        ll c = code; for (int i = 0; i < n; i++) pick[i] = c % 3, c /= 3;
        if (regular(pick)) factors.push_back(pick);
    }
    for (auto& f : factors) for (auto& g : factors) {
        bool disjoint = true; for (int i = 0; i < n; i++) disjoint &= f[i] != g[i];
        if (disjoint) { vector<pair<int, int>> res(n); for (int i = 0; i < n; i++) res[i] = {f[i], g[i]}; return res; }
    }
    return {};
}

Proof: solutions are exactly pairs of disjoint 2-regular subgraphs

Solution $\Rightarrow$ subgraphs. In a solution, the front faces show every colour once and so do the back faces; front and back of a cube are opposite, so the front/back edges (one per cube) give every colour degree exactly $1+1=2$. The same holds for left/right, and the two pairs of a cube are different, so the subgraphs are edge-disjoint.

Subgraphs $\Rightarrow$ solution. A 2-regular multigraph is a disjoint union of cycles (loops and 2-cycles included). Orient each cycle; put the tail colour of each edge on the front of its cube and the head colour on the back. Each colour is the tail of exactly one edge and the head of exactly one, so the fronts show each colour once and so do the backs. Do the same for left/right with the second subgraph. Finally every cube can realise these choices: put the first pair’s axis front-back and the second pair’s axis left-right (possible, since the axes are perpendicular); a half turn about the vertical axis swaps both front/back and left/right, a half turn about the front-back axis swaps only left/right, and a half turn about the left-right axis swaps only front/back, so each of the four required sidings is reachable. The search enumerates all $3^n$ single subgraphs and all pairs of them, so it finds a solution iff one exists. Balanced colours: if each of the 4 colours appears on exactly 6 faces, it has degree 6 in the whole graph (a loop counts 2), so when two disjoint subgraphs give it degree 2 each, the leftover pairs give it degree 2 as well. Checked against brute force over all $24^4$ orientations on random 4-cube instances, and the example above was found by such a search (it has exactly one triple of 2-factors).

Related notes

• Graph Basics and Modeling
• Euler Tours (orienting cycles)
• Exact Cover and Dancing Links