Bulls and Cows

The computer hides a code of four different digits, 0 to 9 — a leading 0 is allowed, so 0123 is a code like any other. You type a guess of four different digits and press Enter, and it comes back scored: a bull for every digit that is right and in the right place, and a cow for every digit that is in the code but somewhere else. A digit is never both. Four bulls cracks the code; ten guesses without them and the code is shown.

Colours mode is the same game with four pegs from six colours — red, yellow, green, blue, purple and white — and repeats allowed, which makes 1,296 possible codes instead of 5,040. Every colour also carries its own shape, a dot, a triangle, a square, a diamond, a star or a cross, so no two pegs rely on colour alone.

Every opening of four different digits is the same position with the digits renamed, so the first guess is yours to choose freely — and the score it gets splits the 5,040 codes into groups of very different sizes. These are the exact counts for any opening, the same whether you start with 0123 or 9876.

Two things stand out. The likeliest first score is a single cow — 1,440 codes in 5,040 — and it tells you the least. And nothing at all is good news rather than bad: 0 bulls, 0 cows happens for 360 codes, and it rules out four of the ten digits in one go, leaving only codes built from the other six. One score never appears at all: three bulls and one cow is impossible, because if three digits are in place and the fourth is somewhere in the code, the only place left for it is its own.

In Colours a code can hold the same colour more than once, and so can a guess, which is exactly where careless scoring goes wrong. The rule is the min-count rule: for each colour, the number of matches is the smaller of how many that colour appears in the code and how many in the guess. Add those up over all six colours, and whatever is not a bull is a cow. Each peg of the code pays out once and only once, and a bull always takes its peg before a cow can.

The first row is the trap. A scorer that checks each peg of the guess against the code on its own sees two Reds that are both "in the code" and hands out three cows; the right answer is two, because the code has only one Red to give. In Numbers no digit repeats, so the same rule simply counts the digits that are in the code but out of place.

Press Hint and the board fills in a guess that fits every score so far — a code that could itself be the answer. Among all the codes that still fit, it picks the one expected to leave the fewest standing: it imagines playing each candidate, sorts the codes that remain by the score each would give it, and takes the candidate whose groups come out smallest on average. It never looks at the answer, which is what makes it fair to measure by letting it play every code there is.

Perfect play does a little better, and it is known exactly. In the four-digit game any code can be cracked within seven guesses, and the lowest possible average — found by Tetsuro Tanaka of the University of Tokyo in 1996 — is 26,274 guesses over the 5,040 codes, about 5.21 each. For six colours and four pegs, Donald Knuth showed in 1977 that five guesses always suffice, and Koyama and Lai found the lowest average in 1993: 5,625 guesses over the 1,296 codes, about 4.34. The hint gives away about a tenth of a guess to those results because it only ever proposes a code that could be the answer, where a perfect player will sometimes spend a guess on one that cannot, purely to split the field.

It is a pencil-and-paper game, and an old one — it may date back a century or more, played by two people who each write down a secret number and take turns guessing the other's. It was also one of the first games anybody played on a computer: in 1968 Frank King wrote a version called MOO for the Titan computer at Cambridge University, and in 1970 J. M. Grochow wrote another at MIT for the Multics operating system.

The coloured-peg form is a later boxed take on the same idea, with colours in place of digits and repeats allowed. This page plays both under the game's own traditional name, with the rules people played on paper. If you like reasoning from feedback about a hidden answer, Word Guess does it with letters and Minesweeper with numbers on a grid.