I have seen Donald Knuth's Algorithm to guess the correct pattern in maximum 5 tries. However, I want to write a program to find the correct pattern effectively however the code maker can only make a pattern with distinct colors. Donald's algorithm uses the fact that you can make a pattern with 2 or more same colors. Can someone help me find an algorithm that will guess the pattern effectively and not make random guesses?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Is the guesser also restricted to guesses unique colors? If not then you can use the algorithm unchanged and you will still be guaranteed to get it in 5. $\endgroup$– 2012rcampionCommented Nov 6, 2022 at 15:20
-
$\begingroup$ @2012rcampion Yes, if the guesser tries to use a color more than once in his guess, he has a penalty. the program wont even tell him if his pattern is partially correct or not $\endgroup$– Mounir ZouhariCommented Nov 6, 2022 at 16:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I would start by
simply applying Knuth's algorithm as is, except limited to the patterns with no repetitions (654*3 = 360 out of 6^4 = 1296). You would only need to test one starting guess (they're all equivalent, just swap the colors around).
I don't know whether it would be optimal, but at least it would set a minimum.
Also note that optimizing for "requires N guesses at most" is different from optimizing for "requires N guesses on average". (Per Wikipedia, the optimal strategy for the latter has an average of just over 4.34, but a worst case of 6.)
