Bulls and Cows (called Hit & Blow in Japan) is a perfect puzzle for a computer to solve. The idea is very simple: write out every possible answer, then cross off the ones that contradict the clues.

The idea

  1. Make every possible answer (5040 of them for 4 digits).
  2. Pick one candidate and guess it.
  3. Look at the hits and blows you got. For each candidate, check: “If this were the answer, would it give the same hits and blows?” Cross off the ones that would not.
  4. Repeat steps 2 and 3 until you get it right.

The key is step 3: keep only the candidates that would give the same clue. It is the same reasoning a person does in their head, applied mechanically to every candidate.

The program

Written in JavaScript, it looks like this. You can run it in your browser’s developer tools or with Node.js on a computer.

// Count the hits and blows
function judge(answer, guess) {
  let hit = 0, blow = 0;
  for (let i = 0; i < guess.length; i++) {
    if (guess[i] === answer[i]) hit++;
    else if (answer.includes(guess[i])) blow++;
  }
  return [hit, blow];
}

// Make every row of all-different digits
function allCodes(digits, prefix = '') {
  if (prefix.length === digits) return [prefix];
  const list = [];
  for (const d of '0123456789') {
    if (!prefix.includes(d)) list.push(...allCodes(digits, prefix + d));
  }
  return list;
}

// Keep guessing the first candidate that fits the clues
function solve(answer) {
  let candidates = allCodes(answer.length);
  for (let turn = 1; ; turn++) {
    const guess = candidates[0];
    const [hit, blow] = judge(answer, guess);
    console.log(turn, guess, hit, blow, candidates.length);
    if (hit === answer.length) return turn;
    candidates = candidates.filter((c) => {
      const [h, b] = judge(c, guess);
      return h === hit && b === blow;
    });
  }
}

solve('4719');
  • judge counts the hits and blows from an answer and a guess. Because all the symbols are different, you can count it as “a hit if the place matches, otherwise a blow if the symbol is in the answer.”
  • allCodes makes every row of all-different digits.
  • solve guesses the first candidate, keeps only the candidates that would give the same clue, and repeats.

The output

When the answer was “4719”, it printed this (from the left: guess number, guess, hits, blows, and the number of candidates before the guess).

1 0123 0 1 5040
2 1456 0 2 1440
3 2547 0 2 369
4 3674 0 2 80
5 4268 1 0 15
6 4395 1 1 6
7 4719 4 0 1

The candidates shrank from 5040 to 1440, 369, 80, 15, 6 and finally 1, and the program got it on guess 7. When we let this program solve all 5040 possible answers, the average was about 5.56 guesses, and the worst answer took 9.

Solving it in fewer guesses

This program always guesses “the first candidate.” If you choose your guesses more carefully, you can cut down the number of guesses.

  • Pick a guess that splits what is left well: For each possible guess, count how the answer candidates would split across the possible clues. Then choose the guess that makes the biggest leftover group smallest, or the one that makes the average leftover smallest.
  • Use rows that are not candidates, too: Even a row you already know is wrong can pay off if it splits the candidates well.

With these tricks, 4 digits can be solved in 7 guesses or fewer for every answer, with an average of about 5.3 (Is There a Winning Strategy for Bulls and Cows?). The catch is that each guess means checking a huge number of combinations, so the computation takes longer.

The app’s Hint works the same way

The Hint in the app “Bulls and Cows” also counts every candidate answer that does not contradict the clues so far, and shows one thing in this order:

  1. If some slot has the same symbol in every candidate, it tells you that slot.
  2. If some symbol is in none of the candidates, it tells you that symbol.
  3. If neither applies, it reveals one slot of the answer.

(How to Use the Hint)

If you would like to build a game yourself, see How to Make a Number-Guessing Game too.