Uma implementação de solucionador para o clássico jogo de palavras Boggle! Você já competiu em um jogo intenso de Boggle pensando que esgotou todas as palavras possíveis no tabuleiro? Não pense mais!
Com um arquivo de dicionário de sua escolha e um quadro com dimensões personalizadas, você terá todas as palavras em inglês que existem em seu quadro Boggle em um piscar de olhos! (No meu computador, o algoritmo é executado em <3s em uma placa 50x50!!) Se você quiser usar um dicionário diferente daquele que forneci, não há problema - apenas certifique-se de que cada palavra esteja separada por uma nova linha.
Depois de navegar até o diretório raiz do projeto, use os seguintes comandos no terminal:
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Supondo que o arquivo Boggle.java não tenha sido modificado, este programa encontrará todas as palavras contidas no seguinte quadro:
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
Como você pode imaginar, consultar um dicionário para verificar se cada sequência possível de letras é uma palavra em inglês seria uma tarefa bastante árdua. Acontece que para qualquer placa de tamanho nxn , há no máximo n^2 x (n^2)! possíveis sequências de letras que precisam ser verificadas quanto à validade. Isso claramente quebra muito rápido - uma placa simples 3 x 3 requer no máximo 3.265.920 validações, e isso nem é do tamanho de uma placa Boggle real! Então, como eu fiz isso? Quero dizer, mesmo resolver uma placa 8 x 8 exigiria no máximo cerca de 10 ^ 90 cálculos! Devo ter feito algo muito inteligente aqui. Acontece que existe uma abordagem incrivelmente mais eficiente. O cerne do algoritmo de resolução gira em torno de uma estrutura de dados específica conhecida como Trie. Dada uma string de comprimento n , um Trie é capaz de nos dizer se a string que procuramos existe ou não em nosso dicionário em tempo O(n) (linear)! Esta é uma grande melhoria em relação à execução da pesquisa binária para cada palavra possível no arquivo de dicionário. Na verdade, um Trie pode verificar se adicionar ou não uma letra a uma string existente resultará em outra palavra válida em tempo constante! Isto é o que torna o algoritmo tão rápido: realizamos uma primeira pesquisa profunda de cada letra no quadro, adicionando uma letra adjacente à palavra atual que construímos e anexando-a aos nossos resultados se produzir uma palavra contida em nosso dicionário. Se em algum momento chegarmos a uma string que não é um prefixo de nenhuma outra palavra, voltamos para o prefixo válido mais próximo e continuamos. Coisas muito legais!
A eficiência do tempo de execução, entretanto, tem um custo. O arquivo de dicionário que uso tem aproximadamente 5 megabytes de texto, então os requisitos de espaço para compilar cada palavra em um dicionário Trie são enormes. Construir um Trie a partir do dicionário é, na verdade, o que leva mais tempo para ser realizado, com velocidade de execução média de aproximadamente 2,2 segundos no meu computador. Se olharmos pelo lado positivo, a criação do dicionário Trie requer tempo e espaço constantes em relação às dimensões do tabuleiro que estamos resolvendo. Conclui-se que o único elemento preocupante é o tempo de execução do nosso algoritmo de resolução, que se mostrou eficiente na resolução de placas com dimensões de até 50 x 50 em menos de 3 segundos. Se você estiver interessado nos limites extremos, o algoritmo levou cerca de 77 segundos no meu sistema para encontrar soluções para uma placa de 250 x 250 .
