项目 —— 填词游戏

TIP

我们为你提供了一个简单有趣的项目，帮助你进行知识巩固，请认真阅读文档内容。

如果你卡住了，请记得回来阅读文档，或请求身边人的帮助。

📥

本节附件下载

编写一个人工智能来完成填词游戏。

能够实现将文字转换为图片。

$ python generate.py data/structure1.txt data/words1.txt output.png
|█|█|█|█|█|█|█|█|█|█|█|█|█|█|
|█|█|█|█|█|█|█|M|█|█|█|█|R|█|
|█|I|N|T|E|L|L|I|G|E|N|C|E|█|
|█|N|█|█|█|█|█|N|█|█|█|█|S|█|
|█|F|█|█|L|O|G|I|C|█|█|█|O|█|
|█|E|█|█|█|█|█|M|█|█|█|█|L|█|
|█|R|█|█|█|S|E|A|R|C|H|█|V|█|
|█|█|█|█|█|█|█|X|█|█|█|█|E|█|
|█|█|█|█|█|█|█|█|█|█|█|█|█|█|

背景

你如何生成一个填字游戏？考虑到填字游戏的结构 (即网格中哪些方格需要填入字母)，以及要使用的单词列表，问题就变成了选择哪些单词应该填入每个垂直或水平的方格序列。我们可以将这种问题建模为一个约束满足问题。每一个方格序列都是一个变量，我们需要决定它的值 (在可能的单词域中哪个单词将被填入该序列)。考虑一下下面的字谜结构。

在这个结构中，我们有四个变量，代表了我们需要填入这个字谜的四个单词 (在上图中每个单词都用数字表示)。每个变量由四个值定义：它开始的行 ( i 值)，它开始的列 ( j 值)，单词的方向 (纵向或横向 down or across)，以及单词的长度。例如， 变量1 将是一个由第 1 行 (假设从顶部计数的 0 索引)、第 1 列 (假设从左边计数的 0 索引)、方向为 across 和 4 的长度表示的变量。

与许多约束满足问题一样，这些变量有一元和二元约束。变量的一元约束是由其长度决定的。例如，对于 变量1 来说，数值 BYTE 可以满足一元约束，但是数值 BIT 则不能 (它有错误的字母数量)。因此，任何不满足变量的一元约束的值都可以立即从变量的域中删除。

变量的二元约束是由其与相邻变量的重合度给出的。 变量1 有一个邻居： 变量2 。 变量2 有两个邻居： 变量1 和 变量3 。对于每一对相邻的变量，这些变量都有一个重叠部分：一个它们共同的单方块。我们可以将这种重叠表示为每个变量有用相同字符位置的索引对。例如， 变量1 和 变量2 之间的重叠可以表示为一对 (1, 0) ，这意味着 变量1 在索引 1 处的字符必然与 变量2 在索引 0 处的字符相同 (再次假设索引从 0 开始)。因此， 变量2 和 变量3 之间的重叠将被表示为一对 (3, 1) ， 变量2 的值的字符 3 必须与 变量3 的值的字符 1 相同。

对于这个问题，我们将增加一个额外的约束条件，即所有的单词必须是不同的：同一个单词不应该在谜题中重复出现多次。

那么，接下来的挑战是写一个程序来找到一个满意的赋值：为每个变量提供一个不同的词 (来自给定的词汇表)，从而满足所有的一元和二元约束。

理解

这个项目中有两个 Python 文件： crossword.py 和 generate.py 。第一个文件已经完全为你写好了，第二个文件有一些函数留给你去实现。

首先，让我们看一下 crossword.py 。这个文件定义了两个类， Variable (代表填字游戏中的变量) 和 Crossword (代表填字游戏本身)。

注意，要创建一个变量，我们必须指定四个值：它的第 i 行，第 j 列，它的方向 (常数 Variable.ACROSS 或常数 Variable.DOWN``)，以及它的长度( length``)。

字谜类需要两个值来创建一个新的字谜：一个定义了字谜结构的 structure_file ( _ 用来代表空白单元格，任何其他字符都代表不会被填入的单元格) 和一个定义了字词列表 (每行一个) 的 word_file ，用来作为游戏的词汇表。这些文件的三个例子可以在项目的数据目录中找到，也欢迎你自己创建。

特别要注意的是，对于任何一个字谜对象的字谜，我们都会存储以下的数值：

• crossword.height 是一个整数，代表填字游戏的高度。
• crossword.width 是一个整数，代表填字游戏的宽度。
• crossword.structure 是一个二维列表，代表字谜的结构。对于任何有效的第 i 行和第 j 列，如果该单元格是空白的， crossword.structure[i][j] 将为真 (必须在该单元格中填入一个字符)，否则将为假 (该单元格中没有字符要填)。
• crossword.words 是一个包含所有单词的集合，在构建填字游戏的时候，可以从这些单词中提取。
• crossword.variables 是谜题中所有变量的集合 (每个变量都是一个 Variable 对象)。
• crossword.overlaps 是一个字典，它将一对变量映射到它们的重合处。对于任何两个不同的变量 v1 和 v2，如果这两个变量没有重叠， crossword.overlaps[v1, v2] 将是 None ，如果这两个变量有重叠，则是一对整数 (i, j) 。这对 (i, j) 应被解释为： v1 的第 i 个字符的值必须与 v2 的第 j 个字符的值相同。

