Mastermind hint solver

[tifon]

Mastermind hint solver

I stumbled across a very difficult programming challenge.

The challenge is... given a set of clues and results from the game "Mastermind", determine the answer, and whether or not there's many or no possible answers.

For example:

(Toggle Plain Text)
9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0

The number 3411 is the only one that satisfies the rules.

An explanation of the challenge, and the rules of Mastermind are here:
http://cemc.math.uwaterloo.ca/ccc/1996/21b-prob.html

Now, it's not a difficult challenge at all if you brute force it. Go through every number from 0000 to 9999 and see which ones satisfy all of the clues.

But... that's a terribly ugly algorithm. Very bad complexity. There must be a way to deduce an answer more logically? Thinking about it sends my brain in wild directions though. Seems very difficult.

Have any ideas?

 

[טרול המתכנן]

I think this calls for an 'inverse' solution

Let P be the 'options space' (0,1,...,k)ⁿ
In your case k = 9, n = 4.

Let R be the 'results space' (0,1,...,n) X (0,1,...,n)

Let T ∈ P be the target you're looking for.

Let F be the 'master mind function', F: PXP → R.

The important observation is that F(X,Y) = F(Y,X)

The problem is to find T from a set of 'guesses' Xi ∈ P and 'results' Ri ∈ R, such that F(Xi,T) = Ri
The solution is to build, for each such (Xi,Ri) tuple, the set Si ⊂ P of all options such that:
s ∈ Si → F(s,Xi) = Ri

The final result(s) is:
∩ Si
i

Well, the actual work is in the details of building Si. Basically, if your guess is G = (a,b,c,d) and you get (w,b), you need to build all (x,y,s,t) that preserve b entries in-order from G, preserve w entries out-of-order from G, and all other entries (if exist) cannot be from G.

Example:
2384 0/2
(2,3,x,y) ... x,y in {0, 1, ..., 9} / {2,3,4,8}
(2,x,8,y) ... x,y in {0, 1, ..., 9} / {2,3,4,8}
(2,x,y,4) ... x,y in {0, 1, ..., 9} / {2,3,4,8}
(x,3,8,y) ... x,y in {0, 1, ..., 9} / {2,3,4,8}
(x,3,y,4) ... x,y in {0, 1, ..., 9} / {2,3,4,8}
(x,y,8,4) ... x,y in {0, 1, ..., 9} / {2,3,4,8}

It's probably smarter to work with a logical array like np.ones([10]*4, 'bool')
and than on each step you take a logical and with the 'options matrix' a guess.
I'll throw a python code later.

 

[tifon]

Thanks for you replay prog troll

Thanks for you replay prog troll

With your soution s ∈ Si → F(s,Xi) = R, in a case k = 9 and n = 9 or more, will take a 387420489 (Kⁿ) options to chack.
I can't use this method due to a real time environment.

But i'm trying right to use Genetic Algorithms:

http://www.c-sharpcorner.com/Upload...rticleID=e2b3b833-648a-4a58-b19f-5c4057d3d6ed

I will try to adjust this algorithm to my and i will post it soon.

Thanks again

 

[טרול המתכנן]

Well, this is an implementation detail...

You don't have to use that giant logical array - I just assumed it'll make the code simpler (I'm not even sure that's true).

We probably don't even need to actually build these sets (Si) - we just need to track the patters. But again it makes the code more complex (as evident by the fact that I didn't drop in the promised code...).

Genetic algorithms? In general it's a not-guaranteed to converge (at all) method.