Solution

Answer: 4640261571849533

Let the unknown 16-digit secret be

$$x_0x_1x_2\dots x_{15}$$

Each guess gives a constraint of the form:

“Exactly $k$ positions match.”

This is a constraint satisfaction problem.

For each row $g$,

$$\sum_{i=0}^{15} [x_i = g_i] = k$$

where $[P]$ is 1 if proposition $P$ is true and 0 otherwise.

The key observation is that the constraints are extremely tight:

22 equations,
only 16 digit positions,
each position has only 10 possibilities.

A brute force search over $10^{16}$ candidates is impossible, but a carefully pruned backtracking search is very small.

Mathematical Analysis

We encode each guess as:

$$(g^{(j)}, c^{(j)})$$

where:

$g^{(j)}$ is a 16-digit string,
$c^{(j)}$ is the required number of exact matches.

For a partially constructed secret, suppose we have already assigned some positions.

For every clue $j$, define:

$m_j$: current number of matches already forced,
$r_j$: remaining positions not assigned yet.

Then feasibility requires

$$m_j \le c_j \le m_j + r_j$$

because:

we cannot exceed the required number of matches,
and even if all remaining positions matched, we still must be able to reach $c_j$.

This gives a powerful pruning rule.

Strong Constraint from the “0 correct” row

We are told:

$$2321386104303845 ; 0 \text{ correct}$$

Therefore the secret differs from this row in every position.

So immediately:

$$x_i \ne (\text{digit in that row at position } i)$$

for all 16 positions.

This alone eliminates one digit per position.

Efficient Search Strategy

We recursively assign digits position-by-position.

At each step:

Try candidate digits.
Update all clue match counts.
Reject immediately if any clue becomes impossible:

$$m_j > c_j$$

$$m_j + r_j < c_j$$

Because the constraints are so restrictive, the tree collapses rapidly and yields a unique solution.

Python Implementation

from collections import defaultdict

# (guess, number_of_correct_positions)
clues = [
    ("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),
]

N = 16

# Precompute allowed digits for each position
allowed = [set("0123456789") for _ in range(N)]

# Apply the 0-correct constraint immediately
for guess, score in clues:
    if score == 0:
        for i, d in enumerate(guess):
            allowed[i].discard(d)

solution = None

def search(pos, current, matches):
    global solution

    if solution is not None:
        return

    # Finished all positions
    if pos == N:
        if all(matches[i] == clues[i][1] for i in range(len(clues))):
            solution = "".join(current)
        return

    for digit in allowed[pos]:

        new_matches = matches[:]

        # Update match counts
        for i, (guess, score) in enumerate(clues):
            if guess[pos] == digit:
                new_matches[i] += 1

        # Feasibility check
        feasible = True
        remaining = N - pos - 1

        for i, (guess, score) in enumerate(clues):
            m = new_matches[i]

            # Too many matches already
            if m > score:
                feasible = False
                break

            # Even matching everything left can't reach score
            if m + remaining < score:
                feasible = False
                break

        if feasible:
            current.append(digit)
            search(pos + 1, current, new_matches)
            current.pop()

search(0, [], [0] * len(clues))

print(solution)

Code Walkthrough

1. Store the clues

clues = [
    ("5616185650518293", 2),
    ...
]

Each tuple contains:

a guessed sequence,
the exact number of correct positions.

2. Allowed digits

allowed = [set("0123456789") for _ in range(N)]

Initially every position may contain any digit.

Then we process the clue with 0 matches:

if score == 0:
    for i, d in enumerate(guess):
        allowed[i].discard(d)

So those digits are forbidden in their positions.

3. Recursive search

search(pos, current, matches)

Parameters:

pos = current digit position,
current = partial secret,
matches[i] = current matches for clue $i$.

4. Update constraints

When trying a digit:

if guess[pos] == digit:
    new_matches[i] += 1

5. Pruning

For each clue:

if m > score:

Too many matches already.

and

if m + remaining < score:

Even if all remaining positions matched, we could not reach the required total.

These two inequalities prune almost the entire search tree.

Verification on the Small Example

For the sample:

90342 ;2
70794 ;0
39458 ;2
34109 ;1
51545 ;2
12531 ;1

the same program finds uniquely:

$$39542$$

matching the problem statement.

Final Verification

The computed secret is:

$$4640261571849533$$

Checking against a few clues:

$5616185650518293$ → exactly 2 matches
$3847439647293047$ → exactly 1 match
$2321386104303845$ → 0 matches

All 22 constraints are satisfied exactly, and the solution is unique.

Answer: 4640261571849533

Project Euler Problem 185