Discussion :

[MaitreEauEau]

Salut!

Je suis nouveau ici, alors soyez gentil

Donc, voilà. Je veux faire un solveur de Boggle en C pour me pratiquer.

Boggle est un jeu de lettres conçu par Alan Turoff et déposé par Parker Brothers / Hasbro, Inc.

Le jeu commence par le mélange d'un plateau (carré) de 16 dés à 6 faces, généralement en le secouant. Chaque dé possède une lettre différente sur chacune de ses faces. Les dés sont rangés sur le plateau 4 par 4, et seule leur face supérieure est visible. Après cette opération, un compte à rebours de 3 minutes est lancé et tous les joueurs commencent à jouer.
Chaque joueur cherche des mots pouvant être formés à partir de lettres adjacentes du plateau. Par «*adjacentes*», il est sous-entendu horizontalement, verticalement, ou en diagonale. Les mots doivent être de 3 lettres au minimum, peuvent être au singulier ou au pluriel, conjugués ou non, mais ne doivent pas utiliser plusieurs fois le même dé pour le même mot. Les joueurs écrivent tous les mots qu'ils ont trouvés sur leur feuille personnelle. Après les 3 minutes de recherche, les joueurs doivent arrêter d'écrire et le jeu entre dans la phase de calcul des points.

Par exemple, si on a une grille comme suit:

A E R T
U E S E
M S R O
A F I D

On devra former des mots de 3 lettres et plus, adjacentes (horizontale, verticale et diagonale). Ici, on aurait:

EAU, AERE, AERES, MUE, MUES, MUER, MUEE, MUEES, SES, etc.

Je veux faire un petit programme qui trouvera tout les mots d'une grille. J'ai cru comprendre en faisant des recherches qu'il me fallait utiliser l'algorithme DFS (depth-first search). J'ai trouvé le code source d'un solveur de grille de Boggle en C, mais je n'arrive pas à comprendre les fonctions dfs et output.

Bref, est-ce que vous seriez capable de m'expliquer le fonctionnement du programme?

LIEN VERS LE PROGRAMME: http://www.circlemud.org/pub/jelson/...ggle1/boggle.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
 
 
#define BOX_SIZE	4
 
#define MIN_WORD_LEN	3
#define MAX_WORD_LEN	8
 
#define NOT_SEEN	0
#define SEEN		1
 
#define DICT_SIZE       300000
#define FOUND_SIZE      1000
 
char *dict[DICT_SIZE];
char *found[FOUND_SIZE];
 
int num_words, num_found = 0;
 
char letters[BOX_SIZE][BOX_SIZE];
int graph[BOX_SIZE][BOX_SIZE];
char choices[MAX_WORD_LEN+1];
 
void try_print(char *word)
{
  int i;
 
  if (num_found >= FOUND_SIZE) {
    printf("too many words found\n");
    return;
  }
 
  for (i = 0; i < num_found; i++)
    if (!strcmp(word, found[i]))
      return;
 
  found[num_found++] = strdup(word);
  printf("bog %s\n", word);
}
 
 
void output(int depth)
{
  static int bot, top, cen, res;
 
  choices[depth] = '\0';
  bot = 0;
  top = num_words-1;
 
  for(;;) {
    cen = (bot+top)/2;
    res = strcmp(choices, dict[cen]);
    if (!res) {
      try_print(choices);
      return;
    } else if (bot >= top) {
      return;
    } else if (res > 0) {
      bot = ++cen;
    } else
      top = --cen;
  }
}
 
 
void dfs(int x, int y, int depth)
{
  int i, j;
 
  if (x < 0 || y < 0 || x >= BOX_SIZE || y >= BOX_SIZE)
    return;
  if (graph[x][y] == SEEN) {
    return;
  }
 
  graph[x][y] = SEEN;
 
  choices[depth++] = letters[x][y];
 
  if (depth >= MIN_WORD_LEN)
    output(depth);
 
  if (depth < MAX_WORD_LEN) {
    for (j = -1; j <= 1; j++)
      for(i = -1; i <= 1; i++)
	if (i || j)
	  dfs(x+i, y+j, depth);
  }
 
  graph[x][y] = NOT_SEEN;
}
 
 
 
