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

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

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

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));
    }
}