Problem Definition
Guess a secret code of 4 distinct colours from 6. After each guess, receive feedback: black peg = right colour, right position; white peg = right colour, wrong position. Goal: crack the code in as few guesses as possible.
Algorithm: Constraint Elimination
Inspired by Donald Knuth’s 1977 algorithm: (1) Generate all 360 possible codes. (2) Make a guess. (3) Receive feedback. (4) Eliminate all codes that wouldn’t produce the same feedback. (5) Pick the first remaining candidate. (6) Repeat until solved.
Information Theory
Each guess carries information. First guess eliminates ~82% of candidates (360 → ~65). By guess 3, most codes are nearly solved. Average: 4.15 guesses. Maximum: 6 guesses. Theoretical optimal (Knuth’s minimax): ≤5 guaranteed.
Two-Pass Feedback Scoring
Pass 1: Count exact matches (black pegs). Pass 2: Count colour matches (white pegs) using boolean arrays to prevent double-counting. This prevents a colour being scored as both exact and misplaced.
Key Insight
The simple “first candidate” strategy averages 4.15 guesses vs Knuth’s optimal 4.34 — counterintuitively, the simpler strategy has a better average because it’s optimistic, while Knuth’s minimax optimizes for worst-case.