Accueil > Réalisations > Logiciels > Jeux de l’esprit > Boggle > Boggle : algorithme de résolution
Boggle : algorithme de résolution
mardi 25 janvier 2011, par
Le programme ci dessous prend en argument la grille (suite de 16 lettres) et renvoie la liste des mots trouvés, avec leur score, sans dédoublonage (il suffit de passer le résultat de cette commande à un « sort -u » pour avoir la liste réelle des solutions).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "words.h"
#define GRID_SIZE 4
#define MIN_WORD_LEN 3
#define MAX_WORD_LEN (GRID_SIZE*GRID_SIZE)
#define NOT_USED 0
#define USED 1
#define DICT_SIZE ((sizeof(dict)/sizeof(char *))-1) // -1 a cause du NULL
char letters[GRID_SIZE][GRID_SIZE];
int grid[GRID_SIZE][GRID_SIZE];
char choices[MAX_WORD_LEN+1];
int points[] =
{
0, // Mots de 0 lettres
0, // Mots de 1 lettres
0, // Mots de 2 lettres
1, // Mots de 3 lettres
1, // Mots de 4 lettres
2, // Mots de 5 lettres
3, // Mots de 6 lettres
5, // Mots de 7 lettres
11, // Mots de 8 lettres
11, // Mots de 9 lettres
11, // Mots de 10 lettres
11, // Mots de 11 lettres
11, // Mots de 12 lettres
11, // Mots de 13 lettres
11, // Mots de 14 lettres
11, // Mots de 15 lettres
11, // Mots de 16 lettres
};
int TestWord(int depth)
{
static int bot, top, cen, res;
int result = 0;
choices[depth] = '\0';
bot = 0;
top = DICT_SIZE-1;
while(1)
{
cen = (bot+top)/2;
res = strcmp(choices, dict[cen]);
if (!res)
{
result = 1;
printf("%d\t%s\n", points[strlen(choices)], choices);
return result;
}
else if (bot >= top)
{
// Si la racine existe, on descend en profondeur, sinon c'est inutile
//
result = !strncmp( choices, dict[cen], depth);
if( result) return result;
if( top+1<DICT_SIZE) result = !strncmp( choices, dict[top+1], depth);
if( result) return result;
if( bot-1>0) result = !strncmp( choices, dict[bot-1], depth);
return result;
}
else if (res > 0)
{
bot = ++cen;
}
else
{
top = --cen;
}
}
return result;
}
void Recurse(int x, int y, int depth)
{
int res;
if (x < 0 || y < 0 || x >= GRID_SIZE || y >= GRID_SIZE)
{
return;
}
if (grid[x][y] == USED)
{
return;
}
grid[x][y] = USED;
choices[depth++] = letters[x][y];
if (depth >= MIN_WORD_LEN)
{
res = TestWord(depth);
}
else
{
res = 1;
}
if( res && depth < MAX_WORD_LEN )
{
Recurse(x-1, y-1, depth);
Recurse(x , y-1, depth);
Recurse(x+1, y-1, depth);
Recurse(x-1, y , depth);
Recurse(x+1, y , depth);
Recurse(x-1, y+1, depth);
Recurse(x , y+1, depth);
Recurse(x+1, y+1, depth);
}
grid[x][y] = NOT_USED;
}
int main(int argc, char *argv[])
{
int i, j;
char buf[128];
FILE *f;
int k;
if( argc != 2 || strlen(argv[1]) != 16 )
{
fprintf( stderr, "Syntax is %s <16 letters grid>\n", argv[0] );
exit(1);
}
k=0;
for (j = 0; j < GRID_SIZE; ++j)
{
for (i = 0; i < GRID_SIZE; ++i)
{
letters[i][j] = argv[1][k++];
grid[i][j] = NOT_USED;
}
}
for (j = 0; j < GRID_SIZE; j++)
for (i = 0; i < GRID_SIZE; i++)
Recurse(i, j, 0);
exit(0);
}Remarque : ce programme inclut le fichier « words.h » qui est le dictionnaire des mots utilisés. Ce fichier doit contenir les mots écrits en lettres capitales et triés par ordre alphabétique de la manière suivante :
#ifndef __WORDS_H__
#define __WORDS_H__
static char *dict[] =
{
"AAS",
"ABACA",
.../...
"ZYTHUM",
"ZYTHUMS",
NULL
};
#endifIl aurait bien sur été possible de lire le dictionnaire depuis un fichier texte à chaque lancement du programme mais cela présenterait deux inconvénients :
- il faudrait recharger la liste à chaque lancement (ce qui serait pénalisant en terme de performances) ;
- en incluant les données sous forme statique dans le programme, tout système d’exploitation un tantinet évolué permettra un partage de ces données entre plusieurs instances du programme, ce qui économisera de la mémoire en cas d’exécutions concurrentes du programme.
Par contre, il faudra bien évidement recompiler le programme à chaque modification du dictionnaire.
Algorithme utilisé
L’algorithme utilisé est très simple : il s’agit d’une exploration systématique des combinaisons de lettres possibles. Dans la fonction « main », on fait successivement démarrer cette exploration à chacune des 16 cases de la grille de départ.
Ensuite la fonction Recurse ajoute successivement une des lettres voisines (si elle est libre) dans la chaîne « choices » et teste l’existence de ce mot via la fonction TestWord. Cette fonction :
- cherche le mot dans le dictionnaire (recherche dichotomique) ;
- affiche le mot et son score si le mot existe ;
- renvoie un code de retour égal à 1 si la racine du mot existe dans le dictionnaire (ce qui accélère énormément la recherche en évitant l’exploration de « branches mortes »).
La fonction « Recurse » s’appelle ensuite elle même pour les lettres adjacentes à la lettre courante. La récursion s’arrête lorsque la profondeur maximale est atteinte (16 pour une grille de 4 sur 4).
Cet algorithme est utilisé par l’excellente application iPhone « MotàMot » développée par la société LMA Consulting....
Messages
1. Boggle : algorithme de résolution, 2 mars 2020, 16:19, par Kat
Bonjour
je découvre ce forum depuis la Vendée.
Je ne suis pas féru de programmation C mais plutôt de programmation en langage 4D.
Je cherche à adapter cet algorithme. J’ai besoin de comprendre la logique sur la façon dont est abordée la gestion des lettres voisines (ou comment être certain que les lettres utilisées se touchent).
Merci de votre aide.
Belle journée
1. Boggle : algorithme de résolution, 3 mars 2020, 09:46, par Paul Courbis
Bonjour
L’algorithme est expliqué en fin d’article.
Cordialement