int my_sort(const void *a, const void *b)
{
  return (strcmp(*(char **)a, *(char **)b));
}
 
 
int main(int argc, char *argv[])
{
  int i, j;
  char buf[128];
  FILE *f;
 
  num_words = 0;
 
  if (!(f = fopen("./bigdict", "r"))) {
    perror("error opening dictionary");
    exit(0);
  }
 
  while (fgets(buf, 128, f)) {
    buf[strlen(buf)-1] = '\0';
    for (i = 0; i < strlen(buf); i++)
      buf[i] = tolower(buf[i]);
    dict[num_words++] = strdup(buf);
#if 0
    dict[num_words++] = strdup(strcat(buf, "s")); /* naively pluralize */
#endif
 
    if (num_words >= DICT_SIZE) {
      printf("dictionary too large\n");
      exit(1);
    }
  }
 
  qsort(dict, num_words, sizeof(char *), my_sort);
 
#if 0
  for (i = 0; i < num_words; i++)
    puts(dict[i]);
#endif
 
  for (j = 0; j < BOX_SIZE; j++) {
    for (i = 0; i < BOX_SIZE; i++) {
      do {
	scanf("%s", buf);
      } while (!isalpha(*buf));
      letters[i][j] = tolower(*buf);
      graph[i][j] = NOT_SEEN;
    }
  }
 
  for (j = 0; j < BOX_SIZE; j++)
    for (i = 0; i < BOX_SIZE; i++)
      dfs(i, j, 0);
 
  return 0;
}

[MaitreEauEau]

UPP

[MaitreEauEau]

UPP? none knwos

[Invité(e)]

none knwos

??? no one knows peut être ?

Sinon, l'algorithme est assez simple : on parcourt le plateau de jeu comme on le ferait à la main, il n'y a pas de mystère.

J'ai mis quelques commentaires pour mieux comprendre le code.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
 
void dfs(int x, int y, int depth)
{
  int i, j;
 
  /* vérifiction de la cohérence ddes paramètres*/
  if (x < 0 || y < 0 || x >= BOX_SIZE || y >= BOX_SIZE)
    return;
 
  /* si la case a déjà été prise en compte, on la passe */
  if (graph[x][y] == SEEN) {
    return;
  }
 
  /* on ajoute la case au mot courant */
  graph[x][y] = SEEN;
  choices[depth++] = letters[x][y];
 
  /* si regarde si le mot courant appartient au dictionnaire */
  if (depth >= MIN_WORD_LEN)
    output(depth);
 
 /* tant qu'on n'a pas atteint la taille max des mots, on ajoute une lettre au mot
     à partir des case adjacententes*/
  if (depth < MAX_WORD_LEN) {
    for (j = -1; j <= 1; j++)
      for(i = -1; i <= 1; i++)
	if (i || j)
	  dfs(x+i, y+j, depth);
  }
 
  graph[x][y] = NOT_SEEN;
}
 
 
 
/* fonction utilisée pour trier le dictionnaire */
int my_sort(const void *a, const void *b)
{
  return (strcmp(*(char **)a, *(char **)b));
}
 
 
int main(int argc, char *argv[])
{
  int i, j;
  char buf[128];
  FILE *f;
 
  num_words = 0;
 
  /* ouverture du fichier dictionnaire */
  if (!(f = fopen("./bigdict", "r"))) {
    perror("error opening dictionary");
    exit(0);
  }
 
  /*lecture du dictionnaire */
  while (fgets(buf, 128, f)) {
    buf[strlen(buf)-1] = '\0';
    for (i = 0; i < strlen(buf); i++)
      buf[i] = tolower(buf[i]);
    dict[num_words++] = strdup(buf);
#if 0
    dict[num_words++] = strdup(strcat(buf, "s")); /* naively pluralize */
#endif
 
    if (num_words >= DICT_SIZE) {
      printf("dictionary too large\n");
      exit(1);
    }
  }
 
  /* tri des entrées du dictionnaire */
  qsort(dict, num_words, sizeof(char *), my_sort);
 
#if 0
  /* affichage du dictionnaire*/
  for (i = 0; i < num_words; i++)
    puts(dict[i]);
#endif
 
  /* Remplissage de la grille par l'utilisateur */
  for (j = 0; j < BOX_SIZE; j++) {
    for (i = 0; i < BOX_SIZE; i++) {
      do {
	scanf("%s", buf);
      } while (!isalpha(*buf));
      letters[i][j] = tolower(*buf);
      graph[i][j] = NOT_SEEN;
    }
  }
 
  /* appel de la fonction dfs sur chaque case du jeu */
  for (j = 0; j < BOX_SIZE; j++)
    for (i = 0; i < BOX_SIZE; i++)
      dfs(i, j, 0);
 
  return 0;
}

La fonction output est une fonction de recherche dichotomique.

Si tu veux aller plus loin, tu peux ajouter des traces dans le code, en particulier au début de la fonction dfs. Une trace comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

printf("dfs : mot à tester : %s\n", choices);