算法生成Zebra/Einstein拼图

Question

首先,我不一定要找一个完整的算法,我可以复制和粘贴,然后称它为一天.任何"一般方法"解决方案对我来说都没问题!

这整个帖子都受到工作缓慢的一天的刺激,并且在这个网站上磕磕绊绊,无法弄清楚他们是如何实现他们的发电机的.

问题

对于那些不知道的人来说,"斑马拼图"或"爱因斯坦之谜"是一个着名的逻辑谜题,你可能已经遇到过.

完整的wiki文章在这里,但我会发布相关内容.

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. 

这一切都很好.我在网上找到了几种简洁明了的方法来解决这个问题,特别是使用约束编程.但是,让我感兴趣的是制作更多这类谜题.

做得更多

显然,矩阵表示是思考这个问题的合理方式.每列包含一个人,房子,他们喝的东西,他们驾驶的汽车类型等等.

我最初的想法是从一个随机生成的网格开始,该网格是完整的(即,已经解决),然后(不知何故)从解决的版本中创建唯一标识它的提示.每次可以确定某些东西时,它都会从网格中删除.

剥离我在开头列出的网站,以下可用于解决网格的"提示"可以是以下类型:

• 人/动物/植物在给定的房屋中生活/生长.

• 人/动物/植物不在特定的房屋中生活/生长.

• 人/动物/植物与其他人/动物/植物住在同一房屋内.

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

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

• 人/动物/植物与其他人/动物/植物之间有一个房屋.

• 人/动物/计划与左侧或右侧的另一个人/动物/植物之间有一个房子.

• 人/动物/植物与其他人/动物/植物之间有两个房屋.

• 人/动物/计划与左侧或右侧的另一个人/动物/植物之间有两个房屋.

• 人/动物/植物离开或远离其他人/动物/植物.

你可以看到这些如何被推广,扩展等;

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

例如,如果你说"英国人不拥有一棵松树",你就无法在拼图中的任何特定时间将两件事物巧合在一起.然而,如果只剩下两棵树要解决,这实际上可能是一个决定性的证据.

我是否以完全错误的方式思考这个问题？更好的方法是创建一个带有一些随机的,预定义的已知元素的网格(即红屋位于中间),然后使用这些提示构建网格作为构建规则？

任何建议,阅读文章,学习的编程技术等,将不胜感激!

Answer 1

这是一个使用求解器的简单算法:

1. 生成随机拼图实例.

2. 构建一个包含与此拼图实例相关的所有可能线索的集合C. (有一些有限的,实际上有很少的可能线索:例如,如果有5个房屋,有5个可能的形式"人A住在房子B"的形式,8个可能的形式"人A生活"的线索在B"旁边,等等.)

3. 选择C中线索的随机排列c ₁,c ₂,...,c _n.

4. 设置i = 1.

5. 如果我 > n,我们就完成了.线索的集合C是最小的.

6. 设D = C - { c _i }.在线索集D上运行求解器并计算可能的解决方案的数量.

7. 如果恰好有一个解决方案中,设置Ç = d.

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

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