Problem 185: Number Mind

Project Euler Problem 185 Solution

EulerSolve provides an optimized solution for Project Euler Problem 185, Number Mind, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

Number Mind is a variant of Master Mind: a secret sequence of digits has to be found, and after each guess we are told only in how many places the guess has the correct digit. A correct digit in a wrong place earns nothing: for the secret $1234$ the guess $2036$ scores $1$, for the $3$ in the third place, although its $2$ also occurs in the secret. In Master Mind terms, only the black key pegs are reported. ^[2] In the warm-up example, six guesses for a 5-digit secret, $90342$, $70794$, $39458$, $34109$, $51545$ and $12531$ with the scores $2,0,2,1,2,1$, leave $39542$ as the only possibility. The task gives $22$ guesses for a 16-digit secret, with the score $0$ once, $1$ six times, $2$ seven times and $3$ eight times, and asks for the unique 16-digit secret sequence. ^[1]

The whole solution in one sentence: we keep the digits still possible at every place, discard every partial state in which a guess has too many hits or can no longer get enough, and branch on which possible places of one guess are its hits, choosing the guess with the fewest options, so that fewer than $10^5$ states find the secret and prove it unique.

Mathematical Approach

Sections 1–4 derive a pruning test and forced conclusions from the guesses, Sections 5–7 build the search and prove it correct, Section 8 runs it on the warm-up and Section 9 compares other exact methods.

1. Every guess is a counting equation

Write the secret as $x=(x_1,\dots,x_L)$, with $L=16$, or $L=5$ in the warm-up, and guess number $t$ as $g^{(t)}=(g^{(t)}_1,\dots,g^{(t)}_L)$ with score $m_t$. With $[P]$ equal to $1$ when the statement $P$ is true and $0$ otherwise, guess $t$ says

$$\sum_{i=1}^{L}\bigl[x_i=g^{(t)}_i\bigr]=m_t.$$

A guess is thus a list of $L$ statements "place $i$ holds the digit $g_i$", where we drop the index $t$ when the guess is clear, and its score says how many of them are true; equivalently, the Hamming distance of guess and secret is $L-m_t$. ^[3] For example, $39542$ and $90342$ agree in the fourth and fifth places only, a score of $2$. For the warm-up, testing all $10^5$ sequences shows that $39542$ is the only one that fits. For $16$ digits that would take $10^{16}$ tests, and no general shortcut is expected: when the length and the number of symbols may grow, deciding whether such scores admit any secret at all is NP-complete. ^[4] A proposed secret is easy to check, but no method is known that decides every instance in polynomial time.

2. Candidate sets

During the search we keep, for every place $i$, the set $A_i\subseteq\{0,1,\dots,9\}$ of digits still possible there; a sequence fits the state if $x_i\in A_i$ for every $i$. A place is decided when $A_i$ has one element and open when it has at least two; if some $A_i$ is empty, nothing fits. At the start every $A_i$ holds all ten digits. A guess with score $0$ says that none of its statements is true, so it removes $g_i$ from every $A_i$. In the warm-up, $70794$ removes $7$, $0$, $7$, $9$ and $4$ from $A_1,\dots,A_5$ in turn, which leaves $9^5=59049$ sequences. In the main puzzle, $2321386104303845$ removes one digit from each place and leaves $9^{16}\approx1.85\cdot10^{15}$ sequences.

3. Two bounds for every guess

Fix a state and a guess $t$. Let $f_t$ be the number of decided places with $A_i=\{g_i\}$, the sure hits, and let $C_t$ be the set of open places with $g_i\in A_i$, the possible hits, of which there are $c_t=|C_t|$.

Claim. Every sequence that fits the state and gives guess $t$ its score satisfies

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

Proof. A fitting sequence has the digit $g_i$ at each sure hit, so it has at least $f_t$ hits. A hit at place $i$ needs $g_i\in A_i$, which holds only at the sure hits and in $C_t$: a place decided to another digit, or one that has lost $g_i$, cannot be a hit. So there are at most $f_t+c_t$ hits.

A state that violates these bounds for some guess contains no solution and is discarded with everything below it. This is the pruning of backtracking: a partial candidate that cannot be completed is abandoned. ^[5] When every place is decided, $c_t=0$ and the bounds say $f_t=m_t$ for every guess, so the state is a solution.

4. Conclusions without a choice

Let $r_t=m_t-f_t$ be the number of hits that guess $t$ still needs; in a state that passes the test of Section 3, $0\le r_t\le c_t$. The two extreme cases leave no freedom:

