22

Firstly I'm not necessarily looking for a complete algorithm I can just copy and paste, then call it a day. Any "general approach" solutions would be fine for me!

This entire post was spurred by a slow day at work, and stumbling upon this site and not being able to figure out how they implemented their generator.

The Problem

For those of you who don't know, the "Zebra Puzzle" or "Einstein's Puzzle" is a famous logic puzzle that you've probably ran into before.

The full wiki article is here, but I'll post the relevent bits.

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.

This is all well and good. I've found several concise and neat ways online to solve this problem, especially using constraint programming. However, what interests me is making more of these types of puzzles.

Making More

Obviously, a matrix representation is a logical way to think about this. With each column containing a person, house, what they drink, what type of car they drive, etc.

My initial thought was to start with a randomly generated grid that is complete (ie, solved) then (somehow) create hints from the solved version that uniquely identify it. Every time something can be determined, it's removed from the grid.

Ripping off the site I listed at the beginning, the following "hints" that can be used to solve the grid can be of the following type:

  • The person/animal/plant lives/grows in a given house.

  • The person/animal/plant does not live/grow in a given house.

  • The person/animal/plant lives in the same house as the other person/animal/plant.

  • The person/animal/plant is a direct neighbor of the other person/animal/plant.

  • The person/animal/plant is the left or right neighbor of other person/animal/plant.

  • There is one house between the person/animal/plant and the other person/animal/plant.

  • There is one house between the person/animal/plan and the other person/animal/plant on the left or right.

  • There are two houses between the person/animal/plant and the other person/animal/plant.

  • There are two houses between the person/animal/plan and the other person/animal/plant on the left or right.

  • The person/animal/plant lives left or right from the other person/animal/plant.

You can see how these could be generalized, extended, etc;

The difficulty is, using my approach (starting with a complete grid and generating these hints), I'm not sure how to make sure the set of hints I create would absolutely result in the target grid.

For example, if you say "The Englishman does not own a pine tree" you cannot decisively pair two things together at any given time in the puzzle. Yet if there were only two trees remaining to solve for, this could in fact be a decisive piece of evidence.

Am I thinking about this the entirely wrong way? Would a better approach be to create a grid with some randomized, pre-defined known elements (ie, the red house is in the middle) and then build up the grid using these hints as rules for building?

Any advice, articles to read, programming techniques to learn about, etc. would be greatly appreciated!

4

5 回答 5

11

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

  1. 生成一个随机拼图实例。

  2. 建立一个包含与这个谜题实例有关的所有可能线索的集合C。（可能的线索是有限的，实际上非常少：例如，如果有 5 个房子，则有 5 个可能的线索，形式为“A 住在 B 房子”，8 个可能的线索，形式为“A 住旁边的房子B”，等等。）

  3. 选择C​​中线索的随机排列c 1 , c 2 , ..., c n。

  4. 设置i = 1。

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

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

  7. 如果只有一个解，则设置C = D。

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

（您可以通过批量删除线索而不是一次删除一条线索来加快此过程，但这会使算法更难以描述。）

于 2013-01-28T20:00:14.073 回答
3

我对这个解决方案并不完全有信心，但这就是我的处理方式：

从一个随机的解决方案开始（即，温室持有吸 LM 的波兰人，红房子持有抽丁香的爱尔兰人等）。您可以将该解决方案视为语句之间的关系图。其中每个元素（抛光剂、红房子等）通过“是”边缘或“无边缘”连接到所有其他元素（在我们的例子中，抛光剂通过“是”边缘连接到温室，并连接到带有“无边”的丁香（在许多其他边中，这个初始图是一个完整的有向图）。

现在，如果你随机去掉边，直到你得到一个最小的连通图，你应该有一个代表一个可解谜题的图。将每个 yes 边缘转换为“foo is/does bar”，将每个 no 边缘转换为“foo is not/doesn't bar”。

直觉上，这听起来对我来说是正确的。但同样，这绝不是正式或公认的方式，而且可能是完全错误的。

于 2013-01-28T19:40:11.017 回答
2

你也可以反过来做（这也会给你一个求解器）：

  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 或更大的表。

于 2013-12-09T10:08:04.373 回答
1

有趣的是，“爱因斯坦”谜题（意在引用，所有“聪明”的东西都倾向于分配给爱因斯坦，可能更有魅力），与数独生成算法（通过适当的术语翻译）和魔方（3x3x3）有关求解算法

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

在魔方（我觉得更有趣）的情况下，线索对应于立方体的对称性（例如，绿色紧挨着红色，等等）并且通过重新对齐（解决）找到丢失的数据立方体

这是一个粗略的大纲，谢谢

于 2014-05-05T19:26:19.427 回答
0

这是另一个想法——一旦你生成了完整的网格，在你提供线索之前删除项目之前在你的手机上拍一张照片（或复制设计）。您可能会完成任务的一半而忘记原始/最终布局的外观，并且可以避免误导您的科目/应试者。

想为复活节做一个，类似的图案，5 个人，5 种巧克力，5 种年龄，5 种不同的复活节帽子，5 种不同的最喜欢的饮料，冰淇淋等。

于 2019-03-26T13:56:51.083 回答