Une implémentation de solveur pour le jeu de mots classique Boggle ! Avez-vous déjà participé à une partie intense de Boggle en pensant avoir épuisé tous les mots possibles sur le tableau ? Ne réfléchissez plus !
Avec un fichier de dictionnaire de votre choix et un tableau aux dimensions personnalisées, vous aurez tous les mots anglais qui existent dans votre tableau Boggle en un rien de temps ! (Sur mon ordinateur, l'algorithme s'exécute en <3 s sur un tableau 50x50 !!) Si vous souhaitez utiliser un dictionnaire autre que celui que j'ai fourni, ce n'est pas un problème - assurez-vous simplement que chaque mot est séparé par une nouvelle ligne.
Une fois accédé au répertoire racine du projet, utilisez les commandes suivantes dans le terminal :
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
En supposant que le fichier Boggle.java n'ait pas été modifié, ce programme trouvera tous les mots contenus dans le tableau suivant :
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
Comme vous pouvez l’imaginer, chercher dans un dictionnaire pour vérifier si chaque séquence de lettres possible est un mot anglais serait une tâche assez ardue. Il s'avère que pour toute carte de taille nxn , il y a un maximum de n^2 x (n^2) ! séquences possibles de lettres dont la validité doit être vérifiée. Cela s'effondre clairement très rapidement : une simple carte 3 x 3 nécessite au maximum 3265920 validations, et ce n'est même pas la taille d'une vraie carte Boggle ! Alors comment ai-je fait ? Je veux dire, même résoudre un tableau 8 x 8 prendrait au maximum environ 10 ^ 90 calculs ! J'ai dû faire quelque chose de vraiment intelligent ici. Il s’avère qu’il existe une approche incroyablement plus efficace. Le nœud de l’algorithme de résolution tourne autour d’une structure de données particulière connue sous le nom de Trie. Étant donné une chaîne de longueur n , un Trie est capable de nous dire si la chaîne que nous recherchons existe ou non dans notre dictionnaire en temps O(n) (linéaire) ! Il s'agit d'une énorme amélioration par rapport à l'exécution d'une recherche binaire pour chaque mot possible dans le fichier de dictionnaire. En fait, un Trie peut vérifier si l'ajout d'une lettre à une chaîne existante entraînera ou non un autre mot valide en temps constant ! C'est ce qui rend l'algorithme aussi rapide qu'il l'est : nous effectuons d'abord une recherche approfondie à partir de chaque lettre du tableau, ajoutant une lettre adjacente au mot actuel que nous avons construit et l'ajoutons à nos résultats s'il produit un mot contenu. dans notre dictionnaire. Si à un moment donné nous atteignons une chaîne qui n’est le préfixe d’aucun autre mot, nous revenons au préfixe valide le plus proche et continuons. Des trucs plutôt sympas !
L'efficacité d'exécution a cependant un coût. Le fichier de dictionnaire que j'utilise contient environ 5 mégaoctets de texte, donc l'espace requis pour compiler chaque mot dans un dictionnaire Trie est assez énorme. Construire un Trie à partir du dictionnaire est en fait ce qui prend le plus de temps à réaliser, avec une vitesse d'exécution moyenne d'environ 2,2 secondes sur mon ordinateur. Si l’on regarde le bon côté des choses, la création du dictionnaire Trie nécessite un temps et un espace constants par rapport aux dimensions du tableau que nous résolvons. Il s’ensuit que le seul élément de préoccupation est le temps d’exécution de notre algorithme de résolution, qui s’est avéré efficace pour résoudre des cartes allant jusqu’à 50 x 50 en moins de 3 secondes. Si vous êtes intéressé par les limites extrêmes, il a fallu à l'algorithme environ 77 secondes sur mon système pour trouver des solutions à une carte de 250 x 250 .
