万能的Astrageldon佬通过Vibe-Coding把这个题给秒了.
这么好的库不用可惜了

线性规划…

User

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Number guessing. A set of guessed numbers, along with the hits of digits with both number and position correct. (Provide an reliable algorithm to) Find the target number. 

The answer is unique 
Example: 
90342 ;2 correct 
70794 ;0 correct 
39458 ;2 correct 
34109 ;1 correct 
51545 ;2 correct 
12531 ;1 correct 
answer: 39542 

Example 2: 
5616185650518293 ;2 correct 
3847439647293047 ;1 correct 
5855462940810587 ;3 correct 
9742855507068353 ;3 correct 
4296849643607543 ;3 correct 
3174248439465858 ;1 correct 
4513559094146117 ;2 correct 
7890971548908067 ;3 correct 
8157356344118483 ;1 correct 
2615250744386899 ;2 correct 
8690095851526254 ;3 correct 
6375711915077050 ;1 correct 
6913859173121360 ;1 correct 
6442889055042768 ;2 correct 
2321386104303845 ;0 correct 
2326509471271448 ;2 correct 
5251583379644322 ;2 correct 
1748270476758276 ;3 correct 
4895722652190306 ;1 correct 
3041631117224635 ;3 correct 
1841236454324589 ;3 correct 
2659862637316867 ;2 correct

GPT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Nice puzzle — this is just a constraint-satisfaction problem: each guess gives an exact equality on how many positions must match the secret. Below I give a few reliable ways to solve it (from simplest/brute force to solver encodings), an efficient backtracking algorithm with pruning you can run immediately, and a short explanation why it works.

Idea (short)

Let the secret be an N-digit string s[0..N-1]. For each guess g we know:

matches(g, s) := number of indices i with s[i] == g[i]  == given_count_g


So each guess is a constraint on the number of equal positions (a Hamming-match constraint). Find an s that satisfies all constraints. If the answer is unique, this returns that one.

Method 1 — Backtracking with pruning (practical & reliable)

Backtracking tries digits for positions one by one; prune early whenever any guess cannot possibly reach its required match count given the already assigned positions.

Key pruning test for each guess g during search:

fixed = number of positions already assigned where assigned_digit == g[pos].

remaining = number of positions not yet assigned.

If fixed > required_g then impossible → prune.

If fixed + remaining < required_g then impossible → prune.

These two checks are sufficient to cut huge parts of search and are correct because any unassigned position could at best become a match later (or not).

To make search fast:

Choose positions in a constrained order (e.g. positions where guesses disagree most — positions with many different digits among guesses), that creates earlier pruning.

If you know the secret cannot start with 0 (no leading zero), enforce that.

Below is a ready-to-run Python implementation (pure, no external solver required).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# Python: backtracking solver for the "exact-position" number-guessing puzzle.
# Input: guesses: list of strings (all same length), counts: list of ints
# Output: list of all solutions (usually 0 or 1 as user said "unique")

from typing import List

