クロスワードパズルの生成
1. 序章
このチュートリアルでは、クロスワードパズルの生成のトピックを探求します。 これは、単語のセットを効果的にグリッドに配置して、それらが重なるようにします。
特に、最高のクロスワードを生成するために単語を配置する場所を決定する方法に焦点を当てます。
2. 反復配置
開始アルゴリズムは、スペースがなくなるまで単語をグリッドに繰り返し配置することです。これは、単語リストをシャッフルしてから下に移動し、セットに到達するまで各単語をグリッドに配置することで機能します。配置する単語の数。
このアルゴリズムは、単語を配置できる無限グリッドを想定していることに注意してください。 実際には、これは明らかに当てはまらないので、どの実装も私たちの制約の範囲内で機能する必要があります。
2.1. アルゴリズム
ここでは多くのことが行われていますが、すべてが上記のアルゴリズムで表現されているわけではありません。 特に、単語を配置し、単語が合法であるかどうかをチェックするためのメカニズムは、簡潔にするために省略されています。
最初の単語はグリッドの真ん中に配置されています。 その後、他のすべての単語はそこから展開されます。
後続の単語は、単語内の各文字を繰り返し処理し、グリッドを繰り返し処理して、この文字が含まれる位置を見つけることで場所を見つけます。単語が合法的にここに配置できるかどうかを確認します。 1。 これらのチェックの最初のパスが通過するまで続行します。この場合、ここで停止してこの単語を配置します。
場合によっては、適切なスロットがありません。 たとえば、共通の文字がない場合や、単語を合法的に配置できる場所がない場合があります。 次に、十分な単語を配置するか、単語がなくなるまで続行します。
2.2. 実施例
このアルゴリズムを試してみて、実際の動作を見て、最初のクロスワードを作成する方法を示しましょう。
最初にランダムに選択された単語は「SHOP」です。これはグリッドに直接配置され、次のようになります。
この後、アルゴリズムの大部分から始めます。
次の単語は「GREEDS」です。最初の一致が見つかるまで、単語内のすべての文字とクロスワード内のすべてのセルの各文字を繰り返し処理します。 この場合、「GREEDS」の最後の「S」は、
次に、単語をここに配置できるかどうか（つまり、他の単語に悪影響を与えるかどうか）を確認し、配置できる場合は、単語の開始位置と進行方向を決定します。
最後に、それを追加します。
リストから取得する次の単語は「FAINT」です。この単語は配置できず、スキップされます。 この単語のすべての文字とクロスワードグリッドのすべてのセルを繰り返し処理した後、一致するものはまったく見つかりません。
次に、「SIMPLIFY」を取得します。最初の潜在的なスロットは、「SHOP」の先頭にある「S」です。ただし、できません。 「GREEDS」という単語と競合するため、ここに単語を配置します。そのため、「SIMPLIFY」に「P」が見つかるまで、セルをスキャンし続けます。 は、「SHOP」の「P」と一致します。
これは適切な場所であり、他の単語の邪魔になりません。そのため、ここに追加できます。
次に、単語がなくなるか、グリッドに配置された特定の数に達するまで、後続の単語ごとにこのプロセスを繰り返すことができます。
この時点で、完成したクロスワードができました。
3. 繰り返し生成
これまでのところ、クロスワードグリッドを生成でき、最初の試みは非常にうまくいきました。 ただし、別の単語セットは印象的でないものを生成する可能性があります：
この場合、原因はクロスワードでランダムに選択された単語にありました。
3.1. アルゴリズム
多くのクロスワードグリッドを生成し、最適なグリッドを選択することで、全体的な結果を改善できます。
クロスワードをスコアリングする方法がある場合は、単純に多くのグリッドを生成し、それぞれにスコアを付けて、最高のスコアのみを保持することができます。
これを行うとき、ループを指定された回数、指定された時間繰り返すことができます（5分で生成できる最高のクロスワードを取得したい場合があります）、または特定の値を超えるスコアを持つ最初のクロスワードです。
または、これらの組み合わせでさえ、特定の値を超えるスコアを持つ最初のクロスワードパズル、または1,000回の反復で生成できる最高のクロスワードパズルのいずれか早い方が必要な場合があります。
3.2. クロスワードの採点
多くのクロスワードを生成したら、「最良」の意味を決定する必要があります。これは、生成するクロスワードのタイプによって異なりますが、次のようなものがあります。
- 満たされた数対。 空白の正方形：塗りつぶされた正方形が多いほど、クロスワードの密度が高くなります。
- 幅と幅の比率。 高さ：これが1.0に近いほど、結果のグリッドはより正方形になります。
- 単語の平均の長さ：次に、必要に応じて長い単語または短い単語のいずれかを選択できます。
またはあなたが使いたい他のもの。 唯一の重要な詳細は、すべてのクロスワードが同じように採点されることです。
たとえば、より密度の高い、より正方形のクロスワードを選択するスコアリングアルゴリズムは、次のようになります。
ここで、次のスコアを生成します。
- 10*最も短い側と最も長い側の比率。 これは、正確に正方形である場合、数値の最大値が10になり、長方形が多いほど数値が小さくなることを意味します。
- 20*塗りつぶされた正方形と空の正方形の比率。 これは、正方形のちょうど半分が空の場合は20、半分以上が埋められている場合は20を超え、半分以上が空の場合は20未満になることを意味します。
これまでに見た2つのグリッドにこれを適用すると、最初のグリッドのスコアは「 21.92672999 」で、2番目のグリッドのスコアは「」であることがわかります。 12.3653512 “なので、最初のグリッドの方が明らかに優れています。
4. 繰り返される単語の配置
これで、単語をグリッドに配置し、これを何度も繰り返し、最良の結果を選択するための一般的なアルゴリズムができました。ただし、これにより、常に同じ方法でグリッドが生成されます。つまり、最初に新しい単語を配置します。それが合うこと。
たとえば、2番目のグリッドは「UNAPPROVED」を「ODIOUS」、の「U」から配置しました。これは、最初の文字が最初に収まる場所だからです。 これは必ずしも言葉を置くのに最適な場所ではないかもしれません。
代わりに、代わりに「O」で交差するように配置した方がよい場合があります。
これにより、以前の14×6ではなく10×6の正方形のクロスワードが生成されます。これは、スコアリングアルゴリズムによってより望ましいものです。
4.1. アルゴリズム
クロスワードのセットのどれが「最良」であるかを判断する手段がすでにあります。これは、スコアリングアルゴリズムです。
これは、最初に新しい単語のすべての配置を見つけ、次にそれぞれを繰り返して、最高の新しいスコアを生成する配置を見つけることによって機能します。 その後、このボードが新しいボードになります。
これを「UNAPPROVED」、のプレースメントに適用すると、
ただし、代わりに「MANIA」の「A」で交差した場合、「17.25806452」のスコアが得られます。これはさらに優れています。
4.2. さらなる拡大
これまでのところ、これは任意の単語に最適な配置を見つけます。 ただし、1つの単語の配置が最適ではない場合、最終的には全体的な結果が向上する可能性があります。たとえば、上記のボードは「未承認」という単語の配置として最適でしたが、結果としていくつか文字は、不可能ではないにしても、単語を配置するのが非常に困難です。
より深いオプションのツリーを構築することで、これを改善できる可能性があります。 この単語のすべての可能な配置だけでなく、次の単語のすべての可能な配置のそれぞれについて生成し、特定の深さまで進み続けることができます。 次に、ツリーの一番上で、一番下で最高のスコアにつながるノードを選択します。 これは、過去に調査した他の検索アルゴリズムと同様であり、優れた結果をもたらす可能性があります。
5. 結論
ここでは、クロスワードパズルを生成するためのいくつかのアルゴリズムを見て、それぞれが以前のパズルを改善するのにどのように役立つか、そしてさらに何ができるかを探りました。
ツリー検索アルゴリズムを実装して、思いつくパズルを見てみませんか。
