如何解决填字游戏（NP-Hard）？
How to solve crossword (NP-Hard)?
我目前正在做作业，但我坚持使用该方法。
我有一个填字游戏问题，它由一个空网格组成（没有像传统填字游戏那样的实心方块），宽度和高度在 4 到 400（含）之间变化。
规则：
- 单词是输入的一部分 - 10 - 1000（含）个不同长度的英语单词的列表。
- 横字只能与竖字相交。
- 竖字只能与横字相交。
- 一个词只能与 1 或 2 个其他词相交。
- 每个字母值一分。
- 单词周围必须有 1 个网格 space 间隙，除非它是交叉单词的一部分。
示例：
X X X X X X
X B O S S X
X X X X X X
目标：
在 5 分钟的时间限制内获得最高分。
到目前为止：
经过一些研究，我知道这是一个 NP-Hard 问题。因此无法计算出最佳解决方案，因为无法检查每个组合。
最简单的解决方案似乎是根据长度对单词进行排序并插入得分最高的单词以获得最高分数（贪心算法）。
我还听说了一个递归树，其节点由替代的等分词插入组成，背包算法适用于这个问题（不确定实现会是什么样子）。
问题：
- 什么允许我检查 5 分钟时间跨度内的最大组合数，并相应地缩放到最大可能的单词列表和网格大小？
- 插入单词时我可以应用什么启发式方法？
顺便说一下，这里的目标是在 5 分钟内获得最佳解决方案。
阐明一个有效单词的每个字母值 1 分，因此一个 5 个字母的单词值 5 分。
提前致谢我整天都在阅读大量关于填字游戏研究论文的数学符号，这似乎让我陷入了一个圈子。
我将从具有以下特征的词开始：
- 它应该有最大可能的交叉点。
- 其长度应使该长度的单词数在列表中最少。
即字长应该是出现次数最少，交集次数最多的
这种选择的原因是它会最大限度地减少可以选择的单词的进一步可能性。例如。选择了一个大小为 9 并带有 2 个进一步交集的单词。这些相交的词的长度为 6 和 5（比方说）。现在，您已经消除了所有那些长度为 6 和 5 的单词的可能性，它们的第 3 个字符是 'a'，第 2 个字符是 's'（比如，'a' 和 's' 是相交的字母）。
如果有很多地方具有相同的配置，运行 这个选择过程会更深入一两步，以便更好地选择首先填充网格的哪个部分（单词）。
现在，尝试填写第一个选定位置中的所有单词（因为它有最小频率，应该很好用）然后在填字游戏中更深入地填充它。在到达死胡同之前，无论哪个词导致最多点，都应该是您的解决方案。当你走到尽头时，你可以用一个新词重新开始。
这似乎是离散优化中一个非常有趣的问题。你当然是对的；由于字数和可能的位置数，您无法探索 space.
的一小部分
另外考虑到 5 分钟的时间限制（相当短），我认为您将很难使用任何可靠的启发式方法。我认为你最好的选择可能是某种随机排列/模拟退火算法。
如果我这样做，我会首先计算词簇，完全忽略纵横字谜结构本身。取一个词，找到与它相交的第二个词。然后找到另一个可以适合这个结构的词（遵守每个词最多 2 个交集），依此类推。您应该最终得到许多这样的集群，您可以按密度（使用的点/面积）对它们进行排名。我认为你应该能够相对快速地做到这一点。
然后对于随机排列/模拟退火部分，对于我的移动，我会将一个簇或未使用的词放在填字游戏本身上，或者移动一个现有的簇/词。只需保存当前得分最高的配置，并在 5 分钟后 return。
如果 5 分钟太短而无法使用随机排列找到任何有意义的东西，另一种方法可能是使用约束传播思想来处理这些集群。
我目前正在做作业，但我坚持使用该方法。
我有一个填字游戏问题，它由一个空网格组成（没有像传统填字游戏那样的实心方块），宽度和高度在 4 到 400（含）之间变化。
规则：
- 单词是输入的一部分 - 10 - 1000（含）个不同长度的英语单词的列表。
- 横字只能与竖字相交。
- 竖字只能与横字相交。
- 一个词只能与 1 或 2 个其他词相交。
- 每个字母值一分。
- 单词周围必须有 1 个网格 space 间隙，除非它是交叉单词的一部分。
示例：
X X X X X X
X B O S S X
X X X X X X
目标：
在 5 分钟的时间限制内获得最高分。
到目前为止：
经过一些研究，我知道这是一个 NP-Hard 问题。因此无法计算出最佳解决方案，因为无法检查每个组合。
最简单的解决方案似乎是根据长度对单词进行排序并插入得分最高的单词以获得最高分数（贪心算法）。
我还听说了一个递归树，其节点由替代的等分词插入组成，背包算法适用于这个问题（不确定实现会是什么样子）。
问题：
- 什么允许我检查 5 分钟时间跨度内的最大组合数，并相应地缩放到最大可能的单词列表和网格大小？
- 插入单词时我可以应用什么启发式方法？
顺便说一下，这里的目标是在 5 分钟内获得最佳解决方案。 阐明一个有效单词的每个字母值 1 分，因此一个 5 个字母的单词值 5 分。
提前致谢我整天都在阅读大量关于填字游戏研究论文的数学符号，这似乎让我陷入了一个圈子。
我将从具有以下特征的词开始：
- 它应该有最大可能的交叉点。
- 其长度应使该长度的单词数在列表中最少。
即字长应该是出现次数最少，交集次数最多的
这种选择的原因是它会最大限度地减少可以选择的单词的进一步可能性。例如。选择了一个大小为 9 并带有 2 个进一步交集的单词。这些相交的词的长度为 6 和 5（比方说）。现在，您已经消除了所有那些长度为 6 和 5 的单词的可能性，它们的第 3 个字符是 'a'，第 2 个字符是 's'（比如，'a' 和 's' 是相交的字母）。
如果有很多地方具有相同的配置，运行 这个选择过程会更深入一两步，以便更好地选择首先填充网格的哪个部分（单词）。
现在，尝试填写第一个选定位置中的所有单词（因为它有最小频率，应该很好用）然后在填字游戏中更深入地填充它。在到达死胡同之前，无论哪个词导致最多点，都应该是您的解决方案。当你走到尽头时，你可以用一个新词重新开始。
这似乎是离散优化中一个非常有趣的问题。你当然是对的；由于字数和可能的位置数，您无法探索 space.
的一小部分另外考虑到 5 分钟的时间限制（相当短），我认为您将很难使用任何可靠的启发式方法。我认为你最好的选择可能是某种随机排列/模拟退火算法。
如果我这样做，我会首先计算词簇，完全忽略纵横字谜结构本身。取一个词，找到与它相交的第二个词。然后找到另一个可以适合这个结构的词（遵守每个词最多 2 个交集），依此类推。您应该最终得到许多这样的集群，您可以按密度（使用的点/面积）对它们进行排名。我认为你应该能够相对快速地做到这一点。
然后对于随机排列/模拟退火部分，对于我的移动，我会将一个簇或未使用的词放在填字游戏本身上，或者移动一个现有的簇/词。只需保存当前得分最高的配置，并在 5 分钟后 return。
如果 5 分钟太短而无法使用随机排列找到任何有意义的东西，另一种方法可能是使用约束传播思想来处理这些集群。