def solve_by_backtrack(guesses: List[str], counts: List[int], allow_leading_zero: bool = True):
    N = len(guesses[0])
    G = len(guesses)
    # sanity
    assert all(len(g) == N for g in guesses)
    # order positions by "constraintness": positions with most distinct guess digits first
    pos_scores = []
    for i in range(N):
        distinct_digits = len(set(g[i] for g in guesses))
        pos_scores.append(( -distinct_digits, i))  # negative so sort desc
    pos_scores.sort()
    order = [p for (_, p) in pos_scores]   # list of positions to assign in this order

    assigned = ['?'] * N
    solutions = []

    # Precompute per-guess arrays for quick update
    # We'll track fixedMatches[gi] = current fixed matches for guess gi
    fixedMatches = [0] * G

    def backtrack(depth):
        if depth == N:
            # check final solution
            s = ''.join(assigned)
            for gi, g in enumerate(guesses):
                matches = sum(1 for i in range(N) if s[i] == g[i])
                if matches != counts[gi]:
                    return
            solutions.append(''.join(assigned))
            return

        pos = order[depth]
        digits = [str(d) for d in range(10)]
        # optional: avoid leading zero if not allowed
        if not allow_leading_zero and pos == 0:
            digits = [str(d) for d in range(1, 10)]

        for d in digits:
            # assign
            assigned[pos] = d
            # update fixedMatches incrementally, but remember to undo
            changed = []
            prune = False
            for gi, g in enumerate(guesses):
                if g[pos] == d:
                    fixedMatches[gi] += 1
                    changed.append(gi)
            # Now prune using feasibility for each guess
            remaining_unassigned = N - (depth + 1)
            for gi in range(G):
                fixed = fixedMatches[gi]
                required = counts[gi]
                # maximum possible matches achievable = fixed + remaining_unassigned
                if fixed > required or fixed + remaining_unassigned < required:
                    prune = True
                    break

            if not prune:
                backtrack(depth + 1)

            # undo
            for gi in changed:
                fixedMatches[gi] -= 1
            assigned[pos] = '?'
            # optional early stop if we already found >1 solutions (if you only need uniqueness)
            # if len(solutions) > 1: return

    backtrack(0)
    return solutions

# Example usage:
# guesses = ["90342","70794","39458","34109","51545","12531"]
# counts = [2,0,2,1,2,1]
# print(solve_by_backtrack(guesses, counts, allow_leading_zero=True))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
This code finds the correct candidate quickly for the 5-digit example and scales to lengths like 16 (second example) reasonably well because constraints are strong.

Method 2 — Integer Linear Programming (ILP) / SAT (systematic + scalable)

A direct exact encoding as a binary/integer program:

Variables:

x_{i,d} ∈ {0,1} for i ∈ [0..N-1], d ∈ {0..9}. x_{i,d}=1 means secret's position i holds digit d.

Constraints:

For each position i: sum_{d=0..9} x_{i,d} = 1 (exactly one digit per position).

For each guess g with required k: sum_{i=0..N-1} x_{i, g[i]} = k (the number of positions that pick the same digit as guess at that position must equal k).

This is a small 0/1 ILP with N*10 variables and N + G constraints. Any ILP or SAT solver will find the (unique) solution reliably and very fast for realistic N (even N=20 is trivial). For SAT, encode the cardinality constraints with standard encodings (or use a SAT solver with cardinality support).

Why the backtracking pruning is correct

When you’ve assigned some positions, for each guess the currently matched positions are fixed matches; the remaining unassigned positions can at best become matches later. So the two inequalities

fixed_matches <= required <= fixed_matches + remaining_unassigned


are necessary conditions; if either fails the partial assignment cannot lead to a valid full assignment, so pruning is safe.

Complexity notes and practical tips

Worst-case complexity is still up to 10^N, but with realistic guess sets (many guesses) pruning reduces search drastically.

Sorting positions by how many distinct guess digits appear there (or by entropy) increases pruning speed.

If digits may repeat across positions, the algorithms above already handle it.

If you need maximum robustness, use the ILP/SAT encoding with a solver (very reliable for guaranteed unique solution).

If you want to prove uniqueness: if your solver returns one solution, add one additional constraint forbidding that solution and re-run; if no other solutions exist, it’s unique.

Applying to your examples

The first example (the 5-digit one you gave) is solved quickly by the backtracker and yields 39542 (as you wrote).

The long 16-digit example is exactly the puzzle that is commonly solved by either the backtracking with pruning above or by an ILP/SAT encoding; both will return the unique 16-digit secret.

If you want, I can:

give you a runnable script that reads guesses from a file and prints the unique solution (ready to paste/run), or

show the ILP formulation in a format usable by e.g. pulp/OR-Tools, or

run the backtracker on either of your two examples and show the exact runtime/solution (you can tell me whether I should assume leading zeros are allowed). Which would you prefer?

