algorithm - 生成填字游戏的高效算法（纽约时报风格）

Question

我想找到一种有效的方法来生成填字游戏。我已阅读此处提到的解决方案。这会生成一个简单的填字游戏，因为我正在寻找一种有效且优化的方式来生成像纽约时报一样的填字游戏。即，当您将拼图旋转 180 度时，它看起来是一样的（黑色方块保持在同一位置）。在这里，我们可以假设网格是最初生成的，我们可以使用超过三个字母的单词。

这样做的最佳方法是什么？我们可以使用什么搜索算法来减少迭代次数并减少耗时？

Answer 1

对于另一个（未完成的）文字游戏，我从不同的角度解决了这个问题。在我的设计中，如果板可以跨 X 或 Y 轴（或两者）镜像，则选择它们。

取一个大小为 N 的正方形，我使用以2^cell count -1作为最大值的位掩码构建所有可能的网格。因此，对于 2x2（4 个单元格）的网格，从 0...15 开始。

0 - 空网格

1 - 左上角的黑色块

2 - 右上角的黑色块

3 - 顶行中的黑色块

.

.

.

15 - 充满黑色块的网格

显然，这会产生许多不合适的候选人。我们可以放弃：

• 用于 Y 轴镜像的行不匹配中间点的任一侧（等等向外）的图案
• 用于 X 轴镜像的列不匹配中间点的任一侧（等等向外）的模式
• 充满黑色块的网格
• 网格范围（第一行、最后一行、第一列、最后一列）没有白块的模式
• 白色块被隔离的图案 (*)

我想我把它跑到大约 7x7 并在合理的时间内完成。我没有做到的是选择单词。然而，一旦你计算了数字，你就可以简单地存储每个网格大小的所有候选值，然后每次都创建新的填字游戏。

(*) - 对于我正在编写的游戏，这很重要，但我不能 100% 确定这是填字游戏的要求。我认为在电路板的各个部分（无论如何配置）有 2 个或更多不同的白色方块图案可能是完全有效的。