Master Mind, Part 2

November 20, 2009

In the previous exercise we wrote a Master Mind setter. In today’s exercise we will write a solver, using an algorithm given by Donald E. Knuth in his article “The Computer As Master Mind” in Volume 9, Number 1, the 1976-1977 edition, of The Journal of Recreational Mathematics.

The central concept of Knuth’s algorithm is the pool of potential solutions. His algorithm chooses at each step a probe that minimizes the maximum number of remaining possibilities over all possible response of the codebreaker; in the event of a tie, any pattern that achieves the minimum may be used, subject to the condition that a probe that is a member of the current pool is preferred to one that is not.

For instance, consider the pool of 1296 possible code words at the start of a puzzle. There are essentially five possible starting probes: 1 1 1 1, 1 1 1 2, 1 1 2 2, 1 1 2 3, and 1 2 3 4 (rotations are excluded, as are variants that substitute one symbol consistently for another). The remaining pool sizes after each of the five probes is applied to all of the 1296 possible code words are given in the table below:

  1111 1112 1122 1123 1234
.... 625 256 256 81 16
W... 0 308 256 276 152
B... 500 317 256 182 108
WW.. 0 61 96 222 312
BW.. 0 156 208 230 252
BB.. 150 123 114 105 96
WWW. 0 0 16 44 136
BWW. 0 27 36 84 132
BBW. 0 24 32 40 48
BBB. 20 20 20 20 20
WWWW 0 0 1 2 9
BWWW 0 0 0 4 8
BBWW 0 3 4 5 6
BBBB 1 1 1 1 1
max 625 317 256 276 312

The minimax solution is 256, achieved when the probe is 1 1 2 2, so that should always be the first probe. Then the solution is determined by making the minimax probe, reducing the pool by applying the result of the probe, and repeating on the reduced pool until the puzzle is solved.

Your task is to write a Master Mind solver based on the rules set out in the previous exercise and Knuth’s algorithm given above. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

2 Responses to “Master Mind, Part 2”

  1. [...] about Programming from google blogs as of November 21, 2009 Master Mind, Part 2 « Programming Praxis – programmingpraxis.com 11/21/2009 Programming Praxis. A collection of etudes, updated [...]

  2. daniel said

    can i see the answer?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: