How to analyze a mastermind-like game using logical inferences

Question

---

DISCLAIMER: I am NOT looking for a solution to Mastermind.

---

I'm trying to write a program to solve a game like mastermind, and I'm a bit stuck. I don't want a full solution, only help with the part I can't get past. Here's the game:

There are N possible colors known in advance. There is an unknown set (possibly with repetitions) of k that are chosen and kept secret. The goal is to guess the colors (with repetitions) in the secret set. Let me emphasize again that this is a set, so order does not matter, but repetitions are allowed. For example

Colors are a,b,c,d,e,f,g,h (N=8) and unknown set is {a,c,c} (k=3).

Successive guesses are made that result in more information about the secret set. Each guess must be a set (repetitions allowed) of k colors. The response to each guess is the number of colors in common between the guess and the unknown set counting repetitions. For example

1. Guess: a,d,e Result: 1

2. Guess: b,c,f Result: 1

3. Guess: a,a,g Result: 1

4. Guess: a,c,h Result: 2

5. Guess: b,e,h Result: 0

The guesses are made by someone else. My objectives are:

- Determine when information about a particular color is known.

- Determine when the unknown set can be logically deduced.

At the start of the game, no colors are definitely in the set or definitely not in the unknown set (assuming N>1). After a guess that results in 0, all of the colors of that guess are known not to be in the unknown set. If the result is k, then all of the colors of that guess are known to be in the unknown set. I'm having trouble writing a program to figure out all the cases in between. For example, nothing is known for certain about any of the colors until the last guess above. After the last guess, the set is known to be a,c,c. The logic is this:

• By 5, b,e,h are not in the unknown set
• By 4, a,c are in the unknown set
• By 1, d is not in the unknown set
• By 2, f is not in the unknown set
• By 3, g is not in the unknown set
• Therefore the only colors in the unknown set are a and c.
• By 3, a is not in the unknown set more than once.
• Therefore the unknown set is a,c,c.

I can work through the logic this way, but I'm not sure how to program this in general. If someone could suggest a structured way to go about it, that would be great. I would prefer a high level explanation, with pseudo-code, rather than a full implementation in any one language. Thanks.

Answer 1

Straight-forward approach: Build the total population of possible combinations. Then, as guesses come in, remove the combinations that cannot possible satisfy the result for the current guess. Once you only have one combination left, that's the solution. Or, earlier in the process, when you no longer have a particular color represented then that one is (obviously) eliminated from the possible secret code.