1
$\begingroup$

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?

$\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$ 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$ Nov 6, 2022 at 16:09

1 Answer 1

1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.