if $r_t=0$, every place of $C_t$ must miss, so $g_i$ is removed from $A_i$ for each $i\in C_t$;
if $r_t=c_t$, every possible hit must be a hit, so $A_i$ becomes $\{g_i\}$ for each $i\in C_t$.

Likewise a set $A_i$ with a single element decides place $i$. These conclusions follow from the equations, so they never lose a solution. A guess with $r_t=0$ and $c_t=0$ is settled: it imposes nothing more.

5. Branching on the hits of one guess

If $0\lt r_t\lt c_t$, we do not know which possible hits are the real ones, and we branch. For a solution $x$ that fits the state, let $S(x)=\{i\in C_t: x_i=g_i\}$ be its set of hits inside $C_t$. Outside $C_t$ its hits are exactly the $f_t$ sure hits, so $S(x)$ has exactly $r_t$ elements. For every subset $S\subseteq C_t$ with $r_t$ elements, the branch $S$ sets $A_i=\{g_i\}$ for $i\in S$ and removes $g_i$ from $A_i$ for $i\in C_t\setminus S$.

Claim. Every solution that fits the state fits exactly one branch, namely $S(x)$.

Proof. The solution $x$ fits the branch $S$ exactly when $x_i=g_i$ for $i\in S$ and $x_i\ne g_i$ for $i\in C_t\setminus S$, that is, exactly when $S(x)=S$.

So the branches split the solutions into disjoint groups: none is lost and none is found twice. There are $\binom{c_t}{r_t}$ of them, the number of ways to choose $r_t$ places out of $c_t$. ^[6] Each branch settles guess $t$, deciding $r_t$ places and removing a digit from the $c_t-r_t$ others at once, and the conclusions of Section 4 are the case of a single branch, since $\binom{c}{0}=\binom{c}{c}=1$.

6. Which guess to branch on

By Section 5 any unsettled guess may be chosen; the choice affects only the size of the search. We take one with the fewest branches $\binom{c_t}{r_t}$, the first in the order of increasing score among equal counts: the "fewest alternatives first" rule that Knuth recommends for exact cover. ^[7] Forced conclusions have one branch, so they always come first. At the start of the main puzzle, the six guesses with score $1$ have $13$ to $16$ possible places, and every guess with score $2$ or $3$ has at least $\binom{12}{2}=66$ branches. The guess $8157356344118483$ shares its fifth, seventh and tenth digits with $2321386104303845$, so it has only $13$ possible places, and the search starts with its $13$ branches.

7. Why the search ends, and what it proves

In every branch the chosen guess becomes settled, and it stays settled further down, because the sets only shrink: its sure hits stay decided, and no open place gets its digit back. So no guess is branched on twice along a path, a path has at most $21$ branchings in the main puzzle, one for each guess with a nonzero score, and the search ends. It stops at states of three kinds:

(a) a bound of Section 3 fails or some $A_i$ is empty: no solution;
(b) every place is decided: exactly one solution, by Section 3;
(c) every guess is settled, but some place is still open.

In case (c) every guess has its full score at decided places, and none of its digits is still possible at an open place, so every choice of digits from the open sets gives exactly the required scores, and as open sets have at least two elements, the state holds at least two solutions. By Section 5 every solution ends in exactly one stopping state. Hence, if the complete search meets case (c) nowhere and finds exactly one state of kind (b), the secret is unique.

8. Worked example: the warm-up puzzle

Sorted by score, the guesses are $70794$, $34109$, $12531$, $90342$, $39458$ and $51545$. After the removals of Section 2 the numbers of branches are $\binom51=5$ for $34109$ and for $12531$, $\binom42=6$ for $90342$, whose second place has lost its $0$, and $\binom52=10$ for $39458$ and $51545$. So the search branches on the place of the hit of $34109$. Its first branch, $x_1=3$, removes $4$, $1$, $0$ and $9$ from the places $2$ to $5$. Now $90342$ can hit only in the places $3$, $4$, $5$ and needs two hits, which gives $3$ branches, against $4$ for $12531$, $4$ for $39458$, which has the sure hit $x_1=3$, and $6$ for $51545$:

$\{3,4\}$: $x_3=3$, $x_4=4$, and $A_5$ loses $2$. Now $12531$ needs its hit in place $2$ or $5$. Either way $39458$ is left with one possible place, which decides $x_5=8$ or $x_2=9$, and then $51545$ has one sure hit, $x_4=4$, and no possible hit: dead.
$\{3,5\}$: $x_3=3$, $x_5=2$, and $A_4$ loses $4$. Now $51545$ can hit only in place $2$ but needs two hits: dead at once.
$\{4,5\}$: $x_4=4$, $x_5=2$, and $A_3$ loses $3$. Now $12531$ needs its hit in place $2$ or $3$. The branch $x_2=2$ leaves $51545$ one hit short, while $x_3=5$ leaves $39458$ one possible place, which decides $x_2=9$ and completes $39542$, with exactly the given scores $2,0,2,1,2,1$.

