任意大小网格内的最佳4字布局

Question

问题陈述：

给出四个单词，把它们放在一个m×n的正方形网格中，这样网格的面积就越小越好。在

单词必须在网格内从左到右、从上到下排列。字母可以重叠，但不能形成附加的单词。所有的词都必须在一条巨大的链条上相互联系。在

可以用4个单词“一，二，三，四”组成的网格示例。注意最后一个网格是最优化的。在

我正在努力学习python，我认为这将是一个很好的应用程序来切齿。在

有什么想法如何组织我的数据和算法来解决这样的问题？我不是在寻找一个直截了当的答案，而是一些建议，比如：

使用此库、此类或此数据结构。或者像这样在可用空间中迭代。在

Answer 1

想想你需要的最大网格尺寸是多少？如果单词是one，two，three，four，那么最大的网格大小将是

12 x 12. This is the size of a grid where each word is placed end to end, sharing the last letter of the previous word.

现在我们有了空间。你怎么把单词放在空格里？试着想出一种暴力的方法。这需要什么？在

Try iterating through all possible combinations of patterns. You can place each word 24 ways and there are 4 words, so you have ~500,000 combinations which is not many for modern computers to chunk through. See which patterns actually satisfy the criteria (letters match up, etc).

一旦你有了一个蛮力的方法，你怎么能改进它呢？在

在数据结构方面，您只需要一个可以存储字符的网格。可以使用嵌套列表结构、numpy数组、pandas或其他很多东西。先试着简单地解决问题，然后再改进。在