通过算法生成斑马/爱因斯坦难题

Question

首先，我并不是一定要找一个可以复制粘贴的完整算法，然后就可以收工了。任何“一般的方法”解决方案都对我来说没问题！

这篇文章的灵感来源于工作中无聊的一天，偶然发现这个网站，但却无法弄清他们是如何实现他们的生成器的。

问题

对于那些不知道的人来说，“斑马难题”或“爱因斯坦难题”是一道著名的逻辑谜题，你可能以前就遇到过。

完整的维基百科文章在这里，但我会发布相关的部分。

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept. 
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be
added that each of the five houses is painted a different color, and their inhabitants
are of different national extractions, own different pets, drink different beverages 
and smoke different brands of American cigarets [sic]. One other thing: in statement 
6, right means your right. 

这些方法看起来都很不错。我在网上找到了几种简洁而整洁的方法来解决这个问题，特别是使用约束编程。但是，我感兴趣的是制作更多这样的谜题。

制作更多

显然，矩阵表示法是思考这个问题的一种逻辑方式。每列包含一个人、房子、他们喝什么、他们开什么车等信息。

我最初的想法是从已完成（即已解决）的随机生成方格开始（以某种方式）创建提示，然后从已解决的版本中唯一地识别它。每次可以确定某些东西时，它就会从方格中删除。

从我在开头列出的网站上翻译过来的以下“提示”可用于解决网格：

    

• 人/动物/植物住/生长在给定的房子里。

    

• 人/动物/植物不住/生长在给定的房子里。

    

• 人/动物/植物住在同一个房子里

    

• 人/动物/植物是另一个人/动物/植物的直接邻居。

    

• 人/动物/植物是其他人/动物/植物的左边或右边的邻居。

    

• 人/动物/植物和另一个人/动物/植物之间有一座房子。

    

• 人/动物/植物和另一个人/动物/植物之间有一座房子，左边或右边。

    

• 人/动物/植物和另一个人/动物/植物之间有两个房子。

    

• 人/动物/植物和另一个人/动物/植物之间有两个房子，左边或右边。

    

• 人/动物/植物住在离其他人/动物/植物左侧或右侧的位置。

您可以看到如何将这些广义化、扩展等;

困难在于，使用我的方法（从完整的方格开始并生成这些提示），我不确定如何确保我创建的提示集会绝对导致目标方格。

例如，如果你说“英国人不拥有松树”，你不能在任何给定时间决定性地配对两个东西。但是，如果只剩下两棵树需要解决，这实际上可能是一个决定性的证据。

我想错了吗？更好的方法是创建一个具有一些随机预定义已知元素的方格（即红房子在中间），然后使用这些提示作为构建规则来构建方格吗？

非常感谢任何建议、阅读文章、学习编程技术等！

- Weaver

---

相关帖子：http://gamedev.stackexchange.com/questions/5909/data-structures-for-logic-games-deduction-rules-sufficient-set-of-clues - greenoldman

Answer 1

下面是一个利用您的求解器的简单算法:

1. 生成随机数独实例。

2. 构建一个包含所有可能提示的集合 C，这些提示与该数独实例相关。（实际上，有限且数量相当小的可能提示：例如，如果有5个房子，则存在5种形式为“A人住在B房子里”的可能提示，8种形式为“A人住在B旁边”的可能提示等等。）

3. 从 C 中随机选择提示的排列顺序 c₁、c₂、…、c_n。

4. 设置 i = 1。

5. 如果 i > n，则完成。提示集合 C 是最小的。

6. 令 D=C-{c_i}。在提示集合 D 上运行您的求解器并计算可能解决方案的数量。

7. 如果存在精确地一种解决方案，则设置 C=D。

8. 设置 i = i + 1 并返回到步骤5。

（您可以通过一次删除多个提示而不是一个一个删除来加快速度，但这样会使算法的描述更加复杂。）

- Gareth Rees

---

谢谢，Gareth！这是一个听起来很棒的解决方案！ - Weaver

+1：我认为这看起来是正确的。但第二步并不是小事。它还会留下Set中冗余和/或无用的线索的可能性。例如，“A住在B的右边”和“B住在A旁边”。或者像“A住在B旁边”，“B住在C旁边”，“C不住在A旁边”这样不太明显的线索。 - RBarryYoung

该算法开始时，C 包含了所有可能的提示，包括许多冗余子集。然后从该集合中删除提示，直到不能再删除任何提示而不使谜题变得模糊不清为止。此时，不应有任何冗余子集剩余。 - Gareth Rees

在自动定理证明中，有比这更酷的东西。如果你将语句扩展到一阶逻辑，会出现一些很酷的东西。例如，不是“英国人住在红房子里”，而是“所有英国人都住在红房子里”或“一些英国人住在红房子里”等等。这创造了一个宇宙和一组谓词。听起来熟悉吗？实际上，这建立了一个理论。稍后，您可以问一个命题在该理论中是否为真？有一种演算法可以让您将其转换为计算（http://en.wikipedia.org/wiki/Resolution_(logic)）。 - thang

