# Knuth's algorithm for Mastermind question

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm).

I have a question about step 3 in the algorithm, "Remove from S any code that would not give the same response if it (the guess) were the code".

How would this estimation (of which codes would not give the same response) be "performed"? Obviously we can't ask for responses for each of the codes in S, that would just be brute force.

Thanks!

• The algorithm isn't guaranteed to be fast; just to be correct. You can indeed iterate over all of the codes in $S$ and check each of them against the response. Dec 13 '14 at 2:47
• @StevenStadnicki Hi, thanks for the answer. But to get a response for each of the remaining $O(|S|)$ codes, wouldn't that cost me $O(|S|)$ guesses? It doesn't seem (to me, which doesn't say much) that there is a way to determine if the responses for two codes are the same, given the response of only one of them, so we would have to submit the second one as a guess, no? Dec 13 '14 at 2:55
• Ana M: you don't need to guess - you just need to match the remaining codes against your most recent guess and determine whether they would give the same response. For instance, suppose your first guess is '1122' and you receive one black peg and one white peg. Then you would remove '3422' from your set $S$, since if that were the actual code then your '1122' response would have netted you two black pegs, but you would keep e.g. '2134' in $S$ since that fits the one black peg, one white peg result. Dec 13 '14 at 3:06

The idea is that $S$ maintains the set of all possible codes that you could be guessing at, so after each guess you iterate through the remaining elements of $S$ seeing how they stack up against the (most recent) guess you've made and rejecting those that don't fit the response you got. For instance, if your first guess is 1122 and you receive a response of one white and one black peg, then you'd remove 1134 from $S$ (since if that had been the actual code you would have gotten a different response, namely two black pegs), but you would keep 2134 in $S$ (since that code is consistent with the response of one black, one white to 1122). You're constantly asking the question 'if this were the master's code, what would the response to my guess have been?' of all codes in $S$, and that calculation — while inefficient — doesn't require any guesses at all.
• @Nulle Not at all. You're keeping every element in the set $S$ that would give the response that you get, and that doesn't require any of the knowledge you're talking about. For each code in $S$ I just ask (myself) 'if this were the real code, and I guessed 1122, what would the result be?'; I can do that without any knowledge of the actual code, because I can follow the rules of the game just as well as the mastermind themselves. 2134 there is just one example, but I would also keep e.g. 3412 in $S$. Nov 14 '16 at 18:50
• @Nulle That's step 6 in the algorithm that OP links to, but that's moot to the question here. In brief, you go through your set $S$ of still-valid possibilities and pick the one that's guaranteed to eliminate the largest number of possibilities regardless of what the actual response is. Nov 14 '16 at 20:34