通过算法生成斑马/爱因斯坦拼图

Question

首先，我不一定要寻找一个完整的算法，我可以直接复制和粘贴，然后收工。任何“通用方法”解决方案对我来说都很好!

整篇文章的灵感来自于一天的工作缓慢，并偶然发现了 this site并且无法弄清楚他们是如何实现他们的生成器的。

问题

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

完整的 wiki 文章是 here ，但我会发布相关位。

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. 

这一切都很好。我在网上找到了几种简洁明了的方法来解决这个问题，尤其是使用约束编程。然而，我感兴趣的是制作更多此类拼图。

制作更多

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

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

扯掉我在开头列出的站点，以下可用于解决网格的“提示”可以是以下类型:

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

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

• 人/动物/植物与其他人住在同一所房子里人/动物/植物。

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

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

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

• 人/动物/计划与另一间房子之间有一座房子左边或右边的人/动物/植物。

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

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

• 人/动物/植物住在另一方的左边或右边人/动物/植物。

您可以看到这些如何被泛化、扩展等；

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

例如，如果您说“The Englishman does not own a pine tree”，则您无法在拼图中的任何给定时间果断地将两件事配对在一起。然而，如果只剩下两棵树需要解决，这实际上可能是一个决定性的证据。

我是不是以完全错误的方式思考这个问题？更好的方法是使用一些随机的、预定义的已知元素(即红色房子在中间)创建一个网格，然后使用这些提示作为构建规则来构建网格吗？

如有任何建议、要阅读的文章、要学习的编程技术等，我们将不胜感激!

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 步。

(您可以通过分批而不是一次删除一个线索来加快速度，但这会使算法更难以描述。)