如何使用逻辑推理分析类似策划者的游戏

Question

---

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

---

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

有N可能提前知道颜色.有一个未知的集合(可能有重复)k被选中并保密.目标是猜测秘密集中的颜色(重复).让我再次强调,这是一个集合,所以顺序无关紧要,但允许重复.例如

颜色是a,b,c,d,e,f,g,h(N=8)和未知集是{a,c,c}(k=3).

进行连续猜测以产生关于秘密集的更多信息.每个猜测必须是一组(允许重复)k颜色.对每个猜测的响应是猜测和未知计数重复之间共同的颜色数.例如

1. 猜猜:a,d,e 结果:1

2. 猜猜:b,c,f 结果:1

3. 猜猜:a,a,g 结果:1

4. 猜猜:a,c,h 结果:2

5. 猜猜:b,e,h 结果: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

高德纳 (Knuth)描述了一个解决方案。我实施了它。