经典 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板的解决方案。
