For the game of Master Mind it has been proven that no more than five moves are required in the worst case.

One such algorithm was published in the Journal of Recreational Mathematics; in '70 or '71 (I think), which always solved the 4 peg problem in 5 moves. Knuth later published an algorithm which solves the problem in a shorter number of moves - on average - but can take six guesses on certain combinations.

In 1994, Kenji Koyama and Tony W. Lai found, by exhaustive search
that *5625/1296 = 4.340* is the optimal strategy in the expected
case. This strategy may take six guesses in the worst case.
A strategy that uses at most five guesses in the worst case
is also shown. This strategy requires *5626/1296 = 4.341* guesses.

* Donald E. Knuth.* ** The Computer as Master Mind.** * J. Recreational Mathematics,* 9 (1976-77), 1-6.

* Kenji Koyama, Tony W. Lai.* ** An optimal Mastermind Strategy.** * J. Recreational Mathematics,* 1994.

Fri Feb 20 21:45:30 EST 1998