我想找到一种生成填字游戏的有效方法。我已阅读提到的解决方案 here .这会生成一个简单的填字游戏，因为我正在寻找一种有效且优化的方式来生成填字游戏，如 New York times .即，当您将拼图旋转 180 度时，它看起来是一样的(黑色方 block 保持在相同的位置)。在这里，我们可以假设网格是最初生成的，我们可以使用任何超过三个字母的词。

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

最佳答案

我从另一个(未完成的)文字游戏的不同角度解决了这个问题。在我的设计中，如果电路板可以在 X 轴或 Y 轴(或两者)上进行镜像，则会被选中。

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

0 - empty grid

1 - black block in top left

2 - black block in top right

3 - black blocks in the top row

.

.

.

15 - grid full of black blocks

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

• 行与中点任一侧都不匹配的模式 (以此类推)用于 Y 轴镜像
• 列与中途任一侧都不匹配的模式 X 轴镜像的点(以此类推)
• 充满黑色方 block 的网格
• 网格范围(第一行、最后一行、第一行)的图案 列，最后一列)没有白色 block
• 白色 block 被隔离的图案 (*)

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

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

https://stackoverflow.com/questions/31675462/