arrays - 包含列表中每个单词的最小“​​拼字板”

Question

我正在寻找一种能够构建字母数组（2D）的算法，我可以从中提取给定列表的每个单词。就像在拼字游戏中一样，单词可以相互交叉，可以是水平的、垂直的或对角的。当然有一些明显的解决方案，但这里的目标是让它尽可能小，这也意味着最大化交叉的数量。

我已经想到了一种使用大量拼字游戏网格的机器学习方法，无论是由人类还是由计算机制作，但我确信有一种更清洁的方法。

谢谢你的帮助。

PS：这是一个艺术项目，不是开玩笑。

Answer 1

那将是相当多的算法。我怀疑解决方案将涉及某种递归。

假设您有一个网格 G0 开始，所有方块都为空白，并且 f(G0) 是优化后的完整网格。

然后我会尝试：

对于第一个单词的每个可能位置 - 设置 G1 = 这个位置的这个单词的网格和所有其他方块空白 - 计算 G1 继续到下一个位置

要计算 G1，您可以递归调用 f(G1)。

如果你有一个很大的网格和很多单词，这将需要永远运行，因为它是一种浪费的算法，但对于典型的 Scrabble 板，我认为它在笔记本电脑上会足够快。