An implementation of Knuth's five-guess algorithm to solve a mastermind code [CC0]

mastermind.py

from itertools import product

def score(self, other):
	first = len([speg for speg, opeg in zip(self, other) if speg == opeg])
	return first, sum([min(self.count(j), other.count(j)) for j in 'ABCDEF']) - first

possible = [''.join(p) for p in product('ABCDEF', repeat=4)]
results = [(right, wrong) for right in range(5) for wrong in range(5 - right) if not (right == 3 and wrong == 1)]

def solve(scorefun):
	attempt(set(possible), scorefun, True)

def attempt(S, scorefun, first=False):
	if first:
		a = 'AABB'
	elif len(S) == 1:
		a = S.pop()
	else:
		a = max(possible, key=lambda x: min(sum(1 for p in S if score(p, x) != res) for res in results))

	sc = scorefun(a)

	if sc != (4, 0):
		S.difference_update(set(p for p in S if score(p, a) != sc))
		attempt(S, scorefun)

if __name__ == '__main__':
	import sys
	secret = len(sys.argv) > 1 and sys.argv[1] or input("Please enter a code (four characters, A-F): ")
	if len(secret) == 4 and not (set(secret) - set('ABCDEF')):
		print("Solving...")
		attempts = 0
		def scorefun(x):
			global attempts
			attempts += 1
			sc = score(secret, x)
			print(x, '+'*sc[0] + '-'*sc[1])
			return sc
		solve(scorefun)
		print("It took", attempts, "attempts.")
	else:
		print(secret, "is not a well-formed mastermind code.")

on L19 the outer loop is on results. I think this is the most efficient thing (since the length of results is constant and small), but in some cases it can be not the optimal (greedy) solution. results is a list of 14 elements. Suppose you are at the end of the game and you have just 3 possibilities: in this case there are only 3 possibilities, not 14 and you can choose one which is impossibile (11 are impossibile in this case).

I suggest you when len(possibile) < k * len(results) (where k is 1 or 2 or 3, or a small number) to don't loop on results but to loop on [score(y, p) for y in possibilities], which should be an array smaller then results (if k=1).

You may be right. You could fork it and try it out.

Now, I don't really remember, since this was three years ago, but I think I copied the algorithm verbatim from Wikipedia or something.