The other four first branches, $x_2=4$, $x_3=1$, $x_4=0$ and $x_5=9$, die within two further branchings. Altogether the search visits $35$ states: $16$ fail the bounds, $18$ branch, $10$ of them with a single forced branch, and one is the solution. Case (c) never occurs, so $39542$ is proved to be the only solution.

9. Simpler exact methods

Filling the places from left to right with only the tools of Sections 2 and 3 is far weaker, as a guess objects only once it has too many hits or too few places left: $8\,573\,625\,136$ partial sequences of length $12$ still pass, so that search takes over $10^{10}$ steps. Meet in the middle trades cleverness for memory. List the halves, places $1$ to $8$ and $9$ to $16$, that give no guess more hits than its score, $9\,600\,850$ and $8\,429\,676$ of them. A left half with $\ell_t$ hits for guess $t$ and a right half with $h_t$ hits form a solution exactly when $\ell_t+h_t=m_t$ for every $t$, so we store all left halves in a hash table under their vectors $(\ell_t)$ and look up $(m_t-h_t)$ for each right half, as Horowitz and Sahni do for subset sums. ^[8]

How the Code Works

The C++ program ^[9] stores a State: assign holds the digit of every decided place and $-1$ for an open one, and banned holds ten flags per place, so $A_i$ is the set of digits whose flag is off. main accepts only --skip-checkpoints; without it, run_checkpoints first solves sample_puzzle and requires $39542$ as its unique solution. The secret of full_puzzle is printed only if the search counted exactly one fully decided solution.

solve_puzzle sorts the guesses by score with std::sort, applies the score-$0$ removals and calls dfs. Each call works on a copy of the state: propagate_singletons decides places with one digit left and rejects empty sets, feasible tests the bounds of Section 3, and a fully decided state is rechecked by satisfies_all and counted. Otherwise dfs computes fixed_match, candidates and need, that is $f_t$, $C_t$ and $r_t$, for every guess, skips settled guesses and keeps the first guess with the smallest combination_count, an exact multiplicative formula. branch_guess decides candidate by candidate whether it joins the subset, pruning when too many or too few remain possible, applies each complete subset to a copy with apply_equal and apply_not_equal and calls dfs. Only a second solution stops the search early; in case (c), dfs returns without counting.

Python runs the same search inside solve with nested functions and math.comb, Java with int[], boolean[][] and the helper combo. Both stop at the first solution, without the warm-up check or a uniqueness test, and like C++ both return without a result in case (c). Java's dfs also applies the first rule of Section 4 to all guesses before it chooses one. Branch counts are at most $\binom{16}{8}=12870$, so no integer type overflows. Python's and Java's sorts keep guesses with equal scores in their given order, std::sort need not, so the tie-break of Section 6, and with it the search tree, may differ between C++ libraries, but by Section 5 the solutions do not. ^[10]

Complexity and Verification

One state costs $O(GL)$ for $G=22$ guesses and $L=16$ places, as feasible and the choice each scan the $352$ pairs of a guess and a place, so $T$ calls of dfs take $O(TGL)$ time; $T$ has no useful bound in general (Section 1). Searching the whole tree, the C++ program built with Clang and libc++ makes $T=96\,029$ calls: $29\,989$ states fail the bounds, $66\,039$ branch, $53\,809$ of them with a single forced branch, and one is the solution. The first state has the most branches, $13$, and no path has more than $18$ nested branchings; with GCC's libstdc++, $T=91\,553$. On a desktop computer C++ needs about $0.2$ seconds, while Java and Python stop at the first solution, at their $58\,764$th and $86\,719$th calls, after about $0.4$ and $4$ seconds. Besides the guesses, the memory is $O(L)$ per level of the current path, at most $21$ levels by Section 7.

Outside the published code we checked that the three programs print the same $16$ digits, compared without display; that case (c) occurs in neither puzzle, using an instrumented copy of the C++ search, so its single solution is proved unique; and that meet in the middle (Section 9) finds exactly one secret among all $10^{16}$ sequences, the same one. On $2000$ random puzzles with $3$ to $5$ digits and $4$ to $12$ guesses scored against a random secret, a separate implementation of the search that completes the open places in case (c) found every solution of an exhaustive test exactly once. For other inputs case (c) matters: with the guesses $0782$, $1966$ and $5023$ scoring $0$, $1655$ and $7368$ scoring $1$, and $3643$ scoring $2$, the C++ program with only its data replaced reports $3345$ as unique, although $16$ four-digit sequences fit.

