6

問題は基本的に、「多くの単語を含むゲーム 'Boggle' の適切なグリッドを生成するにはどうすればよいか」であり、5 文字以上の単語がたくさんあることを良いと定義します。

Boggle は、文字が書かれたサイコロを 4x4 のグリッドに配置して転がすゲームです。例：

H S A V
E N I S
K R G I
S O L A

文字を横、縦、斜めにつなげて言葉を作ることができます。上記の良い例のグリッドでは、「VANISHERS」、「VANISHER」、「KNAVISH」、「ALIGNERS」、「SAVINGS」、「SINKERS」、および使用する辞書に応じて約 271 の他の単語 (「AS」など) を作成できます。 、「私」、「AIR」、「SIN」、「IS」など...

悪い例として、このグリッド

O V W C
T K Z O
Y N J H
D E I E

~44 個の単語しかなく、そのうち 2 個だけが 4 文字を超えています。「TYNED」と「HINKY」。

似たような質問がたくさんありますが、AFAICT はこの正確な質問ではありません。これは明らかにゲーム「Scramble with Friends」への言及です。

ランダムに文字を選択する最初の解決策には、誤ってすべての子音を選択すると、単語がなくなるという問題があります。いくつかのランダムな母音を追加するだけでは、適切な単語のセットを保証するには不十分です。1 ～ 4 文字の単語しか取得できない場合がありますが、優れたアルゴリズムでは、7 文字を超える多くの単語を含む 200 単語を超える文字セットが選択されます。

私はどんなアルゴリズムにもオープンです。明らかに、可能性のあるすべてのグリッドを見つけて、それらを最も単語数の多いグリッドでソートするブルート フォース ソリューションのコードを書くことはできますが、その単純なソリューションを実行するには永遠に時間がかかります。

長い単語 (8 ～ 16 文字) を選択し、それらの文字をランダムにグリッドに配置するなど、さまざまなヒューリスティックを想像できますが、実際には単語を作成できる方法で、残りのスペースを埋めます。私はまだ試していませんが、それだけでは良い単語セットを保証するには不十分だと思います。

ソリューションでは、単語の共通部分を知るために辞書を前処理する必要がある可能性があります。たとえば、「ing」、「ers」、「ght」、「tion」、「land」で終わるすべての単語。または、どういうわけかそれらを共有文字のグラフに整理します。「ing」または「ers」が頻繁に挿入されるように、特定の文字セットに重みを付ける場合があります。

アイデア？

4

3 に答える 3

0

Boggle の仕組みは、側面に特定の文字が書かれた 6 面ダイスがあることです。これらのサイコロはランダムに 16 のマスに割り当てられ、ロールされます。一般的な文字は、サイコロのより多くの面に出現します。周りを検索してください - あなたはサイコロの正確なセットを得ることができるかもしれません.

于 2013-08-11T23:17:50.640 に答える
0

  1. 辞書から統計的な文字頻度と文字ペア頻度を計算します。

  2. 中央の 4 つのマスからランダムに 1 つを選ぶことから始めます。

  3. 1 文字の頻度で重み付けされた正方形の文字をランダムに選択します。

  4. 再帰的に:

    4.1. 空の接続されたすべての正方形の 1 つをランダムに選択します。

    4.2. 接続された塗りつぶされた四角形の二重文字頻度と接続された空の四角形の単一文字頻度の組み合わせ (平均) によって重み付けされたその四角形の文字をランダムに選択します。

出来上がり！

PS また、グリッド内の現在の出現数に基づいてグローバル文字のディレーティングを 4.2 に追加して実験することもできます。

于 2013-08-12T05:34:10.297 に答える