1

我希望有一种方法可以在 Python 中创建以下类型的双字正方形。我有一个给定的单词列表，其中应该包含要在单词 square 中使用的单词。我能想到的当前方式是“蛮力”方式，对于大于 4x4 网格的任何东西来说效率都非常低。 

S C E N T 
C A N O E 
A R S O N 
R O U S E 
F L E E T

我将不胜感激任何帮助。

4

2 回答 2

4

图论/搜索算法可以在这里提供帮助。假设我们已经像这样布置了电路板：

SCENT
CANOE
ARSON
ROUSE
?????

…而且我有>1个词要坚持在最后一个位置。棋盘的这种状态（上图）是树中的一个节点。假设在那个地方还有 5 个词要坚持：我还有 5 个可以去的状态（节点）。这在过程的早期更有价值：

SCENT
?????
?????
?????
?????

同样，将其视为树中的一个节点。在这里，也许我有 13 个可能的单词。这 13 个选项中的每一个都将我带到一个有 12 个选项的节点，这 12 个选项中的每一个都有 11 个选项，等等。我们正在探索的树如下所示：

          ?
          |
        SCENT
        ?????
        ?????
        ?????
        ?????
    /---/ | \-----\----\
   /      |   \    \    \
  |       |    \    \    \
SCENT  SCENT    ?    ?    ?
CANOE  ARSON
?????  ?????   ... etc ...
?????  ?????
?????  ?????
| |    /  | \
| |   /   \  \
? ?  /     |  \
   SCENT   ?   ?
   ARSON
   CANOE
   ?????
   ?????

蛮力解决方案将完全探索这棵树，访问每个节点。但是，节点的数量通常非常高。我们的想法是有效地探索它：如果我们可以确定仅填充两个单词的“节点”将永远不会产生任何有效的解决方案，我们可以立即停止探索：我们消除该节点及其下方的所有节点。维基百科关于蛮力搜索的文章提到了这一点：

加速蛮力算法的一种方法是通过使用特定于问题类的启发式方法来减少搜索空间，即候选解决方案的集合。例如，在八皇后问题中，挑战是将八个皇后放在标准棋盘上，这样没有皇后攻击任何其他皇后。由于每个皇后可以放置在 64 个方格中的任何一个中，因此原则上有 648 = 281,474,976,710,656 种可能性需要考虑。但是，因为皇后都是一样的，而且没有两个皇后可以放在同一个格子上，所以候选者都是从所有64个格子中选择一组8个格子的可能方式；这意味着 64 选择 8 = 64!/56!/8! = 4,426,165,368 个候选解决方案——大约是之前估计的 1/60,000。此外，没有两个皇后在同一行或同一列的安排可以成为解决方案。

正如这个例子所示，一点点分析通常会导致候选解决方案的数量急剧减少，并可能将一个棘手的问题变成一个微不足道的问题。

那么，我们该怎么做呢？老实说，这是你必须聪明的部分。您可能可以做多种可能的事情。例如，当我们填写两个单词时：

SCENT
CANOE
?????
?????
?????

我们看到，要使其成为有效状态，我们需要有以 SC、CA、EN、NO 和 TE 开头的单词。（一旦我们填写了最后的单词，这些将是沿垂直方向的单词。）如果我们缺少以这些前缀开头的单词，那么这将永远不会产生有效的解决方案，因为我们没有可能的垂直单词. 如果我们能够快速确定这一点，那么我们可以快速消除这种状态，以及处于这种状态的所有可能结果：如果这在蛮力中尤其早期，这可能是有价值的。

我们可以通过生成所有单词的所有前缀的集合，在 O(1) 时间内完成诸如“前缀检查”之类的操作。假设n个长度为L的单词，这需要 O( nL ) 来完成。要检查前缀是否有效，我们只需查看它是否在集合中。

现在当然，如果我们的单词列表包含（例如）所有可能的 5 个字母单词，这将让我们无处可去，因为每个前缀都可以。但是，您可能没有得到这样的清单。

您可以将前缀集扩展为前缀映射 → 具有该前缀的单词。如果前缀中只有一个单词，我们现在可以将它放在板上。（如果它不属于那里，那么什么都不会。）当然，这会使在板上放置更多单词变得更加复杂。

图论也将有助于解决蛮力：一旦您将问题视为图形或树，您会发现“蛮力”只是一种树探索算法：它只是节点本身，以及您如何在它们之间移动他们不同。

于 2013-10-22T00:12:59.377 回答
1

我会列出一个有共同字母的单词对，以及这些单词中字母的索引，然后搜索不同的交叉点组合，直到你得到一个将单词排列成正方形的交叉点组合。

于 2013-10-21T23:19:07.823 回答