Footnotes and References

The references below supply the background facts. The bounds, the branching rule and its correctness proof are derived in this article, and the counts come from the computations described above.

Project Euler 185 — Number Mind. After each guess only the number of places with the correct digit is reported; six guesses determine the 5-digit secret 39542, and the task asks for the unique 16-digit secret consistent with 22 guesses.
Wikipedia — Mastermind (board game). A coloured or black key peg marks a code peg correct in both colour and position, a white one a correct colour in the wrong position.
Wikipedia — Hamming distance. The number of positions at which two strings of equal length differ.
M. T. Goodrich — On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results. Information Processing Letters 109 (2009), 675–678. Theorem 1: black-peg Mastermind satisfiability is NP-complete, by a reduction from 3-dimensional matching with one colour per triple plus a null colour.
Wikipedia — Backtracking. Candidates are built step by step, and a partial candidate that cannot be completed is abandoned together with its whole subtree.
Wikipedia — Binomial coefficient. C(n, k) counts the k-element subsets of an n-element set and can be computed by the multiplicative formula.
Wikipedia — Knuth's Algorithm X. Any systematic rule for choosing the next column finds all solutions; Knuth suggests a column with the fewest 1s to reduce the number of iterations.
Wikipedia — Subset sum problem. Horowitz and Sahni split the elements into two halves, list the subset sums of each half and combine the two lists.
C++ — Euler185.cpp. The linked immutable revision contains feasible, dfs, branch_guess and run_checkpoints; it is the implementation record for this article.
cppreference — std::sort. The order of equivalent elements is not guaranteed to be preserved, whereas Python's list.sort and Java's Arrays.sort are guaranteed to be stable.

Problem 185 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Guess {
    std::string digits;
    int matches = 0;
};

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

struct State {
    std::vector<int> assign;  // -1 or [0..9]
    std::vector<std::array<bool, 10>> banned;
};

bool propagate_singletons(State& st) {
    bool changed = true;
    while (changed) {
        changed = false;
        for (std::size_t pos = 0; pos < st.assign.size(); ++pos) {
            if (st.assign[pos] != -1) {
                continue;
            }
            int last_digit = -1;
            int allowed = 0;
            for (int d = 0; d <= 9; ++d) {
                if (!st.banned[pos][static_cast<std::size_t>(d)]) {
                    ++allowed;
                    last_digit = d;
                }
            }
            if (allowed == 0) {
                return false;
            }
            if (allowed == 1) {
                st.assign[pos] = last_digit;
                for (int d = 0; d <= 9; ++d) {
                    st.banned[pos][static_cast<std::size_t>(d)] = (d != last_digit);
                }
                changed = true;
            }
        }
    }
    return true;
}

bool apply_equal(State& st, const int pos, const int digit) {
    if (st.assign[static_cast<std::size_t>(pos)] == digit) {
        return true;
    }
    if (st.assign[static_cast<std::size_t>(pos)] != -1) {
        return false;
    }
    if (st.banned[static_cast<std::size_t>(pos)][static_cast<std::size_t>(digit)]) {
        return false;
    }
    st.assign[static_cast<std::size_t>(pos)] = digit;
    for (int d = 0; d <= 9; ++d) {
        st.banned[static_cast<std::size_t>(pos)][static_cast<std::size_t>(d)] = (d != digit);
    }
    return true;
}

bool apply_not_equal(State& st, const int pos, const int digit) {
    if (st.assign[static_cast<std::size_t>(pos)] == digit) {
        return false;
    }
    if (st.assign[static_cast<std::size_t>(pos)] != -1) {
        return true;
    }
    st.banned[static_cast<std::size_t>(pos)][static_cast<std::size_t>(digit)] = true;
    return true;
}

bool feasible(const State& st, const std::vector<Guess>& guesses) {
    for (const auto& g : guesses) {
        int min_match = 0;
        int max_match = 0;
        for (std::size_t i = 0; i < st.assign.size(); ++i) {
            const int d = g.digits[i] - '0';
            if (st.assign[i] == d) {
                ++min_match;
                ++max_match;
            } else if (st.assign[i] == -1 && !st.banned[i][static_cast<std::size_t>(d)]) {
                ++max_match;
            }
        }
        if (min_match > g.matches || max_match < g.matches) {
            return false;
        }
    }

    for (std::size_t i = 0; i < st.assign.size(); ++i) {
        if (st.assign[i] != -1) {
            continue;
        }
        bool any = false;
        for (int d = 0; d <= 9; ++d) {
            if (!st.banned[i][static_cast<std::size_t>(d)]) {
                any = true;
                break;
            }
        }
        if (!any) {
            return false;
        }
    }
    return true;
}