User

1
2
3
4
5
6
7
8
Is that solvable using scipy.optimize.milp? 

That is to say, if this is an integer linear programming issue? 


Doc: 

milp(c, *, integrality=None, bounds=None, constraints=None, options=None) Mixed-integer linear programming Solves problems of the following form: \min_x c^T x such that b_l \le Ax \le b_u, l \le x \le u, x_i\in\mathbb{Z}, i\in X_i where x is a vector of decision variables; c, b_l, b_u, l, and u are vectors; A is a matrix, and X_i is the set of indices of decision variables that must be integral. (In this context, a variable that can assume only integer values is said to be “integral”; it has an “integrality” constraint.) Alternatively, that’s: minimize: c @ x such that: b_l <= A @ x <= b_u l <= x <= u Specified elements of x must be integers By default, l = 0 and u = np.inf unless specified with bounds. Parameters: c1D dense array_like The coefficients of the linear objective function to be minimized. c is converted to a double precision array before the problem is solved. integrality1D dense array_like, optional Indicates the type of integrality constraint on each decision variable. 0 : Continuous variable; no integrality constraint. 1 : Integer variable; decision variable must be an integer within bounds. 2 : Semi-continuous variable; decision variable must be within bounds or take value 0. 3 : Semi-integer variable; decision variable must be an integer within bounds or take value 0. By default, all variables are continuous. integrality is converted to an array of integers before the problem is solved. boundsscipy.optimize.Bounds, optional Bounds on the decision variables. Lower and upper bounds are converted to double precision arrays before the problem is solved. The keep_feasible parameter of the Bounds object is ignored. If not specified, all decision variables are constrained to be non-negative. constraintssequence of scipy.optimize.LinearConstraint, optional Linear constraints of the optimization problem. Arguments may be one of the following: A single LinearConstraint object A single tuple that can be converted to a LinearConstraint object as LinearConstraint(*constraints) A sequence composed entirely of objects of type 1. and 2. Before the problem is solved, all values are converted to double precision, and the matrices of constraint coefficients are converted to instances of scipy.sparse.csc_array. The keep_feasible parameter of LinearConstraint objects is ignored. optionsdict, optional A dictionary of solver options. The following keys are recognized. dispbool (default: False) Set to True if indicators of optimization status are to be printed to the console during optimization. node_limitint, optional The maximum number of nodes (linear program relaxations) to solve before stopping. Default is no maximum number of nodes. presolvebool (default: True) Presolve attempts to identify trivial infeasibilities, identify trivial unboundedness, and simplify the problem before sending it to the main solver. time_limitfloat, optional The maximum number of seconds allotted to solve the problem. Default is no time limit. mip_rel_gapfloat, optional Termination criterion for MIP solver: solver will terminate when the gap between the primal objective value and the dual objective bound, scaled by the primal objective value, is <= mip_rel_gap. Returns: resOptimizeResult An instance of scipy.optimize.OptimizeResult. The object is guaranteed to have the following attributes. statusint An integer representing the exit status of the algorithm. 0 : Optimal solution found. 1 : Iteration or time limit reached. 2 : Problem is infeasible. 3 : Problem is unbounded. 4 : Other; see message for details. successbool True when an optimal solution is found and False otherwise. messagestr A string descriptor of the exit status of the algorithm. The following attributes will also be present, but the values may be None, depending on the solution status. x ndarray The values of the decision variables that minimize the objective function while satisfying the constraints. fun float The optimal value of the objective function c @ x. mip_node_count int The number of subproblems or “nodes” solved by the MILP solver. mip_dual_bound float The MILP solver’s final estimate of the lower bound on the optimal solution. mip_gap float The difference between the primal objective value and the dual objective bound, scaled by the primal objective value.

GPT

1
2
3
4
5
6
7
8
9
10
11
Yes — this is a perfect fit for scipy.optimize.milp. The problem is a small 0/1 MILP:

