リストのすべての単語が含まれている最小の「スクラブルボード」

Question

私は、指定されたリストの各単語を抽出できる文字の配列（2D）を構築できるアルゴリズムを探しています。 スクラブルの場合と同様に、単語は互いに交差し、水平、垂直または斜めになります。もちろん、いくつかの明白な解決策がありますが、ここでの目標は可能な限り小さくすることです。交差の回数を最大化することも意味します。

私は人間やコンピュータのいずれかのスクラブルグリッドの大きなセットを使用して機械学習の方法を考えましたが、よりクリーンな方法があると確信しています。

ありがとうございました。

PS：それは芸術プロジェクトのためのものであり、冗談ではありません。

Answer 1

これはかなりのアルゴリズムです。私は、解決策には何らかの再帰が含まれると思われます。

最初にグリッドG0を作成し、すべての四角を空白にしてf（G0）を最適化済みのグリッドにします。次の位置へ移動します G1をうまく - =セットG1、この位置では、この言葉と 空白の他のすべての正方形とグリッドを - 最初の単語 の可能な各位置について

を：

それから私はしようとするだろう

G1を処理するには、f（G1）を再帰的に呼び出すことができます。

大きなグリッドと多くの単語がある場合は、無駄なアルゴリズムなので、これは永遠に実行されますが、典型的なスクラブルボードでは、ノートパソコンで十分に速いと思うはずです。