Excel challenge: Mastermind

Since the readership for this blog skews heavily toward Excel nerds, I’m going to post an Excel challenge here once in a while. This is the first one, and it comes in three parts, in increasing order of difficulty (I encourage you to have a go even if you don’t think you can do the whole thing).

The challenge is based on Mastermind, a 2-player board game. In the game, one player (the ‘code maker’) chooses a pattern of 4 colors from 6 possibilities (with repetition allowed, e.g. blue, green, blue, red). To keep things simple here, I’ll write each code as a number with the digits 1-6, e.g. 6241.

The second player, the ‘code breaker’ has to guess the pattern, including the order of the colors. They do this by guessing a series of patterns, for which the code maker gives them a score.

The score comes in the form of black and white pegs: the number of black pegs is the number of positions in which the guess and the code exactly match, and the total number of pegs (black and white) is the highest number of positions in which they could match if the guess was rearranged. Some examples should clarify.

Ex 1: code 1111, guess 1122, scores 2 black pegs (the first 2 positions match) and no white pegs (because the score couldn’t be made any higher by rearranging)

Ex 2: code 1234, guess 1243, scores 2 black (first 2 match) and 2 white (because the last 2 could be rearranged to match)

Ex 3: code 1234, guess 1323, scores 1 black (first position matches) and 2 white (because rearranging the guess could add 2 more exact matches)

Ex 4: code 1231, guess 6455, scores 0 (no matches)

Part 1: Scoring formula

Given 4 cells with the code, and 4 cells with a guess, can you come up with some Excel formulas to determine the score of the match? One cell should return the number of black pegs, and another should return the number of white. You can use other cells to store intermediate workings (for example, you might want to have a cell that checks if the first cell in the code matches the first cell in the guess, and repeat for the 2nd, 3rd, and 4th, before summing them up).

If you want an extra challenge, try one of these:

1. Can you write the formula with no helper cells? In other words, the only cells you would put formulas in would be the cell to return the number of black, and the cell to return the number of white. (I think this is possible, but I haven’t tried yet.)
2. Can you write the formula (with as many helper cells as you need) without using any Excel functions? Arithmetic operations (+, -, *, /) are allowed, but nothing where you have to write a function name, like INDEX, MID, MAX, etc.

You can use the template in the attached spreadsheet, which is currently set up to generate a random code and a random first guess for you to compare, or just start on a clean new sheet…

Spreadsheet: Mastermind

Part 2: Solve the game

Once you’ve written the scoring, you can actually play the game. Have someone (or yourself as long as you don’t peak!) fill in random digits for the code and hide the row, then make your guesses, and see how many it takes you to crack the code (you’ll know you’ve got it when you score 4 black).

The next challenge is to try to find the formulas you need to have Excel solve it for you. In other words, write formulas that will fill in the guess fields until you find an exact match for the code.

If you’re not a mathematician / computer scientist, that might sound a bit strange – so let me give you an example of a simple series of rules that you could implement in Excel that would solve the game:

1. First, guess 1111, 2222, 3333, 4444, and 5555. Based on the results of these, you know exactly how many of every color you have (for 1-5, it’s the black score for that guess, and for 6 it’s whatever number you need to bring the total up to 4).
2. Next, pick one number you know is in the code (let’s say 3) and one number you know is not (let’s say 4), and guess 3444, 4344, and 4434. The 4s will score nothing, and the 3 will score 1 white if it’s in the wrong place, and 1 black if it’s in the right place, so if you get any blacks you can place the 3, and if you don’t get any it has to be in the last position (the only one you haven’t tried).
3. Now pick another number you know is in (let’s say 5) and the same number you know is out (4 in this example). There are three positions the 5 could be in (because it can’t be where the 3 is), so make two guesses with the 5 in two of those and 4s everywhere else. If you get a black, that’s where it should be. If you get two whites, it has to be in the third position.
4. Finally, you have two numbers correctly positioned and two others left to place, which means their are only two possibilities. Guess one of those, and if that’s wrong guess the other.

At most, this will take 12 guesses. That’s the number allowed in the original version of the game, but it would be a pretty bad score for a person to get. That’s because this algorithm is deliberately set up to only give a little bit of information at each step – that makes it easy to know where you are and what to do next, but it’s definitely not the most efficient.

Can you find an approach that will always get the answer in 10 guesses? 8? Even less? VBA is allowed if you want, but a formula-only approach is encouraged.

Send me whatever you come up with at the email address at the bottom, and I’ll give a shout out to the person with the best algorithm (to avoid any ambiguity: I’ll say the algorithm which takes the fewest guesses on average over all the different possible codes is the best; if two people tie, the first one I get back wins; if your file takes too long to run I may not test it; and I reserve the right to completely renege on all of the above in any way I choose…).

One note: this game is a classic among computer scientists, and if you look you can find a lot of thoughts on how to write algorithms for it. Implementing one of those algorithms in Excel formulas is probably not easy, but it’s also not the same as the challenge of figuring out your own solution. This challenge is for fun, and there’s no prize. I encourage you to try doing it by yourself.

Part 3: Shortest fixed algorithm

This last part is reserved for uber-nerds only…

The wikipedia article on the twelve-coin problem includes a set of three weighings that will solve the problem, where each weighing is fixed (i.e. doesn’t depend on the results of the earlier ones).

In the same spirit, can you find a fixed set of Mastermind guesses, the scores of which will always allow you to know what the code is? How small a set can you find? Feel free to use VBA for this part – it’s not strictly necessary, but if you know it it will probably help.

As far as I know, this has not been looked at before, and the answer is not on google. I have an answer, but I don’t know if it’s the best… I’m hoping someone can find something better.

Submissions:

I would love to see whatever you come up with for this. Send your submissions to [the name of this blog (the bit that comes before .wordpress.com)] at gmail dot com.

Since this blog hasn’t yet reached the multi-million daily viewer traffic that it surely will, I’m going to leave this one open for a while – but if you’ve submitted an entry and want to know where you stand, send me an email and I’ll let you know.

Happy puzzling!

Image credit: Wikipedia user ZeroOne [link].