How to Win at Bulls and Cows

There is an old folk logic game. It is called bulls and cows. It is also called mastermind.

in mastermind instead of numbers - colors — **in mastermind** instead of numbers – colors

The rules are simple:

The host thinks up a random secret 4-digit number with unique digits. The player makes attempts to guess the number. An attempt is a 4-digit number with unique digits, which is given to the host. The host gives hints on how many digits were guessed without matching their positions in the secret number (number of cows) and how many were guessed up to the position in the secret number (number of bulls). For example:

The secret number “3219” was conceived. Attempt: “2310″.

Result: two “cows” (two numbers: “2” and “3” – guessed in incorrect positions) and one “bull” (one number “1” guessed right up to the position).

The winner is the one who guesses the number in the fewest moves.

In this text I would like to present my algorithm for finding a solution to this game. I called this method: matrix of possible solutions.

For the sake of certainty, let's say there is a variant of the game from a three-digit number. For four-digit numbers, the essence is the same. I will show the essence of the algorithm in a particular form, that is, by example.

Preparation

The first thing you need to do is draw a table of options like this. This is the matrix of possible solutions. Initially, it is empty. It lists which numbers can be in hundreds, which in tens, and which in units.

That is, the table shows what numbers can be in each digit. To fill the table, you need to make moves.

Move #1: Option 123 – Hint: 2 cows

Hints like zero bulls and several cows are simply a gift from fate, since you can safely blur as many as three cells in the decision matrix. Now this means that 1 is not a bull 2 is not a bull 3 is not a bull

Move #2: 298 – Hint: 1 cow

This means that 2, 9 and 8 are not bulls. It covers up these cells in the decision matrix.

Move #3: 354 Hint: 2 cows

This also means that 3 5 4 are not bulls. We cover up these cells in the matrix.

Move #4: 532- hint: 2 bulls

When bulls appear, there is no need to cover anything up in the table. But hypotheses should be made based on possible combinatorics.

In this case, all the information is present to win. When there is a hint of 2 bulls, then three hypotheses must be tested. One will remain and two will be refuted.

1. Hypothesis: Bulls are 53_ (spoiler: wrong)

Then 2 is not in the number. Then 1 3 are also cows. That is, the number should contain the numbers 1 3 5. However, the second clue says that there is a fourth number different from 1 3 5. Contradiction. The hypothesis is invalid.

3. Hypothesis: Bulls are 5_2 (spoiler: wrong)

Then there is no 3 in the number. Based on the move 3, then there are 1 2 4 5 . But these are 4 numbers! Too many. Contradiction.

2. Hypothesis: bulls are _32 (spoiler: correct)

Then 5 is not in the number. So there is also 4 in the number. So there is no 1, 9, 8 4 5 . There is not a single clue that would violate the hypothesis. The answer is 432.