Accueil > Réalisations > Logiciels > Jeux de l’esprit > Boggle > Boggle : algorithme de résolution

Boggle : algorithme de résolution

mardi 25 janvier 2011, par Paul Courbis

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
};
#endif

Il 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

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.

Les spams donneront systématiquement lieu à dépôt de plainte. Les messages peu aimables ou comportant trop de fautes d'orthographe seront purement et simplement supprimés sans publication. Aucune obligation de publication ne pourra être opposée au webmaster, sauf éventuel droit de réponse dûment justifié.
ipv6 ready ipv6 test
Suivre ce site :
Recommander cette page :
Bookmark and Share
Traduire :