algorithm - 如何使用逻辑推理分析策划类游戏

Question

---

免责声明:我不是在寻找 Mastermind 的解决方案。

---

我正在尝试编写一个程序来解决像 mastermind 这样的游戏，但我有点卡住了。我不想要一个完整的解决方案，只帮助我无法通过的部分。这是游戏:

预先知道 N 种可能的颜色。有一组未知的(可能有重复的)k 被选择并保密。目标是猜测 secret 集中的颜色(重复)。我再次强调，这是一个集合，所以顺序无关紧要，但允许重复。例如

Colors are a,b,c,d,e,f,g,h (N=8) and unknown set is {a,c,c} (k=3).

连续猜测会导致更多关于 secret 集的信息。每个猜测必须是一组(允许重复)k 颜色。对每个猜测的响应是猜测和未知集重复计数之间的共同颜色数。例如

1. Guess: a,d,e Result: 1

2. Guess: b,c,f Result: 1

3. Guess: a,a,g Result: 1

4. Guess: a,c,h Result: 2

5. Guess: b,e,h Result: 0

猜测是别人做的。我的目标是:

- 确定有关特定颜色的信息何时已知。

- 确定何时可以逻辑推导出未知集。

在游戏开始时，没有颜色肯定在集合中或绝对不在未知集合中(假设N>1)。在猜测结果为 0 之后，已知该猜测的所有颜色都不在未知集中。如果结果为 k，则已知该猜测的所有颜色都在未知集中。我在编写一个程序来找出介于两者之间的所有情况时遇到了麻烦。例如，在上面的最后一次猜测之前，对任何颜色都一无所知。经过最后一次猜测，该集合已知为 a,c,c。逻辑是这样的:

• 到 5 时，b,e,h 不在未知集中
• 到4，a,c都在未知集中
• 根据 1，d 不在未知集中
• 到2，f不在未知集中
• 到3，g不在未知集中
• 因此，未知集中的唯一颜色是a 和c。
• 到 3 时，a 不在未知集中不止一次。
• 因此未知集是a,c,c。

我可以通过这种方式处理逻辑，但我不确定通常如何对此进行编程。如果有人可以建议一种结构化的方法来解决这个问题，那就太好了。 我更喜欢使用伪代码的高级解释，而不是任何一种语言的完整实现。谢谢。

Answer 1

直截了当的方法:构建可能组合的总数。然后，随着猜测的出现，删除不可能满足当前猜测结果的组合。一旦你只剩下一个组合，这就是解决方案。或者，在该过程的早期，当您不再代表某种特定颜色时，该颜色(显然)会从可能的密码中删除。