TAOCP 7.2.2 Exercise 62
Each cube has six faces colored independently with four colors.
Exercise 62. ▶ [22] When the faces of four cubes are colored randomly with four colors, estimate the probability that the corresponding "Instant Insanity" puzzle has a unique solution. How many 2-regular graphs tend to appear during the "factored" solution process?
Verified: no
Solve time: 3m08s
Solution
Each cube has six faces colored independently with four colors. The faces are grouped into three opposite pairs, so each cube determines three independent ordered color pairs
$$ (u_k^{(1)}, v_k^{(1)}),\ (u_k^{(2)}, v_k^{(2)}),\ (u_k^{(3)}, v_k^{(3)}), \qquad 1 \le k \le 4, $$
each uniformly distributed over ${1,2,3,4}^2$.
A solution of the Instant Insanity puzzle selects, for each cube $k$, exactly one opposite pair to represent the “front-back axis”, one for the “left-right axis”, and one for the “top-bottom axis”. This induces a partition of the three pairs per cube into the three axes, so each cube contributes a bijection between its three pairs and the set of axes. The number of such bijections is $3! = 6$, hence the number of global factorizations is
$$ 6^4 = 1296. $$
Fix one such factorization and consider a single axis, say the first. For each cube $k$, the selected opposite pair contributes one visible face to that axis column. Conditional on the chosen pair $(u_k^{(1)}, v_k^{(1)})$, the visible color is equally likely to be either endpoint, hence uniformly distributed over ${1,2,3,4}$. Independence across cubes follows from independence of face colorings. The axis therefore induces four independent uniform colors.
The axis constraint requires these four colors to be all distinct. The number of favorable 4-tuples is $4!$, and the total number of 4-tuples is $4^4$, hence
$$ \Pr(\text{axis is valid}) = \frac{4!}{4^4} = \frac{24}{256} = \frac{3}{32}. $$
The three axes are independent under a fixed factorization, since they depend on disjoint face pairs. Therefore the probability that a fixed factorization yields a valid full solution is
$$ \left(\frac{3}{32}\right)^3 = \frac{27}{32768}. $$
Let $X$ denote the number of valid factorizations. Linearity of expectation gives
$$ \mathbb{E}[X] = 1296 \cdot \frac{27}{32768}. $$
Since $1296 = 6^4 = (2 \cdot 3)^4 = 2^4 \cdot 3^4 = 16 \cdot 81$, this becomes
$$ \mathbb{E}[X] = 16 \cdot 81 \cdot \frac{27}{32768} = \frac{16 \cdot 2187}{32768} = \frac{34992}{32768}. $$
Division yields
$$ \frac{34992}{32768} = 1 + \frac{2224}{32768} \approx 1.067871. $$
A standard Poisson approximation applies because the 1296 factorizations are sparse in the configuration space of independent random colorings. With mean $\lambda \approx 1.067871$, the probability of exactly one solution is
$$ \Pr(X=1) \approx \lambda e^{-\lambda}. $$
Substitution gives
$$ \Pr(X=1) \approx 1.067871 \cdot e^{-1.067871}. $$
Since $e^{-1.067871} \approx 0.3430$, this yields
$$ \Pr(X=1) \approx 0.366. $$
Thus the probability that a random instance has a unique solution is
$$ \boxed{0.37 \text{ (approximately)}}. $$
For the “factored” solution process, each axis corresponds to a spanning assignment selecting one face pair per cube, and the induced structure on the four cube positions is a 2-regular graph: every cube participates in exactly two adjacency constraints (its two remaining axes), forcing degree 2 at each vertex when projected onto a single axis constraint graph. On four vertices, every 2-regular graph is a single 4-cycle, of which there are exactly $3$ labeled realizations.
Since the construction produces one such 2-regular graph per axis, the process generates
$$ \boxed{3} $$
2-regular graphs in total, each corresponding to one axis constraint. This completes the derivation. ∎