Crossword 对象还支持一个方法 neighbors ，它可以返回与给定变量重叠的所有变量。也就是说， crossword.neighbors(v1) 将返回一个与变量 v1 相邻的所有变量的集合。

接下来，看一下 generate.py 。在这里，我们定义了一个 CrosswordCreator 类，我们将用它来解决填字游戏。当一个 CrosswordCreator 对象被创建时，它得到一个填字游戏的属性，它应该是一个 Crossword 对象 (因此具有上面描述的所有属性)。每个 CrosswordCreator 对象还得到一个域属性：一个字典，它将变量映射到该变量可能作为一个值的一组词。最初，这组词是我们词汇表中的所有词，但我们很快就会写函数来限制这些域。

我们还为你定义了一些函数，以帮助你测试你的代码： print 将向终端打印你的填字游戏的一个给定的赋值 (每个赋值，在这个函数和其他地方，是一个字典，将变量映射到它们相应的词)。同时， save 将生成一个与给定作业相对应的图像文件 (如果你无法使用这个函数，你需要 pip3 install Pillow )。 letter_grid 是一个被 print 和 save 使用的辅助函数，它为给定的赋值生成一个所有字符在其适当位置的 2D 列表：你可能不需要自己调用这个函数，但如果你想的话，欢迎你这样做。

最后，注意 solve 函数。这个函数做了三件事：首先，它调用 enforce_node_consistency 来强制执行填字游戏的节点一致性，确保变量域中的每个值都满足一元约束。接下来，该函数调用 ac3 来强制执行弧一致性，确保二元约束得到满足。最后，该函数在最初的空赋值 (空字典 dict ()) 上调用 backtrack ，试图计算出问题的解决方案。

不过， enforce_node_consistency 、 ac3 和 backtrack 等函数还没有实现 (以及其他函数)。这就是你的任务。

明确

完成 grece_node_consistency , revise , ac3 , assignment_complete , consistent , order_domain_values , selected_unassigned_variable 和 backtrack 在 generate.py 中的实现，这样如果有有解的话你的人工智能就能生成完整的字谜。

• enforce_node_consistency 函数应该更新 self.domains ，使每个变量都是节点一致的。

  • 回顾一下，当对每个变量来说，其域中的每个值都与该变量的一元约束一致时，就实现了节点一致性。在填字游戏的情况下，这意味着要确保变量域中的每个值的字母数与变量的长度相同。
  • 要从一个变量 v 的域中移除一个值 x ，因为 self.domains 是一个将变量映射到数值集的字典，你可以调用 self.domains[v].remove(x) 。
  • 这个函数不需要返回值。

• revise 函数应该使变量 x 与变量 y 保持弧一致性。

  • x 和 y 都是 Variable 对象，代表谜题中的变量。
  • 回顾一下，当 x 的域中的每一个值在 y 的域中都有一个不引起冲突的可能值时， x 就与 y 保持弧一致性。(在填字游戏的背景下，冲突是指一个方格，两个变量对它的字符值意见不一)。
  • 为了使 x 与 y 保持一致，你要从 x 的域中删除任何在 y 的域中没有相应可能值的值。
  • 回顾一下，你可以访问 self.crossword.overlaps 来获得两个变量之间的重叠，如果有的话。
  • y 的域应该不被修改。
  • 如果对 x 的域进行了修改，该函数应返回 True ；如果没有修改，则应返回 False 。

• ac3 函数应该使用 AC3 算法，对问题实施弧一致性。回顾一下，当每个变量域中的所有值都满足该变量的二进制约束时，就实现了弧一致性。

  • 回顾一下， AC3 算法保持着一个要处理的弧的队列。这个函数需要一个叫做 arcs 的可选参数，代表要处理的弧的初始列表。如果 arcs 是 None ，你的函数应该从问题中的所有弧的初始队列开始。否则，你的算法应该从一个初始队列开始，该队列中只有在列表 arcs 中的弧 (其中每个弧是一个变量 x 和另一个变量 y 的元组 (x，y) )。
  • 回顾一下，为了实现 AC3 ，你要一次一次地修改队列中的每个弧。不过，任何时候你对一个域做了改变，你可能需要在队列中增加额外的弧，以确保其他弧保持一致。
  • 你可能会发现在 ac3 的实现中调用 revise 函数是很有帮助的。
  • 如果在执行弧一致性的过程中，你从一个域中删除了所有剩余的值，则返回 False (这意味着问题无解，因为这个变量已经没有可能的值了)。否则，返回 True 。
  • 你不需要担心在这个函数中强制执行词的唯一性 (你将在 consistent 函数中实现这个检查。)

