algorithm - n位主谋变异算法

Question

前几天我在大学举办的比赛中遇到了这样一个问题:

Given the history of guesses in a mastermind game using digits instead of colors in a form of pairs (x, y) where x is the guess and y is how many digits were placed correctly, guess the correct number. Each input is guaranteed to have a solution.

Example for a 5-place game:

(90342, 2)
(70794, 0)
(39458, 2)
(34109, 1)
(51545, 2)
(12531, 1)

Should yield:

39542

Create an algorithm to correctly guess the result in an n-place mastermind given the history.

所以我唯一的想法是根据给定猜测中的正确投篮来保持每个数字正确的概率，然后尝试生成最可能的数字，然后是下一个，依此类推 - 例如我们第一名的可能性为 9(因为第一个猜测有 2/5=40% 正确)，7 是不可能的，依此类推。然后我们对数字中的其他地方做同样的事情，最后生成一个概率最高的数字来测试它是否与所有的猜测。

不过，这种方法的问题是生成下一个可能的数字，然后再生成下一个，等等(因为我们可能不会在第一次尝试中打出本垒打)真的很重要(或者在至少我没有看到一个简单的方法来实现它)并且由于这场比赛有大约 90 分钟的时间框架并且这不是唯一的问题，我认为预期的方法不会如此复杂。

那么如何才能更轻松地做到这一点呢？

Answer 1

我想到的一种方法是编写一个例程，该例程通常可以根据特定的尝试及其分数过滤组合的枚举。

因此，对于您的示例，您最初会选择最受限制的尝试之一(得分为 2 的尝试之一)作为过滤器，然后枚举满足它的所有组合。

该枚举的输出然后用作下一个未处理的 try 过滤器运行的输入，依此类推，直到 tries 列表耗尽。

最终枚举出来的候选try就是解决方案。