Guess the Word: Minimax Elimination Strategy

You are given a list of 6-letter words and access to a Master API. The API has a .guess(word) method that returns how many characters in your guess match the secret word at the exact same position. You get at most 10 guesses to find the secret. This is LeetCode 843: Guess the Word, rated hard. The trick is not just guessing, but guessing strategically to eliminate as many candidates as possible each round.

The problem

You are given a word list words and a Master object. Calling master.guess(word) returns an integer from 0 to 6 representing how many characters in word match the secret word at the exact same positions. You must find the secret word in at most 10 calls to master.guess.

Input:  words = ["master","monkey","muster","market","mashed","mocker"], secret = "master"
Output: (found in at most 10 guesses)

The catch: the API only tells you the count of positional matches, not which positions matched. You need to use that count to narrow down the possibilities.

The key insight: maximize elimination with minimax

A naive approach would be to guess random words from the list and filter. That works sometimes, but can fail when the word list does not shrink fast enough. The problem gives you only 10 guesses, and the list can have up to 100 words.

The better approach is to pick each guess deliberately. For every possible guess, imagine what happens for each possible match count (0 through 6). The words in the candidate list split into groups based on how many characters they share with the guess at the same positions. Some guesses create more balanced splits than others.

Think of it like the game 20 Questions. You want each question to cut the remaining possibilities roughly in half. A question like "is it an animal?" is much better than "is it a golden retriever?" because it eliminates more options regardless of the answer.

Here, each guess is a "question," and the match count is the "answer." A good guess is one where no single match count leaves too many candidates alive.

The approach step by step

1. Start with all words as candidates
2. For each candidate, simulate guessing it: count how many other candidates fall into each match-count group (0 through 6)
3. Pick the candidate whose largest group is the smallest (minimax)
4. Call master.guess with that word
5. If you get 6 matches, you found the secret
6. Otherwise, filter candidates to only those with the same match count against your guess
7. Repeat until found

The code

def findSecretWord(words: list[str], master) -> None:
    def match_count(w1: str, w2: str) -> int:
        return sum(a == b for a, b in zip(w1, w2))

    candidates = words[:]

    for _ in range(10):
        best_guess = candidates[0]
        best_max_group = len(candidates)

        for word in candidates:
            groups = [0] * 7
            for other in candidates:
                groups[match_count(word, other)] += 1
            max_group = max(groups[i] for i in range(7) if groups[i] > 0)
            if max_group < best_max_group:
                best_max_group = max_group
                best_guess = word

        matches = master.guess(best_guess)
        if matches == 6:
            return

        candidates = [w for w in candidates if match_count(w, best_guess) == matches]

The match_count helper compares two words character by character and counts exact positional matches. This is the same thing the Master API does internally, but we use it locally to simulate outcomes and filter candidates.

The outer loop runs at most 10 times, matching the guess limit. Inside, we evaluate every candidate as a potential guess. For each one, we build an array of 7 buckets (match counts 0 through 6) and count how many other candidates fall into each bucket. The "score" for a guess is the size of its largest bucket. We pick the guess with the smallest such score.

After guessing, if the result is not 6 (a perfect match), we filter the candidate list down to only words that would produce the same match count against our guess. This is the key filtering step: if master.guess("market") returns 2, then the secret must have exactly 2 characters matching "market" at the same positions. Any candidate that does not have exactly 2 matches with "market" cannot be the secret.

Step-by-step walkthrough

Complexity analysis

Time: For each of the (at most) 10 guesses, we evaluate every candidate against every other candidate. With n candidates, that is O(n^2) per round. Since n shrinks each round, the total work is bounded by O(10 * n^2) where n is the initial list size.

Space: We store the candidate list (O(n)) and a small fixed-size groups array (7 entries). Total: O(n).

The building blocks

Elimination-based search

The core pattern here is maintaining a candidate set and narrowing it based on feedback from each query. You see this same idea in binary search (each comparison eliminates half the array), in Wordle-style games, and in constraint satisfaction problems.

def eliminate(candidates, guess, match_result):
    return [w for w in candidates if match_count(w, guess) == match_result]

The filtering step is simple on its own. The hard part is choosing the right guess to maximize how much you eliminate.

Minimax decision making

The minimax principle comes from game theory. You assume the worst case and optimize for it. Here, the "adversary" is the unknown secret word. For each possible guess, you look at the worst-case scenario (the largest group of remaining candidates for any match count) and pick the guess that makes that worst case as small as possible.

This pattern appears in any problem where you must make decisions under uncertainty and want to guarantee progress regardless of the outcome.

Edge cases

• Single word: if the list has only one word, guess it immediately. The minimax loop still works because it picks the only candidate.
• All words identical match counts: if every candidate has the same match count against every other candidate, minimax cannot help. This is rare with 6-letter words but theoretically possible. Random guessing with filtering still works within the 10-guess limit for the problem constraints.
• Match count of 0: getting 0 matches is still useful information. It eliminates every word that shares any positional character with your guess.
• Large word lists: with 100 words, the O(n^2) selection is still fast (10,000 comparisons per round). The 10-guess limit is sufficient because minimax cuts the list aggressively.
• Duplicate words in the list: the problem guarantees unique words, but the algorithm handles duplicates naturally since they would always have 6 matches with each other.

From understanding to recall

You now understand how Guess the Word transforms into an elimination problem where each guess is chosen to minimize worst-case remaining candidates. The minimax selection loop, the match counting, and the filtering step all fit together cleanly.

But the details matter under pressure. Remembering to use 7 buckets (0 through 6 matches). Getting the filtering condition right (match_count(w, best_guess) == matches, not !=). Knowing to break early when matches == 6. These small decisions add up, and getting any of them wrong means a failed attempt.

Spaced repetition turns this into muscle memory. You practice the minimax guess selection and the filtering step at increasing intervals until the pattern flows without hesitation. After a few rounds, you see "guess with limited attempts" and your hands just write the elimination loop.

Related posts

• Open the Lock - BFS search through a state space with constraints
• Word Search - Backtracking through character grids
• Design Add and Search Words - Trie-based pattern matching with wildcards

Guess the Word is a great example of how game theory concepts like minimax apply to algorithm problems. The elimination strategy is elegant: pick the guess that guarantees the most progress, filter based on feedback, and repeat. CodeBricks drills this pattern with spaced repetition so it becomes second nature when you encounter similar interactive or adversarial problems.