Cracking Number Puzzles with Constraint Satisfaction

Imagine someone writes a three-digit code on a piece of paper and puts it in a sealed envelope. You cannot see the code. But you are allowed to make statements about guesses: “one digit is correct and in its place,” “two digits are present but misplaced,” and so on.

Can you recover the code without guessing randomly?

The viral crack the password puzzle is a particularly good example because it looks like a collection of unrelated clues. Underneath, however, all five sentences are instances of one mathematical operation. Once we identify that operation, we can stop writing complicated case distinctions and start thinking clearly about what information means.

There are two versions of the viral picture, one handwritten on blue and one as a gray lock graphic. Both describe exactly the same five clues: 682, 614, 206, 738, 380. We interpret the statements as exact counts, not lower bounds. “One digit is right” means exactly one, and the other two are not in the secret. We also allow a leading zero, so 042 is a valid three-character code.

The goal is not to teach a computer five special rules. It is to find a representation in which all five rules become the same kind of thing.

1. Begin with everything that could be true

A code has three positions. At each position we can independently choose one of ten symbols, 0 through 9. The multiplication principle gives

\[ |\Omega| = 10\cdot 10\cdot 10 = 10^3 = 1000. \]

Here \(\Omega\) denotes the universe of possible secrets. It includes 000, 001, …, 042, …, 999. It is important to use strings rather than numbers: the number 42 and the code 042 are not the same representation.

For now, imagine all 1,000 secrets spread out like a field of dots. Every new clue paints some dots gray because those codes are impossible. The survivors are the codes consistent with everything we have learned.

The key idea is simple: each clue filters a set of possible codes. We do not need to find the secret directly. We discard candidates that contradict an observation. One survivor means the answer is unique; several mean the puzzle is underdetermined; none mean the clues conflict or the rules need revisiting.

2. What does it mean for two codes to match?

We need to distinguish two ways a guessed symbol can be correct. Consider the hidden code 042 and the proposed guess 206.

The guess contains the correct symbols 2 and 0, but neither sits in the correct position. The 6 does not occur at all. So we should report

\[ F(\texttt{042},\texttt{206})=(0,2). \]

The first coordinate \(E\) counts exact matches: symbol and position are both right. The second coordinate \(W\) counts misplaced matches: the symbol occurs in the secret, but it was used in a different slot.

This ordered pair \(F(s,g)=(E,W)\) is the feedback function. It contains everything we need to model the five hints. In particular, a feedback value (1,0) means exactly one correct position and zero additional matching digits. Checking only “at least one correct position” would be an incorrect interpretation.

Why repeated digits require care

Suppose the secret is 0012, while the guess is 0000. There are two exact zeroes. The two extra guessed zeroes are not additional matches, because only two zeroes actually exist in the secret.

It is tempting to count distinct symbols with a set: “Does the guess contain a zero?” But a set forgets how many copies there are. We need a multiset—a set with multiplicities.

Let \(c_s(d)\) be the number of occurrences of digit \(d\) in the secret, and \(c_g(d)\) its count in the guess. The total number of matched symbols, disregarding positions, is

\[ T(s,g)=\sum_{d\in\{0,\ldots,9\}}\min(c_s(d),c_g(d)). \]

Why the minimum? Because we can match only as many copies as the smaller pile contains. If the secret has two copies of 0 and the guess has four, then \(\min(2,4)=2\) matches. After counting exact positions separately, misplaced matches are whatever remains:

\[ E(s,g)=\sum_{i=1}^{L}[s_i=g_i],\qquad W(s,g)=T(s,g)-E(s,g). \]

The square brackets denote an indicator: \([P]\) is 1 when proposition \(P\) is true and 0 otherwise. There is no magic in these equations. They merely formalize counting what you can match and not counting the same symbol twice.

The same formula works for numbers, colored Mastermind pegs, letters and almost any fixed-length code with repeated symbols. The choice of symbols is irrelevant; the equality relationships are what matter.

3. Translate every sentence into the same language

Our five observations can now be written as five equations:

No new logic is necessary for the third hint, even though it originally looks much more complicated than the others. “Two right, both in the wrong place” simply means (0,2).

If the \(i\)-th guess is \(g_i\) and the corresponding observation is \(r_i\), define its consistent set

\[ C_i=\{s\in\Omega:F(s,g_i)=r_i\}. \]

A secret must satisfy all hints, not just one. Therefore, the solution set is the intersection