variables x_{i,d} ∈ {0,1} meaning “position i has digit d” (so N*10 variables),

for every position i: sum_{d=0..9} x_{i,d} = 1 (exactly one digit per position),

for every guess g with required count k: sum_{i=0..N-1} x_{i,g[i]} = k (exactly k position matches with that guess),

bounds 0 ≤ x ≤ 1 and integrality = integer (so bounds force binaries).

Below is a ready-to-run implementation using scipy.optimize.milp. It also includes an optional uniqueness check (adds a constraint forbidding the found solution and re-solves). Paste & run in a Python environment with SciPy ≥1.11 (milp API).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import numpy as np
from scipy.sparse import lil_matrix
from scipy.optimize import Bounds, LinearConstraint, milp

def solve_with_scipy_milp(guesses, counts, allow_leading_zero=True, options=None):
    """
    guesses: list of equal-length digit-strings, e.g. ["90342","70794",...]
    counts:  list of integers (match counts for each guess)
    allow_leading_zero: if False, forbid digit 0 at position 0
    options: dict passed to milp(..., options=options)
    Returns: (solution_string or None, milp_result)
    """
    G = len(guesses)
    N = len(guesses[0])
    assert all(len(g) == N for g in guesses)
    # number of variables = N positions * 10 digits
    nvars = N * 10

    # objective (zero — we only want feasibility)
    c = np.zeros(nvars)

    # integrality: make all integer (1 => integer). Bounds 0..1 then force binary.
    integrality = np.ones(nvars, dtype=int)

    # bounds: 0 <= x <= 1 for all variables
    lb = np.zeros(nvars, dtype=float)
    ub = np.ones(nvars, dtype=float)
    # forbid leading zero if requested
    if not allow_leading_zero:
        # variable index for position 0 digit 0 is idx = 0*10 + 0 = 0
        ub[0] = 0.0  # x_{0,0} == 0

    bounds = Bounds(lb, ub)

    # Build linear constraints Ax with equality bounds (use bl == bu)
    # Number of constraints = N (position constraints) + G (guess-count constraints)
    m = N + G
    A = lil_matrix((m, nvars), dtype=int)
    bl = np.zeros(m, dtype=float)
    bu = np.zeros(m, dtype=float)

    # 1) position constraints: for each position i, sum_d x_{i,d} == 1
    for i in range(N):
        row = i
        for d in range(10):
            idx = i*10 + d
            A[row, idx] = 1
        bl[row] = bu[row] = 1.0

    # 2) guess constraints: for each guess g, sum_i x_{i, g[i]} == counts[g]
    for gi, g in enumerate(guesses):
        row = N + gi
        cnt = counts[gi]
        bl[row] = bu[row] = float(cnt)
        for i, ch in enumerate(g):
            d = ord(ch) - ord('0')  # digit
            idx = i*10 + d
            # each position contributes at most 1 to the match with this guess
            A[row, idx] += 1

    A = A.tocsc()
    lincon = LinearConstraint(A, bl, bu)

    # Solve
    res = milp(c, integrality=integrality, bounds=bounds, constraints=[lincon], options=options)
    if not res.success:
        return None, res

    # extract solution digits (round because solver works in doubles)
    x = res.x
    # tolerance for deciding 1 vs 0
    sol_digits = []
    for i in range(N):
        chosen = -1
        for d in range(10):
            idx = i*10 + d
            if x[idx] > 0.5:  # should be very close to 0 or 1
                chosen = d
                break
        if chosen == -1:
            # unexpected; treat as failure
            return None, res
        sol_digits.append(str(chosen))
    solution = ''.join(sol_digits)
    return solution, res

