¡Una implementación de resolución para el clásico juego de palabras Boggle! ¿Alguna vez has competido en un intenso juego de Boggle pensando que has agotado todas las palabras posibles en el tablero? ¡No lo pienses más!
Con un archivo de diccionario de su elección y un tablero con dimensiones personalizadas, ¡tendrá todas las palabras en inglés que existen en su tablero Boggle en poco tiempo! (¡¡En mi computadora el algoritmo se ejecuta en < 3 segundos en un tablero de 50x50!!) Si desea utilizar un diccionario distinto al que le proporcioné, no hay problema; solo asegúrese de que cada palabra esté separada por una nueva línea.
Una vez navegado al directorio raíz del proyecto, use los siguientes comandos en la terminal:
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Suponiendo que el archivo Boggle.java no haya sido modificado, este programa encontrará todas las palabras contenidas en el siguiente tablero:
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 puedes imaginar, buscar en un diccionario para comprobar si cada secuencia posible de letras es una palabra en inglés sería una tarea bastante ardua. ¡Resulta que para cualquier tablero de tamaño nxn , hay un máximo de n^2 x (n^2)! posibles secuencias de letras cuya validez debe comprobarse. Esto claramente se estropea muy rápido: un tablero simple de 3 x 3 requiere como máximo 3265920 validaciones, ¡y esto ni siquiera es del tamaño de un tablero Boggle real! Entonces, ¿cómo lo hice? Quiero decir, ¡incluso resolver un tablero de 8 x 8 requeriría un máximo de aproximadamente 10 ^ 90 cálculos! Debo haber hecho algo realmente inteligente aquí. Resulta que existe un enfoque increíblemente más eficiente. El quid del algoritmo de resolución gira en torno a una estructura de datos particular conocida como Trie. Dada una cadena de longitud n , un Trie puede decirnos si la cadena que estamos buscando existe o no en nuestro diccionario en tiempo O(n) (lineal). Esta es una gran mejora con respecto a la ejecución de búsqueda binaria para cada palabra posible en el archivo del diccionario. De hecho, un Trie puede verificar si agregar una letra a una cadena existente dará como resultado otra palabra válida en tiempo constante. Esto es lo que hace que el algoritmo sea tan rápido: realizamos una primera búsqueda profunda de cada letra en el tablero, agregamos una letra adyacente a la palabra actual que hemos creado y la agregamos a nuestros resultados si produce una palabra contenida. en nuestro diccionario. Si en algún momento llegamos a una cadena que no es un prefijo de ninguna otra palabra, retrocedemos hasta el prefijo válido más cercano y continuamos. ¡Cosas geniales!
Sin embargo, la eficiencia del tiempo de ejecución tiene un costo. El archivo de diccionario que uso tiene aproximadamente 5 megabytes de texto, por lo que los requisitos de espacio para compilar cada palabra en un diccionario Trie son bastante enormes. Construir un Trie a partir del diccionario es en realidad lo que lleva más tiempo, con una velocidad de ejecución promedio de ~2,2 segundos en mi computadora. Si miramos el lado positivo, la creación del diccionario Trie requiere de un tiempo y espacio constante respecto a las dimensiones del tablero que estamos resolviendo. De ello se deduce que el único elemento de preocupación es el tiempo de ejecución de nuestro algoritmo de resolución, que ha demostrado ser eficiente para resolver tableros con dimensiones de hasta 50 x 50 en menos de 3 segundos. Si está interesado en los límites extremos, al algoritmo le tomó alrededor de 77 segundos en mi sistema encontrar soluciones para una placa de 250 x 250 .