\[ S=C_1\cap C_2\cap C_3\cap C_4\cap C_5. \]

Or, if you prefer to process clues one after another, start with \(S_0=\Omega\) and repeatedly apply

\[ S_{t+1}=\{s\in S_t:F(s,g_t)=r_t\}. \]

This is a constraint satisfaction problem (CSP): find assignments to the variables (the three code positions) for which every constraint is true.

The exact survivor counts in that figure are computed from the solver, not invented for illustration. Starting with 738 removes all codes containing 7, 3 or 8, leaving \(7^3=343\). The remaining rules progressively reduce the count to 78, 13, 5 and finally 1.

4. Solve it by hand: understanding beats enumeration

A computer can inspect all 1,000 codes in milliseconds. But doing the deduction by hand reveals why the answer is inevitable.

Let’s walk through the reasoning without trying combinations blindly.

Clue 738: none of these digits appear. So the code has no 7, no 3 and no 8.

Clue 380: exactly one digit is present, and it is misplaced. Since 3 and 8 are absent, the present digit must be 0. Because 0 occurs in the third position of the guess, it cannot occupy the third position of the secret.

Clue 206: two of these digits are present, both misplaced. We already know that 0 is present. In this guess it occupies the second position, so the true 0 cannot be in position two either. With positions two and three eliminated, 0 must be first.

Clue 682: exactly one digit is correct and in its place. The 8 is excluded by the first clue. The 6 cannot be in the first position, which is already 0. Therefore the 2 must be in the third position, and 6 is not present. We have 0 _ 2.

Clue 614: exactly one digit is present but misplaced. Since 6 is absent, we must choose between 1 and 4. The only empty slot is the second. But 1 is in the second slot of the guess, where it is supposed to be misplaced. Therefore the missing digit is 4.

The unique code is 042.

Notice that this proof is not simply “the computer says so.” Every step follows from a specific, testable constraint. In fact, it gives an independent way to check the implementation.

5. Write the solver—without special-case logic

We can implement the entire feedback function in JavaScript using two frequency maps and a count of exact positions. The key is to keep this one scoring rule separate from the search: the same function can then power a puzzle solver, a Mastermind strategy, or a feedback checker.

function feedback(secret, guess) {
    let exact = 0;
    const inSecret = new Map();
    const inGuess = new Map();

    for (let i = 0; i < secret.length; i++) {
        if (secret[i] === guess[i]) exact++;
        inSecret.set(secret[i], (inSecret.get(secret[i]) || 0) + 1);
        inGuess.set(guess[i], (inGuess.get(guess[i]) || 0) + 1);
    }

    let total = 0;
    for (const [digit, n] of inSecret)
        total += Math.min(n, inGuess.get(digit) || 0);

    return [exact, total - exact];
}

And now the whole viral puzzle becomes a few lines of data and a generic predicate:

const clues = [
    ['682', [1, 0]],
    ['614', [0, 1]],
    ['206', [0, 2]],
    ['738', [0, 0]],
    ['380', [0, 1]],
];

const survivors = [];
for (let n = 0; n < 1000; n++) {
    const secret = String(n).padStart(3, '0');
    const consistent = clues.every(([guess, expected]) =>
        JSON.stringify(feedback(secret, guess)) ===
        JSON.stringify(expected)
    );
    if (consistent) survivors.push(secret);
}
console.log(survivors); // ['042']

This algorithm takes \(O(|\Omega|\,mL)\) comparisons for \(m\) hints and code length \(L\), apart from small bookkeeping factors for symbol counts. At 1,000 candidates and five hints, it is effectively instantaneous. An elaborate SAT solver or clever recursion would solve a problem we do not yet have.

Inspect your own candidate

The following interactive checker compares any three-digit candidate against all five pieces of evidence. It illustrates a useful debugging habit: when a solver rejects a candidate, ask which exact constraint rejected it.

6. How do you know a solution is unique?

Solving for one code is not enough to establish that no second code also fits. A proof of uniqueness requires either a complete deduction or a complete search over the declared universe.

Our solver reports three qualitatively different outcomes:

• \(|S|=0\): inconsistent observations. No possible secret explains them all.
• \(|S|=1\): uniquely determined secret.
• \(|S|>1\): ambiguous puzzle. More information is needed.

This immediately suggests a general-purpose puzzle constructor: invent a secret, generate candidate clues about it, and keep only clue collections whose survivor set contains exactly one code. But there is another, subtler question: do we need every clue?

