Java 中的斑马谜题

斑马谜题是一个复杂的谜题，需要付出大量的努力和脑力来解决。由于它是由著名的德国物理学家 阿尔伯特·爱因斯坦 发明的，因此有时也被称为爱因斯坦谜题或爱因斯坦的脑筋急转弯。

该谜题广泛用于评估计算机算法在解决约束满足问题 (CSP) 方面的能力。大多数人工智能问题都可以建模为约束满足问题 (CSP)。

约束满足问题 (CSP)

一般来说，CSP 问题由有限数量的变量组成，每个变量都有一个有限的值域，以及一组约束。每个约束都定义在原始变量集的一个子集上，并限制这些变量可以同时取的值。任务是为每个变量找到一个赋值，使其满足所有约束；在某些问题中，目标是找到所有这样的赋值。

因此，我们可以将 CSP 定义为一组对象，它们的状态必须满足一些约束或限制。

一些流行的例子包括N皇后问题、图着色问题、填字游戏等。

解决 CSP 的一般方法

解决 CSP 的一般方法是生成-测试法。系统地生成每个可能的变量赋值，然后测试它是否满足所有约束。第一个满足所有约束的赋值就是解决方案。在最坏的情况下（或当我们要查找 CSP 的所有解决方案时，需要考虑的赋值数量是所有变量域的笛卡尔积的大小。因此，该方法的时间复杂度是关于变量数量的指数级。实际上，这种方法的性能非常差。

随机生成-测试算法会根据某种有偏分布（例如，分布可能受最近测试的赋值的影响，就像随机爬山法一样）随机选择要测试的赋值，有时可以表现得非常好，但不幸的是，它们失去了系统性。也就是说，这些随机方法无法证明不存在解决方案，因为它们不一定测试所有可能的赋值。

通常，解决 CSP 有以下三种方法：

• 树搜索
• 约束传播
• 回溯搜索和约束传播相结合

斑马谜题

这个谜题有几种变体。谜题的其他版本与 Life International 的版本有所不同，其中替换了各种颜色、国籍、香烟品牌、饮料和宠物。但逻辑不会改变。以下版本发布在 Life International 上。

1. 有五个房子。
2. 英国人住在红房子里。
3. 瑞典人养了一条狗。
4. 丹麦人喝茶。
5. 绿房子在白房子的正左边。
6. 绿房子里的人喝咖啡。
7. 抽 Pall Mall 香烟的人养鸟。
8. 黄房子里的人抽 Dunhill 香烟。
9. 中间的房子里的人喝牛奶。
10. 挪威人住在第一个房子里。
11. 抽 Blend 香烟的人住在猫旁边那间房子里。
12. 养马的人旁边那间房子里的人抽 Dunhill 香烟。
13. 抽 Blue Master 香烟的人喝啤酒。
14. 德国人抽 Prince 香烟。
15. 挪威人住在蓝房子旁边。
16. 喝水的人住在抽 Blend 香烟的人旁边那间房子里。

请注意，五个房子中的每个房子都漆成不同的颜色，其居民拥有不同的国籍、不同的宠物、喝不同的饮料，并抽不同品牌的美国香烟。还有一件事：在第 5 条陈述中，左表示你的右边。

问题是，谁养了斑马？另外，列出所有房子的解决方案。可选地，显示解决方案是唯一的。

斑马谜题的解决方案

在过去的几年里，已经提出了几种解决这个问题的方法，例如回溯、最小剩余值 (MRV)、前向推理 (FC)、最小冲突等。但在本节中，我们将使用通用方法，即生成-测试。

根据上述 16 条约束（陈述），让我们总结一下谜题的属性。

颜色：红色、绿色、象牙色、黄色、蓝色

国籍：英国人、西班牙人、乌克兰人、挪威人、日本人

饮料：咖啡、茶、牛奶、橙汁、水

香烟： Old Gold、Kools、Chesterfields、Lucky Strike、Parliaments

宠物：狗、蜗牛、狐狸、马、斑马

让我们将给定的数据整理成表格形式，以便更好地理解。

以下 Java 程序包含以下四个用户定义类：

• Zebra 类
• PossibleLine 类
• PossibleLines 类
• Solver 类

Zebra.java

输出

After general rule set validation, remains 60 lines.
After removing out of bound neighbors, remains 52 lines.
After 1 recursive iteration, remains 17 lines
After 2 recursive iteration, remains 6 lines
After 3 recursive iteration, remains 5 lines
-------------------------------------------
1 - Norwegian - Yellow - Cats - Water - Dunhill
2 - Danish - Blue - Horse - Tea - Blend
3 - English - Red - Birds - Milk - Pall Mall
4 - German - Green - Zebra - Coffee - Prince
5 - Swedish - White - Dog - Beer - Blue Master