經典 Boggle 文字遊戲的解算器實作！您是否曾經參加過一場激烈的 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 次計算！我一定在這裡做了一些非常聰明的事情。事實證明，有一種更有效的方法。求解演算法的關鍵圍繞著一種稱為 Trie 的特定資料結構。給定一個長度為n的字串，Trie 能夠在O(n) （線性）時間內告訴我們要搜尋的字串是否存在於我們的字典中！與對字典檔案中每個可能的單字執行二進位搜尋相比，這是一個巨大的改進。事實上，Trie 可以檢查在現有字串中添加一個字母是否會在常數時間內產生另一個有效單字！這就是演算法如此快速的原因：我們從板上的每個字母執行深度優先搜索，將相鄰的字母添加到我們構建的當前單詞中，如果產生包含的單詞，則將其附加到我們的結果中在我們的字典裡。如果在某個時刻我們到達的字串不是任何其他單字的前綴，我們將回溯到最接近的有效前綴並繼續。很酷的東西！
然而，運作時效率是有代價的。我使用的字典檔案大約有 5 MB 的文本，因此將每個單字編譯成字典 Trie 的空間要求是相當巨大的。從字典建立 Trie 實際上是需要最長時間才能完成的事情，在我的計算機上平均執行速度約為 2.2 秒。如果我們往好的方面看，字典 Trie 的創建需要相對於我們正在求解的棋盤的尺寸而言恆定的時間和空間。因此，唯一值得關注的因素是我們的求解演算法的運行時間，事實證明，該演算法可以在不到 3 秒的時間內高效地求解尺寸高達50 x 50的板。如果您對極限邊界感興趣，我的系統中的演算法大約需要 77 秒才能找到250 x 250板的解決方案。