std::string assignment_to_string(const State& st) {
    std::string s(st.assign.size(), '0');
    for (std::size_t i = 0; i < st.assign.size(); ++i) {
        if (st.assign[i] < 0) {
            return "";
        }
        s[i] = static_cast<char>('0' + st.assign[i]);
    }
    return s;
}

bool satisfies_all(const std::string& candidate, const std::vector<Guess>& guesses) {
    for (const auto& g : guesses) {
        int match = 0;
        for (std::size_t i = 0; i < candidate.size(); ++i) {
            if (candidate[i] == g.digits[i]) {
                ++match;
            }
        }
        if (match != g.matches) {
            return false;
        }
    }
    return true;
}

long long combination_count(const int n, const int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    const int kk = std::min(k, n - k);
    long long value = 1;
    for (int i = 1; i <= kk; ++i) {
        value = value * (n - kk + i) / i;
    }
    return value;
}

void branch_guess(const std::vector<Guess>& guesses,
                  const int guess_idx,
                  const std::vector<int>& candidates,
                  const int need,
                  int idx,
                  std::vector<int>& chosen,
                  const State& base,
                  std::string& first_solution,
                  int& solutions);

void dfs(const std::vector<Guess>& guesses, const State& st, std::string& first_solution, int& solutions) {
    if (solutions >= 2) {
        return;
    }

    State cur = st;
    if (!propagate_singletons(cur) || !feasible(cur, guesses)) {
        return;
    }

    bool done = true;
    for (int d : cur.assign) {
        if (d < 0) {
            done = false;
            break;
        }
    }
    if (done) {
        const std::string candidate = assignment_to_string(cur);
        if (!candidate.empty() && satisfies_all(candidate, guesses)) {
            ++solutions;
            if (solutions == 1) {
                first_solution = candidate;
            }
        }
        return;
    }

    int best_guess = -1;
    long long best_branching = (1LL << 60);
    std::vector<int> best_candidates;
    int best_need = 0;

    for (std::size_t gi = 0; gi < guesses.size(); ++gi) {
        const Guess& g = guesses[gi];
        int fixed_match = 0;
        std::vector<int> candidates;
        for (std::size_t pos = 0; pos < cur.assign.size(); ++pos) {
            const int digit = g.digits[pos] - '0';
            if (cur.assign[pos] == digit) {
                ++fixed_match;
            } else if (cur.assign[pos] == -1 && !cur.banned[pos][static_cast<std::size_t>(digit)]) {
                candidates.push_back(static_cast<int>(pos));
            }
        }
        const int need = g.matches - fixed_match;
        if (need < 0 || need > static_cast<int>(candidates.size())) {
            return;
        }
        if (need == 0 && candidates.empty()) {
            continue;
        }
        const long long branches = combination_count(static_cast<int>(candidates.size()), need);
        if (branches < best_branching) {
            best_branching = branches;
            best_guess = static_cast<int>(gi);
            best_candidates = std::move(candidates);
            best_need = need;
        }
    }

    if (best_guess < 0) {
        return;
    }

    std::vector<int> chosen;
    branch_guess(guesses, best_guess, best_candidates, best_need, 0, chosen,
                 cur, first_solution, solutions);
}

void branch_guess(const std::vector<Guess>& guesses,
                  const int guess_idx,
                  const std::vector<int>& candidates,
                  const int need,
                  int idx,
                  std::vector<int>& chosen,
                  const State& base,
                  std::string& first_solution,
                  int& solutions) {
    if (solutions >= 2) {
        return;
    }
    const int remaining = static_cast<int>(candidates.size()) - idx;
    if (static_cast<int>(chosen.size()) > need || static_cast<int>(chosen.size()) + remaining < need) {
        return;
    }
    if (idx == static_cast<int>(candidates.size())) {
        State next = base;
        const Guess& g = guesses[static_cast<std::size_t>(guess_idx)];
        std::vector<bool> selected(candidates.size(), false);
        for (int p : chosen) {
            for (std::size_t i = 0; i < candidates.size(); ++i) {
                if (candidates[i] == p) {
                    selected[i] = true;
                    break;
                }
            }
        }

        for (std::size_t i = 0; i < candidates.size(); ++i) {
            const int pos = candidates[i];
            const int digit = g.digits[static_cast<std::size_t>(pos)] - '0';
            const bool must_equal = selected[i];
            const bool ok = must_equal ? apply_equal(next, pos, digit) : apply_not_equal(next, pos, digit);
            if (!ok) {
                return;
            }
        }
        dfs(guesses, next, first_solution, solutions);
        return;
    }

    chosen.push_back(candidates[static_cast<std::size_t>(idx)]);
    branch_guess(guesses, guess_idx, candidates, need, idx + 1, chosen,
                 base, first_solution, solutions);
    chosen.pop_back();

    branch_guess(guesses, guess_idx, candidates, need, idx + 1, chosen,
                 base, first_solution, solutions);
}

