古典的な Boggle ワード ゲームのソルバー実装です。ボグルの激しいゲームで、ボード上のすべての単語を使い果たしたと考えたことはありますか?もう考えないでください！
選択した辞書ファイルとカスタム サイズのボードがあれば、すぐに Boggle ボード内に存在するすべての英単語が得られます。 (私のコンピュータでは、アルゴリズムは 50x50 ボード上で 3 秒未満で実行されます。!!) 私が提供した辞書以外の辞書を使用したい場合でも、問題ありません。各単語が改行で区切られていることを確認してください。
ルート プロジェクト ディレクトリに移動したら、ターミナルで次のコマンドを使用します。
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Boggle.java ファイルが変更されていないと仮定すると、このプログラムは次のボードに含まれるすべての単語を検索します。
Solving:
a r m
b e s
n i m
arsine
rabies
bismer
bersim
barmen
miners
minbar
abime
abies
abner
resin
bines
bisme
biers
benim
besin
besra
berms
bears
bearm
braes
barse
bares
barms
smear
serab
smear
nears
inerm
mines
miner
miser
arse
aren
ares
arms
rems
reim
rein
reis
rems
rabi
mems
mein
mear
mrem
bine
bise
bien
bier
beni
berm
bear
brei
bren
bars
bare
barm
ears
sime
sine
sier
semi
serb
sera
sear
nims
nies
near
inbe
mise
mien
mems
mear
aes
aer
abn
abr
ars
are
arb
arm
rem
rei
ren
res
reb
rem
rea
rms
rab
mem
men
mer
mea
mrs
bim
bin
bis
ben
bes
ber
bra
bae
bar
ems
ems
ers
era
ear
sim
sin
sie
sib
sem
sei
sen
sem
ser
sea
nim
nis
nib
nei
neb
nea
ism
ise
ism
iba
min
mis
mib
men
mem
mer
mea
ご想像のとおり、辞書を引いて、考えられるすべての文字列が英語の単語であるかどうかを確認するのは、非常に困難な作業です。サイズがnxnのボードの場合、最大数はn^2 x (n^2) であることがわかります。有効性をチェックする必要がある文字の可能なシーケンス。これは明らかに非常に速く分解されます。単純な3 x 3ボードでは最大 3265920 回の検証が必要ですが、これは実際の Boggle ボードのサイズですらないです。それで、私はどうやってそれをやったのでしょうか？つまり、 8 x 8ボードを解くだけでも、最大でおよそ10^90の計算が必要になります。ここで私は何かとても賢いことをしたに違いありません。信じられないほど効率的なアプローチが存在することが判明しました。解決アルゴリズムの核心は、トライとして知られる特定のデータ構造を中心に展開します。長さnの文字列が与えられると、トライは、検索している文字列が辞書に存在するかどうかをO(n) (線形) 時間で知らせることができます。これは、辞書ファイル内の考えられる単語ごとに二分検索を実行する場合に比べて、大幅に改善されています。実際、Trie は既存の文字列に文字を追加すると、別の有効な単語が生成されるかどうかを一定時間内にチェックできます。これがアルゴリズムを高速にする理由です。ボード上の各文字から深さ優先検索を実行し、構築した現在の単語に隣接する文字を追加し、含まれる単語が得られた場合は結果に追加します。私たちの辞書では。ある時点で、他の単語の接頭辞ではない文字列に到達した場合は、最も近い有効な接頭辞に戻り、続行します。かなりクールなものです！
ただし、実行時の効率にはコストがかかります。私が使用する辞書ファイルは約 5 メガバイトのテキストなので、すべての単語を辞書 Trie にコンパイルするために必要なスペースは非常に膨大です。実際、辞書からトライを構築するのに最も時間がかかり、私のコンピュータでは平均約 2.2 秒の実行速度でした。明るい面に目を向ければ、辞書 Trie の作成には、解いているボードの次元に関して一定の時間と空間が必要です。したがって、懸念される唯一の要素は、解決アルゴリズムの実行時間です。このアルゴリズムは、最大50 x 50の寸法の基板を 3 秒以内に解決するのに効率的であることが証明されています。極端な境界に興味がある場合、私のシステムでは、アルゴリズムが250 x 250ボードの解を見つけるのに約 77 秒かかりました。