For this particular viral puzzle, we don’t. The first three clues in the original ordering—682, 614, and 206—already select 042 uniquely! The last two clues, 738 and 380, help a human follow the reasoning, but they are not logically necessary for uniqueness. In fact, removing either one individually still leaves the same unique solution, and removing both still leaves 042.

That distinction is excellent material for puzzle design: a clue may be redundant for the final answer yet useful for making the explanation intuitive. A minimal constraint set and a pedagogically good constraint set need not be identical.

7. The information in an elimination

Suppose we begin with 1,000 equally plausible codes. Before seeing any evidence, we would need \(\log_2(1000)\approx9.97\) bits to identify one code. Why logarithms? Because each ideal yes/no answer can at best halve the possibilities; after \(b\) ideal binary answers we can distinguish \(2^b\) possibilities.

If a clue leaves \(k\) equally plausible candidates, the uncertainty remaining is \(\log_2 k\) bits. The information gained along this observed path is therefore

\[ I_{\mathrm{observed}} = \log_2\frac{|S_{\mathrm{before}}|}{|S_{\mathrm{after}}|}. \]

For the clue 738, this is \(\log_2(1000/343)\approx1.54\) bits. This does not mean every possible answer to the guess 738 would be equally informative. The observed answer happens to eliminate a particular fraction of hypotheses. In the next article we will distinguish information from one actual answer and the expected information of a question before we ask it.

8. A Bayesian view: from possibilities to beliefs

So far every surviving code has been treated equally. That assumption is appropriate if the secret was sampled uniformly by a computer. But imagine the code was chosen by a person, and you suspect familiar patterns are more likely than strange ones. Or imagine some reported clues might contain mistakes.

We can assign a probability \(P(s)\) to each possible secret. A new observation \(r\) to a guess \(g\) updates it according to Bayes’ rule:

\[ P(s\mid r,g)=\frac{P(r\mid s,g)P(s)}{\sum_{u\in\Omega}P(r\mid u,g)P(u)}. \]

Break the equation into familiar pieces: \(P(s)\) is your prior belief; \(P(r\mid s,g)\) says how likely this report would be if that secret were true; the denominator simply rescales everything so the new probabilities add up to one.

When feedback is perfectly trustworthy, the likelihood \(P(r\mid s,g)\) is 1 for a matching code and 0 for a contradiction. Bayes’ rule then does exactly what our constraint solver does: delete impossible codes and renormalize the rest. Hard constraint filtering is Bayesian inference with a noiseless observation model.

If the reporting process can make mistakes, a contradictory secret need not have probability exactly zero. Consider two hypotheses, 042 and 012. The clue 614 → (0,1) supports 042, while the same guess would produce (1,0) for 012. Under a simple binary-symmetric reporting model with reliability \(q\), the likelihoods for the observed report are \(q\) and \(1-q\) respectively. Starting with prior probabilities \(0.75\) and \(0.25\), and \(q=0.90\), we obtain

\[ P(\texttt{042}\mid\text{reported clue}) =\frac{0.75\cdot0.90}{0.75\cdot0.90+0.25\cdot0.10} \approx0.9643. \]

The code is now more credible but not logically certain. Change the assumptions yourself:

A warning matters here: this toy two-hypothesis model deliberately ignores all other codes, and the binary noise model is an illustration rather than a claim about the viral image. The full Bayesian solver supports arbitrary priors and explicit likelihood functions, including independent slot-level noise for RAW Codebreaker feedback.

9. From passive deductions to active experiments

The final distinction is the bridge to the second article. In this puzzle, we were given five experiments and their outcomes. We had no choice about which guess came next. We merely found the secret that explained all observations.

But suppose the envelope is still sealed and you can choose your next guess. Should you try 000, 012, 682, or something that might not even be a possible secret? How can you choose a guess that forces the most useful answer, regardless of what the answer turns out to be?

That question changes the nature of the algorithm. The constraints remain exactly the same, but now we must design the next observation. This is the central idea of Mastermind, active learning and experimental design.

References

• [Knuth1976]Knuth, D. E. (1976–77). “The Computer as Master Mind.” Journal of Recreational Mathematics, 9(1). Paper.

All counts displayed in the interactive exercises are derived from the actual solver. The original viral image is a puzzle illustration, not an authoritative mathematical specification: our exact-count and repeated-digit conventions are stated explicitly above.