Реализация решателя для классической игры в слова Boggle! Вы когда-нибудь участвовали в напряженной игре в Боггла, думая, что исчерпали все возможные слова на доске? Не думайте больше!
Имея выбранный вами файл словаря и доску с нестандартными размерами, вы мгновенно получите все английские слова, существующие на вашей доске Boggle! (На моем компьютере алгоритм работает менее чем за 3 секунды на доске 50x50!!) Если вы хотите использовать словарь, отличный от того, который я предоставил, это не проблема — просто убедитесь, что каждое слово разделено новой строкой.
Перейдя в корневой каталог проекта, используйте в терминале следующие команды:
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 мегабайт текста, поэтому требования к пространству для компиляции каждого слова в словарь Trie довольно огромны. Создание Trie из словаря на самом деле занимает больше всего времени: средняя скорость выполнения на моем компьютере составляет ~ 2,2 секунды. Если мы посмотрим на положительную сторону, то создание словаря Trie требует постоянного времени и пространства по отношению к размерам доски, которую мы решаем. Отсюда следует, что единственным вызывающим беспокойство элементом является время работы нашего алгоритма решения, который доказал свою эффективность при решении досок размером до 50 x 50 менее чем за 3 секунды. Если вас интересуют экстремальные границы, то в моей системе алгоритму потребовалось около 77 секунд, чтобы найти решения для доски 250 x 250 .
