Ce document a été produit par HEVEA.
Votre browser peut avoir a être configuré pour afficher correctement
certains symboles.
Reportez-vous à la documentation d'HEVEA.
Licence d'informatique
Projet C
Mots croisés
Décembre 2002
Ce document est disponible sous forme d'un fichier PostScript compressé.
Le but de ce projet est de placer un ensemble de mots sur une grille
de taille quelconque. Les mots peuvent être placés soit
horizontalement, et ils se lisent alors de gauche à droite, soit
verticalement, et ils se lisent de haut en bas. Deux mots peuvent
s'intersecter (un mot vertical, un mot horizontal) aux positions où
ils possédent des lettres communes. Un mot peut intersecter plusieurs
mots. Tout mot placé sur la grille doit être entouré de cases vides,
hormis pour les cases où il intersecte un autre mot, et à ses
extrémités où les cases en diagonale peuvent être occupées par un
autre mot (voir Fig. 1). Tout le problème est de trouver le
meilleur placement répondant à un certain critère: taille minimale de
la grille englobante, plus grand nombre d'intersections entre mots...
...
Figure 1 : Un exemple de placement pour 4 mots. Les cases en grisé sont
celles qui ne peuvent être occupées en raison de la présence du mot
hélicoptère.
Lecture de l'ensemble de mots
L'ensemble des mots à placer est contenu dans un fichier texte, dont
le nom est passé en paramètre du programme. Le fichier contient un mot
par ligne. Les fonctions fopen et fgets permettent
d'ouvrir et de lire ligne par ligne un fichier. Les mots sont lus un
par un dans un buffer, alloués dynamiquement et insérés dans une liste
chaînée. Voici un exemple de programme utilisant ces deux fonctions et
imprimant le contenu d'un fichier ligne par ligne.
#include <stdio.h>
#define MAX_LENGTH 80
int main(int argc, char *argv[]) {
FILE *file;
char buffer[MAX_LENGTH];
/* Ouverture du fichier en lecture (¨r¨ pour read */
/* argv[1] (1er argument) est le nom du fichier */
if ((file = fopen(argv[1], "r")) == NULL) {
fprintf(stderr, "%s: Error opening %s: ", argv[0], argv[1]);
perror("");
exit(2);
}
/* Lecture d'une ligne */
while (fgets(buffer, MAX_LENGTH, file))
printf("%s", buffer);
}
Recherche d'un meilleur placement
La solution triviale pour trouver un meilleur placement est de les
parcourir dans leur totalité. Pour cela, on utilise l'algorithme
suivant:
-
Placer le premier mot de la liste à la position (0, 0)
horizontalement. La grille G initiale des mots placés est donc
réduite à ce mot. Construire une seconde liste L des mots non
encore placés;
- Pour chaque mot M de la liste L des mots non encore
placés:
-
supprimer M de L;
- Si L est vide, pour chaque placement possible de M dans
G, évaluer le placement obtenu par rapport au critère, et le
stocker si il est meilleur que celui actuellemnt obtenu. Si
aucun placement de M dans G n'est possible, on n'a pas de
solution;
- Si L n'est pas vide, on recommence de manière récursive
l'étape b pour chaque placement possible de M dans G. Si
aucun placement n'est possible, on n'a pas de solution. Avant
chaque appel récursif, on modifie G en fonction du placement
de M dans G;
- réinsérer M dans L;
Le fait qu'un placement soit possible dépend des conditions énumérées
dans la section précédente et des mots déjà placées (i.e. la grille
courante). Ici on cherchera les intersections du mot avec ceux déjà
placés, et pour chaque intersection, on vérifiera si elle est possible
par rapport aux mots déjà placés.
Quant au critère d'évaluation d'un placement, on pourra choisir la
taille minimale de la grille englobante. L'option -i du
programme permet de changer le critère en le plus grand nombre
d'intersections de mots.
Structures de données proposées
En plus de la liste des mots, l'algorithme précédent utilise une liste
de mots non placés et une grille de mots placés. Nous proposons de
représenter une grille de mots placés par un tableau de structures
représentant chacune un mot placé, et contenant:
-
la position (x, y) du mot (i.e. de sa première lettre);
- le sens de placement du mot: horizontal ou vertical;
- la longueur du mot (pour accélerer la recherche des placements
possibles);
- un pointeur sur la chaîne correspondant au mot;
Un tableau est alloué dynamiquement au début du programme, avec une
longueur égale au nombre de mots lus dans le fichier. Ce tableau
représentera la grille courante des mots placés. Une seconde grille
est aussi allouée et contiendra le meilleur placement courant.
L'ensemble de ces structures est représentée Fig. 2.
Figure 2 : Les structures de données proposées.
Ce document a été traduit de LATEX par
HEVEA.