Detailed mathematical approach

Problem Summary

We have two cubes, each carrying 6 distinct digits chosen from \(\{0,1,\dots,9\}\). By placing the cubes side by side, we want to display every two-digit square below 100: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).

The cubes are unlabeled, so swapping them does not create a new arrangement. The only geometric subtlety is that a face marked 6 can be turned upside down and read as 9, and the same goes in the other direction. The task is therefore to count all unordered pairs of 6-digit cubes that satisfy those nine display constraints exactly.

Mathematical Approach

The solution is an exact finite count. Once the digit-pair constraints are written correctly, the search space is so small that exhaustive enumeration is already the clean mathematical method.

The state space of possible cubes

Let \(U=\{0,1,\dots,9\}\). A single cube is a subset \(D\subseteq U\) with \(\lvert D\rvert=6\). Hence the number of possible cubes is

$N_{\text{cube}}=\binom{10}{6}=210.$

We do not distinguish the ordered pair \((D_1,D_2)\) from \((D_2,D_1)\), and identical cubes are allowed, so we are counting unordered pairs with repetition. That gives

$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$

That number is tiny: even before any optimization, checking every candidate pair is completely practical.

The 6/9 closure

The implementations treat 6 and 9 as a single rotational class. If a cube contains either one, it can serve as both when we read a square number. It is convenient to encode that by replacing each cube \(D\) with its effective digit set

$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$

This is the only nontrivial invariant in the problem. After taking the closure, every square check is just a membership question in \(\widehat{D}_1\) and \(\widehat{D}_2\).

Turning the squares into formal constraints

Write the required squares as ordered digit pairs

$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$

A pair of cubes is valid exactly when, for every \((a,b)\in P\), one cube can show \(a\) while the other shows \(b\). Because the cubes may be swapped, the condition is

$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$

There is a useful structural simplification. If we collapse 6 and 9 into a single class \(s\), then the distinct unordered requirements become

$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$

So \(49\) and \(64\) are different square numbers, but after the 6/9 rule they impose the same underlying constraint: one cube must contribute 4 and the other must contribute a rotatable 6/9 face. The implementations keep the original list of nine squares, which is perfectly fine because the digit test already merges 6 and 9.

Worked example

Take \(D_1=\{0,1,2,3,4,5\}\) and \(D_2=\{0,1,2,6,7,8\}\). Since \(D_2\) contains 6, its effective set is \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).

Now check the required squares. \(01\) is immediate from \(0\in D_1\) and \(1\in D_2\). \(04\) works after swapping the cubes: use 4 from the first cube and 0 from the second. \(09\) works because the second cube's 6 also acts as 9. \(16\) and \(36\) use the same 6/9 face together with 1 and 3 from the first cube. \(25\) works by taking 2 from the second cube and 5 from the first. Both \(49\) and \(64\) are satisfied by 4 on the first cube and 6/9 on the second. Finally, \(81\) uses 8 from the second cube and 1 from the first. So this pair is valid.

Why exhaustive enumeration is the right method

Nothing in the actual mathematics suggests a deeper recurrence or a closed-form count. Once the problem is reduced to 22155 unordered cube pairs and 9 constant-size tests per pair, an exhaustive count is not a fallback; it is the natural exact solution. The code therefore does the mathematically simplest thing: generate every admissible cube, test every unordered pair, and count the successes.

How the Code Works

Enumerating the candidate cubes

The Python implementation generates all 6-element digit choices directly as combinations. The C++ and Java implementations represent a cube as a 10-bit mask and scan all 1024 masks, keeping exactly those with 6 set bits. Both approaches produce the same 210 candidate cubes.

Testing one unordered pair

After the candidate list is built, the outer loop selects the first cube and the inner loop starts at the same index, so each unordered pair is visited once and identical cube pairs are included. For each pair, the implementation checks the nine required square pairs one by one using the 6/9-aware digit test. The pair is counted only if every square passes.

Representation details

In C++ and Java, digit membership is a bit operation on the mask, with a special case that treats a request for 6 or 9 as “does the mask contain either one?”. In Python, each cube is a fixed-length tuple and membership is tested directly. The representations differ, but the logical predicate is identical in all three languages.

Complexity Analysis

Generating the 210 cubes costs \(O\!\left(\binom{10}{6}\right)\) conceptually, or \(O(2^{10})\) in the bitmask implementations; either way it is tiny. The main work is the unordered pair loop:

$\binom{210+1}{2}=22155$

candidate pairs, with 9 square checks for each one. So the total number of square tests is

$22155\times 9 = 199395.$

That is effectively constant time for this problem. The memory usage is \(O(210)\) for the stored cube list, plus negligible overhead for the fixed square table.

Footnotes and References

1. Problem page: Project Euler 90 - Cube digit pairs
2. Combination: Wikipedia - Combination
3. Binomial coefficient: Wikipedia - Binomial coefficient
4. Multiset: Wikipedia - Multiset
5. Bitwise operation: Wikipedia - Bitwise operation