algorithm - 字母的最大可能矩形

Question

Write a program to find the largest possible rectangle of letters such that every row forms a word (left to right) and every column forms a word (top to bottom).

我发现了这个有趣的问题。这不是家庭作业，尽管听起来可能是这样。 (我不在学校)。我这样做是为了好玩。

Example

From cat, car, ape, api, rep, tip we get the following rectangle (which is a square):

c a r
a p e
t i p

我最初的想法是构建某种前缀树，这样我就可以检索以特定字符串开头的所有单词。当我们已经有 2 个或更多单词(从上到下或从左到右阅读)并且我们需要找到下一个要添加的单词时，这将很有用。

还有其他想法吗？

编辑

这可以用长方体(3D 矩形)来完成吗？

如果它需要在对角线上有有效的单词怎么办(创意来源:user645466)；如何优化它的算法？

Answer 1

设 D 为字典。固定 m 和 n。我们可以将寻找 m × n 矩形的问题表述为 constraint satisfaction problem (CSP)。

x_i,1…x_i,n ∈ D    ∀i ∈ {1, …, m}
x_1,j…x_m,j ∈ D    ∀j ∈ {1, …, n}
x_i,j ∈ {A, …, Z}    ∀i ∈ {1, …, m}, ∀j ∈ {1, …, n}

解决 CSP 的一种非常常见的方法是将回溯与约束传播相结合。粗略地说，回溯意味着我们选择一个变量，猜测它的值，然后用少一个变量递归地解决子问题，而约束传播意味着试图减少每个变量的可能性(可能为零，这意味着没有解决方案)。

例如，我们可以通过选择 x_1,1 = Q 来开始一个 3 × 3 的网格。

Q??
???
???

对于英语词典，x_1,2 和 x_2,1 的唯一可能性是 U(在拼字游戏之前的“单词”)。

解决 CSP 的艺术是在回溯和约束传播之间取得平衡。如果我们根本不传播约束，那么我们只是在使用蛮力。如果我们完美地传播约束，那么我们就不需要回溯，但是一个自行解决 NP-hard 问题的传播算法可能运行起来相当昂贵。

在这个问题中，除非我们有良好的数据结构支持，否则在每个回溯节点使用大型字典将变得昂贵。我将概述一种使用 trie 的方法或 DAWG快速计算前缀扩展为完整单词的字母集。

在每个回溯节点，我们分配的变量集是一个 Young 画面。换句话说，在它上面和左边的变量被赋值之前，没有变量被赋值。在下图中，. 表示已分配的变量，* 和 ? 表示未分配的变量。

.....*
...*??
...*??
..*???
*?????

标记为* 的变量是下一个要赋值的候选变量。有多个选择而不是每次都选择一个固定变量的优点是一些变量排序可能比其他变量排序好得多。

对于每个 *，在 trie/DAWG 中进行两次查找，一次用于水平方向，一次用于垂直方向，并计算下一个字母集的交集。一种经典策略是选择可能性最少的变量，希望我们能更快地达到矛盾。我喜欢这种策略，因为它会在存在可能性为零的变量时自然修剪，而在存在可能性为 1 的变量时自然传播。通过缓存结果，我们可以非常快速地评估每个节点。