[解決済み] クロスワードを生成するアルゴリズム[クローズド]について

質問

単語のリストがあったとして、それらをどのようにクロスワードのグリッドに並べるか？

基本的には、各単語の開始位置と方向を出力するだけです。

どのように解くのですか？

私は、おそらく最も効率的ではないものの、十分に機能する解決策を思いつきました。基本的には

1. すべての単語を長さの降順で並べ替えます。
2. 最初の単語を取り出し、ボードに配置する。
3. 次の単語を取る。
4. ボード上にすでにあるすべての単語を検索し、この単語と交差する可能性があるかどうか（任意の共通文字）確認します。
5. この単語の可能性のある場所がある場合、ボード上にあるすべての単語をループし、新しい単語が干渉するかどうかを確認します。
6. この単語がボードを壊さないなら、そこに置いてステップ3に進み、そうでなければ、場所を探し続ける（ステップ4）。
7. すべての単語が配置されるか、配置できない状態になるまでこのループを続ける。

これで、動作はするものの、しばしばかなりお粗末なクロスワードができあがります。よりよい結果を得るために、上記の基本的なレシピにいくつかの変更を加えました。

• クロスワードの生成の最後に、単語がいくつ配置されたか (多いほど良い)、ボードの大きさ (小さいほど良い)、および高さと幅の比率 (1 に近いほど良い) に基づいてスコアを付けます。いくつかのクロスワードを生成し、そのスコアを比較して、最も良いものを選びます。
  • 任意の回数のイタレーションを実行する代わりに、任意の時間内にできるだけ多くのクロスワードを作成することにしました。もし、小さな単語リストしか持っていなければ、5 秒で何十もの可能なクロスワードを得ることができるだろう。 より大きなクロスワードは、5～6個の可能性からしか選ばれないかもしれません。
• 新しい単語を配置するとき、許容できる場所を見つけたらすぐに配置するのではなく、その単語の位置に、グリッドのサイズをどれだけ大きくするか、交差点がどれだけあるか (理想的には、それぞれの単語が他の単語と 2-3 回交差することが望ましい) に基づいてスコアを与えます。すべての位置とそのスコアを記録し、最適なものを選択します。