特定のリストの各単語を抽出できる文字の配列 (2D) を構築できるアルゴリズムを探しています。Scrabble のように、単語は互いに交差し、水平、垂直、または斜めに配置できます。もちろん、いくつかの明白な解決策がありますが、ここでの目標は、可能な限り小さくすることです。これは、交差の数を最大化することも意味します。
私は、人間またはコンピューターによって作成されたスクラブル グリッドの大規模なセットを使用した機械学習方法を考えましたが、よりクリーンな方法があると確信しています。
ご協力いただきありがとうございます。
PS: これはアート プロジェクト用です。冗談ではありません。
それはかなりのアルゴリズムになります。解決策にはある種の再帰が含まれると思います。
最初にグリッド G0 があり、すべての正方形が空白で、f(G0) が最適化された完成したグリッドであるとします。
それから私は試してみます：
最初の単語の可能な位置ごとに - G1 = この単語がこの位置にあり、他のすべての四角形が空白のグリッドを設定します - G1 を計算します 次の位置に移動します
G1 を解決するには、f(G1) を再帰的に呼び出すことができます。
大きなグリッドと多くの単語がある場合、これは無駄なアルゴリズムであるため、実行に永遠に時間がかかりますが、典型的な Scrabble ボードでは、ラップトップで十分に高速であると考えるべきです.