原始问题可以转化为命题逻辑中的宇宙和谓词集合。由于命题逻辑的完备定理，每个语句都必须是可判定的（长话短说 :p）。假设一致性，一阶逻辑不存在这样的完备性，这就是扩展更酷的原因。它让您在自己的理论内生成更复杂的问题。这些问题的答案在有限时间内无法“决定”。 - thang

Answer 2

我对这种解决方案并不完全有信心，但这是我的方法：从一个随机的解决方案开始（即绿色房子住波兰人吸LM牌香烟，红色房子住爱尔兰人吸丁香味牌香烟等），您可以将该解决方案视为语句之间关系的图表。其中每个元素（波兰人、红房子等）都与所有其他元素相连，连接方式为“是”边或“否”边（在我们的情况下，波兰人与绿色房子相连的是“是”边，与丁香味牌香烟相连的是“否”边（除其他许多边外，这个初始图是一个完整的有向图））。

现在，如果你随机删除边缘，直到只剩下一个最小的连通图，那么你应该有一个代表可解谜题的图，将每个“是”边翻译成“foo是/做bar”，每个“否”边翻译成“foo不是/不做bar”。

就我而言，这听起来很正确。但再次强调，这绝不是正式或公认的方法，可能是完全错误的。

- Oren

---

这是一个聪明的方法！感谢您的建议！今晚我会尝试一些算法 :) 如果我确认它有效，我会将其标记为答案！ - Weaver

谢谢，如果这种方法失败了，你总是可以使用加雷斯的迭代方法。但我想知道我的方法是否可行 :) - Oren

在这种方法中，“最小连通图”是什么？而且您是否考虑到 NO 连接比 YES 连接多四倍？（也就是说，YES 连接在其两个自由度之一中是唯一的，但 NO 连接不是）。 - RBarryYoung

一个“否”边代表一个有效的线索，就像一个“是”边一样，它相当于从所有可能的线索开始。那么，“是”和“否”的比率有什么影响呢？一个最小连通图应该允许谜题得以解决，这意味着图形包含至少一个顶点到所有其他顶点的路径。我现在才意识到这种方法忽略了更复杂的“抽香烟的人不住在蓝房子里”之类的线索。不确定Gareth的迭代解决方案是否也涵盖了这些问题... - Oren

Answer 3

你也可以采取相反的方式（这样也会得到一个求解器）：

1. 生成所有可能解决方案（即表格）的列表 S。
2. 随机生成一个事实 f（例如：挪威人有一只猫）。
3. 设置 T = S
4. 从 T 中过滤掉违反 f 的所有解决方案。
5. 如果 |T| = 0 那么重复步骤 2 （该事实与之前的某个事实矛盾）
6. 如果 |T| < |S| 那么设置 S = T 并且 F.append(f)（该事实不是之前的事实所包含的）。
7. 如果 |S| > 1 则重复步骤2

完成后 - F将会是导致 S 中仅剩的一个表格的事实列表。

诚然，这种方法非常粗暴，对于5X5甚至更大的表格可能效果并不好。

- Shir

Answer 4

我认为Gareth Rees的答案基础是正确的，但我认为采用加法方法而不是减法方法会更好。

您可以从一组潜在线索（C），一个接受线索的空集（D）和一个空谜题解决方案（S）开始。

然后，您可以循环执行以下过程，直到S可行：

1. 从C中获取下一个线索（C_i）。
2. 尝试使用C_i解决谜题并更新S。
3. S是否发生了变化？如果是，则将C_i添加到D中；否则，将其丢弃。
4. S是否已完成？如果是，则可以停止并使用D作为线索列表；否则，请从步骤1重复。

这绝对保证没有不必要的线索，因为您只保留增加谜题解决方案的线索。而且，与从数十个（或数百个）线索开始并将它们缩减到几个相比，这种方法可能会更快。（还要注意：通过进行一些调整，您可以轻松修改此过程，以在S可解之后通过添加额外的线索来降低谜题难度。）

- ScottM

Answer 5

有趣的是，“爱因斯坦”难题（引号意味着，所有“聪明”的东西似乎都被归于爱因斯坦，也许是为了更具魅力），与数独生成算法（通过适当的术语翻译）以及魔方（3x3x3）求解算法相关。

在数独的情况下，提示对应于网格上已分配的数字，而缺失的信息对应于空槽。

在魔方的情况下（我觉得更有趣），提示对应于立方体的对称性（例如，绿色紧挨着红色之类的），并且可以通过重新对齐（解决）魔方来找到缺失的数据。

这只是一个大致的概述，谢谢。

- Nikos M.

Answer 6

这里有另一个想法 - 在生成完整的网格后，拍下它的照片（或复制设计），然后再移除提供线索的项目。您可能会在完成任务的一半时忘记原始/最终布局应该是什么样子，并避免误导您的受试者/测试者。

考虑为复活节做一个类似的模式，5个人，5种巧克力类型，5个年龄段，5个不同的复活节帽子，5个不同的最爱饮料，冰激凌等等。

- Dan