Bulls and cows solver

How bulls and cows works

One player picks a secret code, usually four different digits. The other player guesses, and every guess gets two numbers back:

• Bulls: digits that are in the code and in the right place.
• Cows: digits that are in the code but in the wrong place.

Say the secret is 5940 and you guess 1234. The 4 is in the code but in the wrong place, so that's 0 bulls and 1 cow. Nothing else in the guess is in the code at all.

It's an old pencil and paper game, and it's the same idea as the board game with colored pegs, just with digits. Lock riddles you see online (the ones with a padlock and five clues) and my game Crack the Vault use it too, only worded differently: "two digits are in the code, one of them in the right place" means 1 bull and 1 cow.

The settings matter

The same clues can point to different codes depending on the rules you play by, so set these first:

• Digits in the code. Three, four or five.
• Digits can repeat. The classic game says no, every digit is different. Some versions allow codes like 7337. With repeats, each digit in your guess is matched at most once: if the code has one 3 and you guess two, only one of them can score.
• Code can start with 0. Usually yes. Turn it off if your game uses real numbers like 1024 and never 0124.

With four different digits and a leading zero allowed there are 5,040 possible codes. Allow repeats and that jumps to 10,000. Ban the leading zero (without repeats) and it drops to 4,536.

A worked example

Here's a real game against the secret 5940, with the count of codes that still fit after each guess. The solver above gives exactly these numbers if you type the same clues.

Guess 1, 1234: 0 bulls, 1 cow. Exactly one of 1, 2, 3 and 4 is in the code, and it isn't where we put it. That alone cuts 5,040 codes down to 1,440.

Guess 2, 5678: 1 bull, 0 cows. One of 5, 6, 7 and 8 is in the code and already in the right place, and the other three aren't in it at all. Two guesses in, only 72 codes are left.

Guess 3, 0179: 0 bulls, 2 cows. This is the guess the solver suggests here, and so are guesses 4 and 5. It's one of the 72 codes that still fit, but that isn't why it was picked. A good guess is the one that splits the remaining codes into the smallest groups, whatever the answer turns out to be. After it, 25 codes are left.

Guess 4, 2098: 0 bulls, 2 cows. Now just 4 codes fit: 5903, 5940, 9603, 9640.

Guess 5, 5903: 2 bulls, 1 cow. That leaves 5940, 9603. One more guess settles it, and 5940 gets 4 bulls.

After guess 5 only two codes were left, so one or two more guesses had to finish it. Here the first of the two was right.

How the next guess is picked

When 800 or fewer codes are left, the solver tries each of them as a guess. For every possible secret it works out the bulls and cows that guess would get, groups the secrets by answer, and looks at the biggest group. It suggests the guess whose biggest group is smallest.

With more than 800 codes left it doesn't suggest anything yet, because early on almost any guess with digits you haven't tried is fine. Below that, the promise is modest and exact: whatever the real code is, that guess leaves at most the number of codes it shows. It isn't always the guess that finishes fastest, and it only picks from codes that still fit, which keeps it honest when you're playing a game that requires sensible guesses.

When no code fits

If the list goes empty, one of the clues is wrong or the settings don't match the game. The solver points to the first guess where the codes run out. That guess is part of the problem, but the mistake can sit in any clue above it, so check them in order. The usual suspects:

• Bulls and cows swapped on one guess.
• A repeated digit in the code while "Digits can repeat" is off.
• A typo in a guess, like 1243 instead of 1234.

Questions