• assignment_complete 函数应该 (如其名所示) 检查一个给定的赋值是否完成。

  • assignment 是一个字典，其中键是 Variable 对象，值是代表这些变量将采取的单词的字符串。
  • 如果每个字谜变量都被分配到一个值 (不管这个值是什么)，那么这个赋值就是完整的。
  • 如果赋值完成，该函数应该返回 True ，否则返回 False 。

• consistent 函数应该检查一个给定的 assignment 是否一致。

  • assignment 是一个字典，其中的键是 Variable 对象，值是代表这些变量将采取的词语的字符串。请注意，赋值不一定是完整的：不是所有的变量都会出现在赋值中。
  • 如果一个赋值满足问题的所有约束条件，那么它就是一致的：也就是说，所有的值都是不同的，每个值的长度都是正确的，并且相邻的变量之间没有冲突。
  • 如果赋值是一致的，该函数应该返回 True ，否则返回 False 。

• order_domain_values 函数应该返回一个 var 域中所有数值的列表，根据最小约束值启发式排序。

  • var 将是一个变量对象，代表谜题中的一个变量。
  • 回顾一下，最小约束值启发式的计算方法是一个赋值导致约束邻近的未分配的变量的数量。也就是说，如果给 var 赋值的结果是排除了邻近变量的 n 个可能的选择，你应该按照 n 的升序排列你的结果。
  • 请注意，在 assignment 中出现的任何变量都已经有了一个值，因此在计算相邻未赋值变量被排除的值的数量时不应该被计算在内。
  • 对于排除相邻变量相同数量可能选择的域值，任何排序都是可以接受的。
  • 回顾一下，你可以访问 self.crossword.overlaps 来获得两个变量之间的重叠，如果有的话。
  • 首先通过返回一个任意顺序的数值列表来实现这个函数可能会有帮助 (这仍然会产生正确的填字游戏)。一旦你的算法开始工作，你就可以回去确保这些值是以正确的顺序返回的。
  • 你可能会发现根据一个特定的 key 来对一个列表进行排序是很有帮助的：Python 包含一些有用的函数来实现这一点。

• select_unassigned_variable 函数应该根据最小剩余值启发式，然后是度启发式，返回字谜中尚未被赋值的单个变量。

  • assignment 是一个字典，其中键是 Variable 对象，值是代表这些变量将承担的单词的字符串。你可以假设赋值不会是完整的：不是所有的变量都会出现在 assignment 中。
  • 你的函数应该返回一个 Variable 对象。你应该返回在其域中剩余数值最少的变量。如果变量之间存在平局，你应该在这些变量中选择度最大的变量 (拥有最多的邻居)。如果在这两种情况下都相同，你可以在相同的变量中任意选择。
  • 首先通过返回任意未分配的变量来实现这个函数可能是有帮助的 (这应该仍然会产生正确的填字游戏)。一旦你的算法开始工作，你就可以回去修改这个函数确保你是根据启发式方法返回一个变量。
  • 你可能会发现根据一个特定的 key 来对一个列表进行排序是很有帮助的：Python 包含一些有用的函数来实现这一点。

• backtrack 函数应该接受一个部分赋值 assignment 作为输入，并且使用回溯搜索，如果有可能的话，返回一个完整的令人满意的变量赋值。

  • assignment 是一个字典，其中键是 Variable 对象，值是代表这些变量将承担的单词的字符串。你可以假设赋值不会是完整的：不是所有的变量都会出现在 assignment 中。
  • 如果有可能生成一个令人满意的字谜，你的函数应该返回完整的赋值：一个字典，其中每个变量是一个键，值是该变量应该承担的单词。如果不可能产生令人满意的赋值，该函数应该返回 None 。
  • 如果你愿意，你可能会发现，如果你把搜索和推理交织在一起，你的算法会更有效率 (比如每次做新的赋值时都要保持弧一致性)。我们不要求你这样做，但允许你这样做，只要你的函数仍然产生正确的结果。(正是由于这个原因， ac3 函数允许一个 arcs 的参数，以防你想从不同的弧队列开始)。

除了要求你实现的函数外，你不应该修改 generate.py 中的任何其他东西，尽管你可以编写额外的函数和 / 或导入其他 Python 标准库模块。如果你熟悉 numpy 或 pandas ，你也可以导入它们，但是你不应该使用任何其他的第三方 Python 模块。你不应该修改 crossword.py 中的任何东西。

提示

• 对于 order_domain_values 和 select_unassigned_variable 来说，不以启发式方法实现它们，然后再添加启发式方法可能会有帮助。你的算法仍然可以工作：只是在找到一个解决方案之前，它可能会探索更多的分配，而不是它需要的。

• 要运行你的程序，你可以运行类似 python generate.py data/structure1.txt data/words1.txt 的命令，指定一个结构文件和一个单词文件。如果可以进行赋值，你应该看到打印出来的赋值。你也可以为图像文件添加一个额外的命令行参数，如运行 python generate.py data/structure1.txt data/words1.txt output.png ，可以为生成的填字游戏生成一个图像表示。

• Crossword 类有一个 neighbors 函数，可以用来访问某个特定变量的所有邻居 (即重叠的变量)。在你需要确定某个特定变量的邻居时，请随时使用这个函数。