std::string solve_puzzle(std::vector<Guess> guesses, bool* unique) {
    if (guesses.empty()) {
        if (unique != nullptr) {
            *unique = false;
        }
        return "";
    }
    const int length = static_cast<int>(guesses.front().digits.size());

    std::sort(guesses.begin(), guesses.end(), [](const Guess& a, const Guess& b) {
        return a.matches < b.matches;
    });

    State initial;
    initial.assign.assign(static_cast<std::size_t>(length), -1);
    initial.banned.assign(static_cast<std::size_t>(length), {});
    for (auto& row : initial.banned) {
        row.fill(false);
    }

    for (const auto& g : guesses) {
        if (static_cast<int>(g.digits.size()) != length) {
            if (unique != nullptr) {
                *unique = false;
            }
            return "";
        }
        if (g.matches == 0) {
            for (int i = 0; i < length; ++i) {
                const int d = g.digits[static_cast<std::size_t>(i)] - '0';
                initial.banned[static_cast<std::size_t>(i)][static_cast<std::size_t>(d)] = true;
            }
        }
    }

    std::string first_solution;
    int solutions = 0;
    dfs(guesses, initial, first_solution, solutions);
    if (unique != nullptr) {
        *unique = (solutions == 1);
    }
    return first_solution;
}

std::vector<Guess> sample_puzzle() {
    return {
        {"90342", 2}, {"70794", 0}, {"39458", 2},
        {"34109", 1}, {"51545", 2}, {"12531", 1},
    };
}

std::vector<Guess> full_puzzle() {
    return {
        {"5616185650518293", 2}, {"3847439647293047", 1},
        {"5855462940810587", 3}, {"9742855507068353", 3},
        {"4296849643607543", 3}, {"3174248439465858", 1},
        {"4513559094146117", 2}, {"7890971548908067", 3},
        {"8157356344118483", 1}, {"2615250744386899", 2},
        {"8690095851526254", 3}, {"6375711915077050", 1},
        {"6913859173121360", 1}, {"6442889055042768", 2},
        {"2321386104303845", 0}, {"2326509471271448", 2},
        {"5251583379644322", 2}, {"1748270476758276", 3},
        {"4895722652190306", 1}, {"3041631117224635", 3},
        {"1841236454324589", 3}, {"2659862637316867", 2},
    };
}

