Problem 997: Dice Box
View on Project EulerProject Euler Problem 997 Solution
EulerSolve provides an optimized solution for Project Euler Problem 997, Dice Box, with C++, Python, Java, and a step-by-step mathematical explanation.
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}....
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.
Problem 997 source code
C++
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
namespace {
using u64 = std::uint64_t;
constexpr int TARGET_X = 9;
constexpr int TARGET_Y = 10;
constexpr int TARGET_Z = 11;
struct Orientation {
std::array<int, 6> face{};
};
u64 pow2(const int exponent) {
assert(0 <= exponent && exponent < 63);
return 1ULL << exponent;
}
u64 f(const int x, const int y, const int z) {
return 3ULL * (pow2(x) + pow2(y) + pow2(z) - 4ULL) * pow2(x + y + z - 1);
}
int parity(const std::array<int, 3>& p) {
int inversions = 0;
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
if (p[i] > p[j]) {
++inversions;
}
}
}
return inversions % 2 == 0 ? 1 : -1;
}
int signed_axis(const int axis, const int sign) {
return 2 * axis + (sign < 0 ? 1 : 0);
}
std::vector<Orientation> orientations() {
std::vector<Orientation> result;
for (int a = 0; a < 3; ++a) {
for (int b = 0; b < 3; ++b) {
for (int c = 0; c < 3; ++c) {
if (a == b || a == c || b == c) {
continue;
}
const std::array<int, 3> perm{a, b, c};
for (int mask = 0; mask < 8; ++mask) {
std::array<int, 3> sign{};
for (int i = 0; i < 3; ++i) {
sign[i] = (mask & (1 << i)) == 0 ? 1 : -1;
}
if (parity(perm) * sign[0] * sign[1] * sign[2] != 1) {
continue;
}
Orientation orientation;
for (int axis = 0; axis < 3; ++axis) {
orientation.face[2 * axis] = signed_axis(perm[axis], sign[axis]);
orientation.face[2 * axis + 1] = signed_axis(perm[axis], -sign[axis]);
}
result.push_back(orientation);
}
}
}
}
return result;
}
u64 brute_count(const int x, const int y, const int z) {
const std::vector<Orientation> all = orientations();
std::vector<std::array<int, 3>> cells;
for (int k = 0; k < z; ++k) {
for (int j = 0; j < y; ++j) {
for (int i = 0; i < x; ++i) {
cells.push_back({i, j, k});
}
}
}
auto index = [=](const int i, const int j, const int k) {
return (k * y + j) * x + i;
};
std::vector<int> grid(static_cast<std::size_t>(x * y * z), -1);
u64 total = 0;
auto search = [&](auto&& self, const int position) -> void {
if (position == static_cast<int>(cells.size())) {
++total;
return;
}
const auto [i, j, k] = cells[static_cast<std::size_t>(position)];
for (int o = 0; o < static_cast<int>(all.size()); ++o) {
const Orientation& current = all[static_cast<std::size_t>(o)];
if (i > 0) {
const Orientation& previous = all[static_cast<std::size_t>(grid[static_cast<std::size_t>(index(i - 1, j, k))])];
if (previous.face[0] != current.face[1]) {
continue;
}
}
if (j > 0) {
const Orientation& previous = all[static_cast<std::size_t>(grid[static_cast<std::size_t>(index(i, j - 1, k))])];
if (previous.face[2] != current.face[3]) {
continue;
}
}
if (k > 0) {
const Orientation& previous = all[static_cast<std::size_t>(grid[static_cast<std::size_t>(index(i, j, k - 1))])];
if (previous.face[4] != current.face[5]) {
continue;
}
}
grid[static_cast<std::size_t>(index(i, j, k))] = o;
self(self, position + 1);
grid[static_cast<std::size_t>(index(i, j, k))] = -1;
}
};
search(search, 0);
return total;
}
void run_checkpoints() {
assert(orientations().size() == 24);
assert(f(1, 1, 1) == 24);
assert(f(2, 3, 4) == 18'432);
assert(f(1, 1, 2) == brute_count(1, 1, 2));
assert(f(1, 2, 2) == brute_count(1, 2, 2));
assert(f(2, 2, 1) == brute_count(2, 2, 1));
assert(f(2, 2, 2) == brute_count(2, 2, 2));
}
} // namespace
int main() {
run_checkpoints();
std::cout << f(TARGET_X, TARGET_Y, TARGET_Z) << '\n';
return 0;
}
Python
from itertools import permutations, product
TARGET_X = 9
TARGET_Y = 10
TARGET_Z = 11
def pow2(exponent):
assert 0 <= exponent < 63
return 1 << exponent
def solve_box(x, y, z):
return 3 * (pow2(x) + pow2(y) + pow2(z) - 4) * pow2(x + y + z - 1)
def parity(perm):
inversions = 0
for i in range(3):
for j in range(i + 1, 3):
if perm[i] > perm[j]:
inversions += 1
return 1 if inversions % 2 == 0 else -1
def signed_axis(axis, sign):
return 2 * axis + (1 if sign < 0 else 0)
def orientations():
result = []
for perm in permutations(range(3)):
for signs in product((1, -1), repeat=3):
if parity(perm) * signs[0] * signs[1] * signs[2] != 1:
continue
face = [0] * 6
for axis in range(3):
face[2 * axis] = signed_axis(perm[axis], signs[axis])
face[2 * axis + 1] = signed_axis(perm[axis], -signs[axis])
result.append(tuple(face))
return result
def brute_count(x, y, z):
all_orientations = orientations()
cells = [(i, j, k) for k in range(z) for j in range(y) for i in range(x)]
grid = [-1] * (x * y * z)
def index(i, j, k):
return (k * y + j) * x + i
def search(position):
if position == len(cells):
return 1
i, j, k = cells[position]
total = 0
for o, current in enumerate(all_orientations):
if i > 0:
previous = all_orientations[grid[index(i - 1, j, k)]]
if previous[0] != current[1]:
continue
if j > 0:
previous = all_orientations[grid[index(i, j - 1, k)]]
if previous[2] != current[3]:
continue
if k > 0:
previous = all_orientations[grid[index(i, j, k - 1)]]
if previous[4] != current[5]:
continue
grid[index(i, j, k)] = o
total += search(position + 1)
grid[index(i, j, k)] = -1
return total
return search(0)
def run_checkpoints():
assert len(orientations()) == 24
assert solve_box(1, 1, 1) == 24
assert solve_box(2, 3, 4) == 18432
assert solve_box(1, 1, 2) == brute_count(1, 1, 2)
assert solve_box(1, 2, 2) == brute_count(1, 2, 2)
assert solve_box(2, 2, 1) == brute_count(2, 2, 1)
assert solve_box(2, 2, 2) == brute_count(2, 2, 2)
def main():
run_checkpoints()
print(solve_box(TARGET_X, TARGET_Y, TARGET_Z))
if __name__ == "__main__":
main()
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Euler997 {
private static final int TARGET_X = 9;
private static final int TARGET_Y = 10;
private static final int TARGET_Z = 11;
private static long pow2(int exponent) {
if (exponent < 0 || exponent >= 63) {
throw new IllegalArgumentException("exponent out of range");
}
return 1L << exponent;
}
private static long solveBox(int x, int y, int z) {
return 3L * (pow2(x) + pow2(y) + pow2(z) - 4L) * pow2(x + y + z - 1);
}
private static int parity(int[] perm) {
int inversions = 0;
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
if (perm[i] > perm[j]) {
++inversions;
}
}
}
return inversions % 2 == 0 ? 1 : -1;
}
private static int signedAxis(int axis, int sign) {
return 2 * axis + (sign < 0 ? 1 : 0);
}
private static List<int[]> orientations() {
List<int[]> result = new ArrayList<>();
for (int a = 0; a < 3; ++a) {
for (int b = 0; b < 3; ++b) {
for (int c = 0; c < 3; ++c) {
if (a == b || a == c || b == c) {
continue;
}
int[] perm = {a, b, c};
for (int mask = 0; mask < 8; ++mask) {
int[] signs = new int[3];
for (int i = 0; i < 3; ++i) {
signs[i] = (mask & (1 << i)) == 0 ? 1 : -1;
}
if (parity(perm) * signs[0] * signs[1] * signs[2] != 1) {
continue;
}
int[] face = new int[6];
for (int axis = 0; axis < 3; ++axis) {
face[2 * axis] = signedAxis(perm[axis], signs[axis]);
face[2 * axis + 1] = signedAxis(perm[axis], -signs[axis]);
}
result.add(face);
}
}
}
}
return result;
}
private static long bruteCount(int x, int y, int z) {
List<int[]> all = orientations();
List<int[]> cells = new ArrayList<>();
for (int k = 0; k < z; ++k) {
for (int j = 0; j < y; ++j) {
for (int i = 0; i < x; ++i) {
cells.add(new int[]{i, j, k});
}
}
}
int[] grid = new int[x * y * z];
Arrays.fill(grid, -1);
return search(0, x, y, cells, all, grid);
}
private static int index(int i, int j, int k, int x, int y) {
return (k * y + j) * x + i;
}
private static long search(int position, int x, int y, List<int[]> cells, List<int[]> all, int[] grid) {
if (position == cells.size()) {
return 1L;
}
int[] cell = cells.get(position);
int i = cell[0];
int j = cell[1];
int k = cell[2];
long total = 0L;
for (int o = 0; o < all.size(); ++o) {
int[] current = all.get(o);
if (i > 0) {
int[] previous = all.get(grid[index(i - 1, j, k, x, y)]);
if (previous[0] != current[1]) {
continue;
}
}
if (j > 0) {
int[] previous = all.get(grid[index(i, j - 1, k, x, y)]);
if (previous[2] != current[3]) {
continue;
}
}
if (k > 0) {
int[] previous = all.get(grid[index(i, j, k - 1, x, y)]);
if (previous[4] != current[5]) {
continue;
}
}
grid[index(i, j, k, x, y)] = o;
total += search(position + 1, x, y, cells, all, grid);
grid[index(i, j, k, x, y)] = -1;
}
return total;
}
private static void runCheckpoints() {
assert orientations().size() == 24;
assert solveBox(1, 1, 1) == 24L;
assert solveBox(2, 3, 4) == 18_432L;
assert solveBox(1, 1, 2) == bruteCount(1, 1, 2);
assert solveBox(1, 2, 2) == bruteCount(1, 2, 2);
assert solveBox(2, 2, 1) == bruteCount(2, 2, 1);
assert solveBox(2, 2, 2) == bruteCount(2, 2, 2);
}
public static void main(String[] args) {
runCheckpoints();
System.out.println(solveBox(TARGET_X, TARGET_Y, TARGET_Z));
}
}