## Word Bulls & Cows

### Strategy

A simple strategy is to make each guess consistent with the answers you've been given so far. Thus your guess will either be the correct word, or one of the possible candidates for the correct word, and each guess will bring you closer to the correct word.

This is usually a pretty good strategy, but it can be very inefficient if you get a large number of hits early in the game. For example, suppose the guesses and answers have been:

- Guess: "WORK" - Answer: 0 Bulls, 0 Cows
- Guess: "WELL" - Answer: 3 Bulls, 0 Cows

From this we can deduce that the word must end in "ell", and so can be one of these eight candidates:

BELL, CELL, DELL, FELL, HELL, SELL, TELL, or YELL.

Using the simple strategy we might guess "BELL", but it could take up to six more guesses to get the word. We have seven chances in eight that we'll be left with seven candidates, making:

7/8 * 7 = 49/8 = 6.125 candidates remaining (on average).

A better strategy is to try and eliminate as many candidates as possible with a guess such as "CYST". Although this can't be the correct answer, it divides the candidates with the following possible answers:

- 0 Bulls, 0 Cows - Candidates left: BELL, DELL, FELL, HELL
- 0 Bulls, 1 Cow - Candidates left: SELL, YELL, TELL
- 1 Bull, 0 Cows - Candidates left: CELL

So there are four chances in eight that you'll be left with four candidates, three chances in eight you'll be left with three candidates, and one chance in eight you'll be left with one candidate, making:

(4/8 * 4) + (3/8 * 3) + (1/8 * 1) = 26/8 = 3.25 candidates remaining (on average).

This shows that "CYST" is nearly twice as good as "BELL" for the next guess.

When playing Word Bulls & Cows you can eliminate letters as efficiently as possible by guessing a series of words with no letters in common. My favourite set of words for four-letter Bulls & Cows is:

MYTH, DUCK, VERB, GASP, JINX, and WOLF.

which use 24 of the 26 letters. The best I've come up with for five-letter Bulls & Cows is:

BLACK, FIGHT, JUMPY, DROWN, and VEXES

which use 24 of the 26 letters with one letter repeated. If anyone can find five five-letter words with no letters in common I'd be interested to know.