bool run_checkpoints() {
    bool unique = false;
    const std::string sample = solve_puzzle(sample_puzzle(), &unique);
    if (sample != "39542" || !unique) {
        std::cerr << "Checkpoint failed for sample puzzle" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    bool unique = false;
    const std::string answer = solve_puzzle(full_puzzle(), &unique);
    if (!unique || answer.empty()) {
        std::cerr << "Failed to find a unique solution" << '\n';
        return 3;
    }
    std::cout << answer << '\n';
    return 0;
}

Python

def solve():
    guesses = [
        ("5616185650518293", 2), ("3847439647293047", 1),
        ("5855462940810587", 3), ("9742855507068353", 3),
        ("4296849643607543", 3), ("3174248439465858", 1),
        ("4513559094146117", 2), ("7890971548908067", 3),
        ("8157356344118483", 1), ("2615250744386899", 2),
        ("8690095851526254", 3), ("6375711915077050", 1),
        ("6913859173121360", 1), ("6442889055042768", 2),
        ("2321386104303845", 0), ("2326509471271448", 2),
        ("5251583379644322", 2), ("1748270476758276", 3),
        ("4895722652190306", 1), ("3041631117224635", 3),
        ("1841236454324589", 3), ("2659862637316867", 2),
    ]
    guesses.sort(key=lambda x: x[1])
    length = len(guesses[0][0])

    def propagate(assign, banned):
        changed = True
        while changed:
            changed = False
            for pos in range(length):
                if assign[pos] != -1:
                    continue
                allowed = [d for d in range(10) if not banned[pos][d]]
                if len(allowed) == 0:
                    return False
                if len(allowed) == 1:
                    assign[pos] = allowed[0]
                    for d in range(10):
                        banned[pos][d] = (d != allowed[0])
                    changed = True
        return True

    def feasible(assign, banned):
        for digits, matches in guesses:
            min_m = 0
            max_m = 0
            for i in range(length):
                d = int(digits[i])
                if assign[i] == d:
                    min_m += 1
                    max_m += 1
                elif assign[i] == -1 and not banned[i][d]:
                    max_m += 1
            if min_m > matches or max_m < matches:
                return False
        return True

    def satisfies_all(assign):
        for digits, matches in guesses:
            m = sum(1 for i in range(length) if assign[i] == int(digits[i]))
            if m != matches:
                return False
        return True

    from math import comb

    result = [None]

    def dfs(assign, banned):
        if result[0] is not None:
            return
        a = list(assign)
        b = [list(row) for row in banned]
        if not propagate(a, b):
            return
        if not feasible(a, b):
            return
        if all(d >= 0 for d in a):
            if satisfies_all(a):
                result[0] = ''.join(str(d) for d in a)
            return

        best_gi = -1
        best_branching = float('inf')
        best_cands = []
        best_need = 0
        for gi, (digits, matches) in enumerate(guesses):
            fixed = 0
            cands = []
            for pos in range(length):
                d = int(digits[pos])
                if a[pos] == d:
                    fixed += 1
                elif a[pos] == -1 and not b[pos][d]:
                    cands.append(pos)
            need = matches - fixed
            if need < 0 or need > len(cands):
                return
            if need == 0 and not cands:
                continue
            branching = comb(len(cands), need)
            if branching < best_branching:
                best_branching = branching
                best_gi = gi
                best_cands = cands
                best_need = need

        if best_gi < 0:
            return

        digits_str = guesses[best_gi][0]

        def branch(idx, chosen):
            if result[0] is not None:
                return
            remaining = len(best_cands) - idx
            if len(chosen) > best_need or len(chosen) + remaining < best_need:
                return
            if idx == len(best_cands):
                na = list(a)
                nb = [list(row) for row in b]
                chosen_set = set(chosen)
                for i, pos in enumerate(best_cands):
                    d = int(digits_str[pos])
                    if pos in chosen_set:
                        if na[pos] != -1 and na[pos] != d:
                            return
                        if na[pos] == -1 and nb[pos][d]:
                            return
                        na[pos] = d
                        for dd in range(10):
                            nb[pos][dd] = (dd != d)
                    else:
                        if na[pos] == d:
                            return
                        nb[pos][d] = True
                dfs(na, nb)
                return
            branch(idx + 1, chosen + [best_cands[idx]])
            branch(idx + 1, chosen)

        branch(0, [])

    assign = [-1] * length
    banned = [[False] * 10 for _ in range(length)]
    for digits, matches in guesses:
        if matches == 0:
            for i in range(length):
                banned[i][int(digits[i])] = True
    dfs(assign, banned)
    return result[0]

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler185 {
    static String[][] guesses = {
            { "5616185650518293", "2" }, { "3847439647293047", "1" }, { "5855462940810587", "3" },
            { "9742855507068353", "3" }, { "4296849643607543", "3" }, { "3174248439465858", "1" },
            { "4513559094146117", "2" }, { "7890971548908067", "3" }, { "8157356344118483", "1" },
            { "2615250744386899", "2" }, { "8690095851526254", "3" }, { "6375711915077050", "1" },
            { "6913859173121360", "1" }, { "6442889055042768", "2" }, { "2321386104303845", "0" },
            { "2326509471271448", "2" }, { "5251583379644322", "2" }, { "1748270476758276", "3" },
            { "4895722652190306", "1" }, { "3041631117224635", "3" }, { "1841236454324589", "3" },
            { "2659862637316867", "2" } };
    static int N = 16;

    static boolean propagate(int[] a, boolean[][] b) {
        boolean ch = true;
        while (ch) {
            ch = false;
            for (int i = 0; i < N; i++) {
                if (a[i] >= 0)
                    continue;
                int cnt = 0, last = -1;
                for (int d = 0; d < 10; d++)
                    if (!b[i][d]) {
                        cnt++;
                        last = d;
                    }
                if (cnt == 0)
                    return false;
                if (cnt == 1) {
                    a[i] = last;
                    ch = true;
                }
            }
        }
        return true;
    }

    static boolean feasible(int[] a, boolean[][] b) {
        for (String[] g : guesses) {
            int m = Integer.parseInt(g[1]);
            String d = g[0];
            int km = 0, unk = 0;
            for (int i = 0; i < N; i++) {
                if (a[i] == d.charAt(i) - '0')
                    km++;
                else if (a[i] < 0 && !b[i][d.charAt(i) - '0'])
                    unk++;
            }
            if (km > m || km + unk < m)
                return false;
        }
        return true;
    }

    static String dfs(int[] a, boolean[][] b) {
        a = a.clone();
        b = Arrays.stream(b).map(boolean[]::clone).toArray(boolean[][]::new);
        if (!propagate(a, b) || !feasible(a, b))
            return null;
        // Apply zero-remaining constraints
        for (String[] g : guesses) {
            int m = Integer.parseInt(g[1]);
            String d = g[0];
            int km = 0;
            for (int i = 0; i < N; i++)
                if (a[i] == d.charAt(i) - '0')
                    km++;
            if (km == m) {
                for (int i = 0; i < N; i++)
                    if (a[i] < 0 && !b[i][d.charAt(i) - '0'])
                        b[i][d.charAt(i) - '0'] = true;
            }
        }
        if (!propagate(a, b) || !feasible(a, b))
            return null;
        boolean done = true;
        for (int x : a)
            if (x < 0) {
                done = false;
                break;
            }
        if (done) {
            for (String[] g : guesses) {
                int m = Integer.parseInt(g[1]);
                String d = g[0];
                int c = 0;
                for (int i = 0; i < N; i++)
                    if (a[i] == d.charAt(i) - '0')
                        c++;
                if (c != m)
                    return null;
            }
            StringBuilder sb = new StringBuilder();
            for (int x : a)
                sb.append(x);
            return sb.toString();
        }
        // Pick best guess
        int bestGi = -1;
        long bestBr = Long.MAX_VALUE;
        for (int gi = 0; gi < guesses.length; gi++) {
            int m = Integer.parseInt(guesses[gi][1]);
            String d = guesses[gi][0];
            int km = 0;
            List<Integer> unk = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (a[i] == d.charAt(i) - '0')
                    km++;
                else if (a[i] < 0 && !b[i][d.charAt(i) - '0'])
                    unk.add(i);
            }
            int need = m - km;
            if (need < 0 || unk.size() < need)
                return null;
            if (need == 0 && unk.isEmpty())
                continue;
            long br = comb(unk.size(), need);
            if (br < bestBr) {
                bestBr = br;
                bestGi = gi;
            }
        }
        if (bestGi < 0)
            return null;
        int m = Integer.parseInt(guesses[bestGi][1]);
        String d = guesses[bestGi][0];
        int km = 0;
        List<Integer> unk = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (a[i] == d.charAt(i) - '0')
                km++;
            else if (a[i] < 0 && !b[i][d.charAt(i) - '0'])
                unk.add(i);
        }
        int need = m - km;
        return combo(a, b, d, unk, need, 0, new ArrayList<>());
    }

    static long comb(int n, int k) {
        if (k < 0 || k > n)
            return 0;
        k = Math.min(k, n - k);
        long v = 1;
        for (int i = 1; i <= k; i++)
            v = v * (n - k + i) / i;
        return v;
    }

    static String combo(int[] a, boolean[][] b, String d, List<Integer> unk, int need, int idx, List<Integer> chosen) {
        if (chosen.size() == need) {
            int[] a2 = a.clone();
            boolean[][] b2 = Arrays.stream(b).map(boolean[]::clone).toArray(boolean[][]::new);
            Set<Integer> cs = new HashSet<>(chosen);
            for (int i : chosen)
                a2[i] = d.charAt(i) - '0';
            for (int i : unk)
                if (!cs.contains(i))
                    b2[i][d.charAt(i) - '0'] = true;
            return dfs(a2, b2);
        }
        if (idx >= unk.size() || unk.size() - idx < need - chosen.size())
            return null;
        chosen.add(unk.get(idx));
        String r = combo(a, b, d, unk, need, idx + 1, chosen);
        if (r != null)
            return r;
        chosen.remove(chosen.size() - 1);
        return combo(a, b, d, unk, need, idx + 1, chosen);
    }

    public static void main(String[] args) {
        int[] a = new int[N];
        Arrays.fill(a, -1);
        boolean[][] b = new boolean[N][10];
        // Pre-apply zero-match guesses
        for (String[] g : guesses)
            if (Integer.parseInt(g[1]) == 0)
                for (int i = 0; i < N; i++)
                    b[i][g[0].charAt(i) - '0'] = true;
        // Sort by ascending matches
        Arrays.sort(guesses, (x, y) -> Integer.compare(Integer.parseInt(x[1]), Integer.parseInt(y[1])));
        System.out.println(dfs(a, b));
    }
}