Detailed mathematical approach

Problem Summary

Project Euler 185 asks for a 16-digit secret code consistent with 22 clues. Each clue is another 16-digit string together with a number telling us how many positions are exact matches. Digits may repeat, and only digit-and-position matches matter; a correct digit in the wrong place gives no credit. One of the clues already says that 2321386104303845 has 0 correct positions, so the search begins with one forbidden digit at every position.

Brute force would mean checking up to \(10^{16}\) possible codes. The implementations avoid that by turning the puzzle into a small but rigid system of exact-match equations and then solving it with propagation plus a carefully chosen depth-first search.

Mathematical Approach

Let the unknown secret be \(x=(x_1,\dots,x_{16})\), where each \(x_i\in\{0,\dots,9\}\). For the \(t\)-th clue, write the guessed digits as \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\) and its required number of exact matches as \(m_t\). Every clue imposes the equation

$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$

Equivalently, the Hamming distance between the secret and clue \(t\) is \(16-m_t\). The search does not guess complete codes; it maintains partial information about these 22 equations and keeps only states that can still satisfy all of them simultaneously.

Allowed digits at each position

At any stage, position \(i\) carries a current allowed set \(A_i\subseteq\{0,\dots,9\}\). If \(A_i=\{d\}\), then the digit at that position is already forced to be \(d\). If \(|A_i|\gt 1\), the position is still undecided.

This is the right state space for Number Mind because every clue talks about a specific digit at a specific position. The zero-match clue is therefore immediate information: if \(m_t=0\), then for every position \(i\) the digit \(g_i^{(t)}\) is removed from \(A_i\). In the full puzzle this single row already performs 16 bans before any branching happens.

Feasibility bounds for a partial state

Fix one clue \(t\). From the current sets \(A_i\), define

$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$

Here \(f_t\) counts positions already forced to match clue \(t\), while \(c_t\) counts undecided positions that could still match it. Any completion of the current state must satisfy the invariant

$f_t\le m_t\le f_t+c_t.$

If \(f_t\gt m_t\), we have already matched the clue too often. If \(f_t+c_t\lt m_t\), even making every remaining candidate match would not be enough. Either way the branch is impossible and can be pruned immediately. This inequality is the central mathematical test used throughout the search.

Forced consequences of the bounds

The same bound yields strong deterministic moves. If \(f_t=m_t\), then clue \(t\) has already used up all of its allowed matches, so every other candidate position for that clue must become a mismatch and the digit \(g_i^{(t)}\) can be deleted from \(A_i\).

If instead \(f_t+c_t=m_t\), then every position that can still match clue \(t\) must in fact match it, so all those positions are forced to their clue digits. There is also a purely positional consequence: if some \(A_i\) shrinks to size 1, that digit is fixed immediately. Repeating these implications is exactly what makes propagation powerful on this puzzle.

Why the branching is done by clue subsets

For clue \(t\), let

$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$

Any valid completion must choose exactly \(r_t\) positions from \(C_t\) that will match clue \(t\); all remaining positions in \(C_t\) must fail to match it. So the clue naturally induces

$\binom{|C_t|}{r_t}$

possible subsets. This is much sharper than branching digit-by-digit, because one branch decision can simultaneously create several equalities and several inequalities.

The search therefore chooses the clue with the smallest binomial branching factor. Once a subset \(S\subseteq C_t\) with \(|S|=r_t\) is selected, positions in \(S\) are forced to equal their clue digits, and positions in \(C_t\setminus S\) are forbidden from taking those digits. After that, feasibility and singleton propagation are run again.

Worked example: the five-digit sample puzzle

The five-digit sample has clues 90342 with 2 exact matches, 70794 with 0, 39458 with 2, 34109 with 1, 51545 with 2, and 12531 with 1. The zero-match clue 70794 immediately forbids 7 at positions 1 and 3, 0 at position 2, 9 at position 4, and 4 at position 5.

Now inspect the clue 90342 with target 2. Because position 2 can no longer be 0, only positions \(1,3,4,5\) can still match that clue, so \(|C_t|=4\) and the branching count is \(\binom{4}{2}=6\). By contrast, the clue 34109 with target 1 still has five candidate positions, so its branching count is \(\binom{5}{1}=5\). That is slightly smaller, so it is the better clue to branch on first.

Continuing this exact logic yields the unique sample secret \(39542\). Checking it against the six sample clues gives match counts \(2,0,2,1,2,1\), so the sample is a complete small-scale version of the full 16-digit search.

How the Code Works

State representation and preprocessing

The C++, Python, and Java implementations store a partial 16-digit assignment together with a 16 by 10 table of forbidden digits. Clues are sorted by their target match counts, so the most restrictive rows, especially the zero-match row and the one-match rows, are examined early. Before recursion begins, every zero-match clue is applied as an immediate position-wise ban.

Propagation and feasibility checks

Each recursive call first propagates singleton positions: whenever only one digit remains allowed at a position, that digit is fixed. Then every clue is rescanned to recompute the current values of \(f_t\) and \(c_t\). If any clue violates \(f_t\le m_t\le f_t+c_t\), the branch is abandoned at once.

The saturated cases \(r_t=0\) and \(r_t=|C_t|\) are especially strong. They mean a clue has no freedom left: either all of its remaining candidates must be mismatches or all of them must be matches. One of the implementations applies the first case explicitly as an extra propagation pass, while the common search logic handles both cases naturally because they create only one possible subset branch.

Choosing the branch and certifying the solution

If the state is still incomplete, the implementation computes \(\binom{|C_t|}{r_t}\) for every clue and branches on the smallest value. A branch is not a raw digit guess; it decides exactly which positions of one clue are the remaining matches. That usually changes several positions at once and triggers more propagation immediately afterward.

When all 16 positions are fixed, the resulting code is checked against all 22 exact-match counts. The instance is known to have a unique solution, and the search is structured to make that visible: the C++ implementation explicitly continues until a second solution would be found, while the others stop after the first consistent completion on this unique-solution input.

Complexity Analysis

In the worst case this remains an exponential backtracking problem: arbitrary exact-match clue systems do not come with a polynomial-time guarantee, and the naive space starts at \(10^{16}\) possible codes. The algorithm becomes practical because it cuts away most of that space long before full assignments are formed.

For this specific puzzle, each node of the search tree is cheap. There are only \(G=22\) clues and \(L=16\) positions, so a full feasibility scan costs \(O(GL)\), which here is just a small constant-size table scan. The expensive part is the number of recursive states, but zero-match preprocessing, singleton propagation, feasibility bounds, and the minimum-\(\binom{|C_t|}{r_t}\) branching rule collapse the tree dramatically.

Memory use is modest. One active recursive path stores the partial assignment and the forbidden-digit table, so the working state is \(O(16\cdot 10)\), plus recursion depth at most 16. In practice the solver succeeds because it reasons about whole clue rows at once instead of exploring codes digit-by-digit.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=185
2. Mastermind and exact-position clue puzzles: Wikipedia - Mastermind
3. Hamming distance: Wikipedia - Hamming distance
4. Constraint satisfaction problem: Wikipedia - Constraint satisfaction problem
5. Backtracking: Wikipedia - Backtracking
6. Binomial coefficient: Wikipedia - Binomial coefficient