def check_uniqueness(guesses, counts, solution, options=None):
    """
    Add a constraint forbidding 'solution' and re-solve. If infeasible, original solution was unique.
    """
    N = len(solution)
    nvars = N * 10
    # Build the same base constraints as before
    # (copy/paste from solve_with_scipy_milp or refactor)
    c = np.zeros(nvars)
    integrality = np.ones(nvars, dtype=int)
    lb = np.zeros(nvars, dtype=float)
    ub = np.ones(nvars, dtype=float)
    bounds = Bounds(lb, ub)

    m = N + len(guesses)
    A = lil_matrix((m+1, nvars), dtype=int)  # +1 for the "forbid solution" constraint
    bl = np.zeros(m+1, dtype=float)
    bu = np.zeros(m+1, dtype=float)

    # position constraints
    for i in range(N):
        row = i
        for d in range(10):
            idx = i*10 + d
            A[row, idx] = 1
        bl[row] = bu[row] = 1.0

    # guess constraints
    for gi, g in enumerate(guesses):
        row = N + gi
        cnt = counts[gi]
        bl[row] = bu[row] = float(cnt)
        for i, ch in enumerate(g):
            d = ord(ch) - ord('0')
            idx = i*10 + d
            A[row, idx] += 1

    # forbid exact same solution: sum_{i} x_{i, sol[i]} <= N-1
    forbid_row = m
    for i, ch in enumerate(solution):
        d = ord(ch) - ord('0')
        idx = i*10 + d
        A[forbid_row, idx] = 1
    bl[forbid_row] = -np.inf
    bu[forbid_row] = N - 1  # force at least one position differ

    A = A.tocsc()
    lincon = LinearConstraint(A, bl, bu)
    res2 = milp(c, integrality=integrality, bounds=bounds, constraints=[lincon], options=options)
    # If res2.status == 2 (infeasible) then no other solution exists => unique
    return res2

# --- Example usage with the 1st sample ---
if __name__ == "__main__":
    guesses = ["90342","70794","39458","34109","51545","12531"]
    counts  = [2,0,2,1,2,1]
    sol, r = solve_with_scipy_milp(guesses, counts, allow_leading_zero=True,
                                  options={"presolve": True, "disp": False})
    print("solution:", sol)
    # uniqueness check
    if sol is not None:
        r2 = check_uniqueness(guesses, counts, sol, options={"presolve": True})
        if r2.status == 2:
            print("Unique solution confirmed (no other solution).")
        else:
            print("Another solution exists or solver returned feasible alternative; check r2.status:", r2.status)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Notes & tips

Binary vs integer: integrality=1 + 0 ≤ x ≤ 1 forces binary variables (0 or 1). We use that pattern above.

Objective: we used zero objective (c = 0) so solver finds any feasible integer solution. If you want a deterministic tie-breaker (not normally necessary) you can set a tiny lexicographic objective, but zero objective is fine.

Numerical tolerance: res.x is double; check using > 0.5 (or round) to decide which variables are chosen.

Performance: tiny problem sizes (e.g. N=16 => 160 variables) are trivial for modern MILP solvers; SciPy’s MILP will quickly find a solution.

Uniqueness test: after you get a solution, add the “forbid exact solution” constraint (sum chosen_vars ≤ N-1) and resolve. If result is infeasible, the solution is unique. (I included check_uniqueness above.)

Leading-zero rule: to forbid leading zero set ub[idx_for_pos0_digit0] = 0.

Solver options: you can pass options={'time_limit':..., 'node_limit':..., 'presolve': True}.

Caveats

SciPy’s milp is a wrapper around its internal MIP solver (IPX or HiGHS MIP backend depending on your SciPy version); it works fine on these sizes. If you need advanced tuning or best performance you can also use specialized MILP solvers (CBC, Gurobi, CPLEX, OR-Tools), but that’s unnecessary for typical puzzles.

Because the MILP is exact (integrality enforced), the solution is combinatorially exact; numerical rounding is only used to interpret the returned double vector.

If you like, I can:

produce a small runnable script that reads guesses from a file or stdin and prints the unique solution and verification, or

show the equivalent pulp or ortools encoding instead. Which do you prefer?