Detailed mathematical approach

Problem Summary

We have an \(x\times y\times z\) rectangular box filled with \(xyz\) identical dice. Each die may be rotated, and whenever two cells share a face, the two touching labels must be equal. If \(f(x,y,z)\) is the number of possible global arrangements, the examples are \(f(1,1,1)=24\) and \(f(2,3,4)=18432\). The target is \(f(9,10,11)\).

Mathematical Approach

The important observation is that a die orientation is not an arbitrary assignment of six labels. A cube has three pairs of opposite faces. Ignoring the signs within each opposite pair, an orientation first assigns these three opposite-face pairs to the three coordinate directions of the box. Then it chooses which member of each pair faces the positive direction. This separates the count into an unsigned skeleton count and a signed orientation count.

Represent the three opposite-face pairs by \(A,B,C\). At a cell \((i,j,k)\), let \(X(i,j,k)\), \(Y(i,j,k)\), and \(Z(i,j,k)\) be the opposite-face pair used by the faces perpendicular to the \(x\)-, \(y\)-, and \(z\)-axis. In every cell these three values must be a permutation of \(A,B,C\). If two neighboring dice touch across an \(x\)-face, both touching labels belong to the same opposite-face pair, so the \(x\)-pair is constant along each \(x\)-line. Therefore

\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]

The local condition \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) has a strong consequence: in any valid unsigned skeleton, at least one box direction carries a globally fixed opposite-face pair. To see why, suppose \(X\) takes two different values in a fixed \(k\)-slice as \(j\) varies. Then \(Y_{i,k}\) is forced to be the third value for every \(i\), and the corresponding \(Z\)-entries are forced as well. Repeating this argument through the rectangular grid propagates the forced pair assignment. If no direction were globally fixed, two such forced propagations would conflict on a rectangle. Thus every skeleton is of one of three types: the \(x\)-direction is globally fixed, or the \(y\)-direction is globally fixed, or the \(z\)-direction is globally fixed.

Count the skeletons of the first type. Choose the fixed opposite-face pair for the \(x\)-direction in \(3\) ways. For each \(x\)-coordinate \(i\), the remaining two pairs can be assigned to the \(y\)- and \(z\)-directions in either order, independently. This gives \(3\cdot 2^x\) skeletons. Similarly the other two types contribute \(3\cdot 2^y\) and \(3\cdot 2^z\).

However, the six completely constant skeletons, one for each global permutation of \(A,B,C\) onto the coordinate axes, have been counted in all three types. They should be counted once, not three times. Hence the unsigned count is

\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]

Now fix one unsigned skeleton and count the signs. For each line parallel to the \(x\)-axis, choose a sign variable \(a_{j,k}\); for each \(y\)-line choose \(b_{i,k}\); for each \(z\)-line choose \(c_{i,j}\). Moving one step along a coordinate axis flips the sign of that axis because the positive face of one die must equal the negative face of the next. The remaining condition is that the signed permutation at every cell is an actual cube rotation, i.e. it has determinant \(+1\). In sign variables this has the form

\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}, \]

where \(r_{i,j,k}\in\{\pm1\}\) is already determined by the unsigned skeleton and coordinate parity.

The number of solutions does not depend on the particular right-hand side. In additive notation over \(\mathbb F_2\), the homogeneous system is

\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]

Every homogeneous solution is

\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]

The parameters \(u_0,\ldots,u_{y-1}\), \(v_0,\ldots,v_{x-1}\), and \(w_0,\ldots,w_{z-1}\) have one global redundancy, so there are \(x+y+z-1\) independent sign bits. Thus every unsigned skeleton supports exactly

\[ 2^{x+y+z-1} \]

signed arrangements.

Multiplying the two independent factors gives the closed form

\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]

How the Code Works

The production computation only evaluates this formula. The helper routine that generates orientations constructs the \(24\) rotation-preserving signed permutations of the three axes. The brute-force routine is deliberately kept only for small boxes; it checks the formula against direct search for \(1\times1\times2\), \(1\times2\times2\), \(2\times2\times1\), and \(2\times2\times2\). The two stated examples are also asserted before printing the target value.

Complexity Analysis

After the derivation, the target computation is \(O(1)\) time and \(O(1)\) memory: it performs a few shifts and multiplications. The brute-force validator is exponential and is intentionally restricted to tiny boxes; it is not part of the real target computation.

References

• Problem page: Project Euler 997
• Cube rotations as orientation-preserving signed permutation matrices.
• Linear systems over \(\mathbb F_2\) for the sign-counting step.