8.2 Taquinons les files
Dans cette section, nous souhaitons construire un programme permettant
par une recherche exhaustive de résoudre le problème du taquin.
Pour ce faire, nous allons utiliser la notion de file.
8.2.1 Implantation d'une file gardée
Une cellule est composée d'une structure state de type
position_t (qui sera décrit dans la
section 8.2.2) et d'un pointeur nommé next sur
une autre cellule.
Une file gardée est constituée de 2 pointeurs ; le premier de
ces pointeurs a pour identificateur tail et pointe sur une
cellule qualifiée de queue de file. Le second a pour
identificateur head et pointe sur une cellule qualifiée de
tête de file. Une file est vide lorsque les pointeurs
tail et head pointent sur NULL.
Fonctions de manipulation de la file.
La file peut être manipulée grâce aux fonctions suivantes dont
on donne le prototype :
-
void initfile(struct file_t *) initialise une file
déjà définie comme étant vide ;
struct cellule_t * creercellule(struct position_t *)
construit une cellule en allouant la mémoire nécessaire, en
affectant next à NULL et en copiant les
informations fournies par le paramètre dans le champs
state ;
int estvide(struct file_t *) retourne 1 si la file est
vide, 0 sinon ;
void ajouter(struct file_t *, struct cellule_t *)
insère une cellule A dans la file. Si la file est vide les
pointeurs tail et head pointent sur la cellule A.
Sinon, le pointeur next de la cellule A pointe vers la
cellule pointée par tail et ce dernier pointeur est
modifié afin de pointer sur la cellule A ;
struct position_t * examiner(struct file_t *) retourne un
pointeur sur la position stockée en tête de la file ;
void supprimer(struct file_t *) supprime la cellule de
tête de la file. Si la file n'a qu'une cellule, on la supprime et
on fait pointer la tête et la queue sur NULL. Sinon, on
parcours la file pour placer la tête sur l'avant dernière
cellule et on supprime la dernière cellule.
Questions.
-
Donnez la déclaration des types cellule_t et
file_t décrits ci-dessus.
- Donnez les définitions des fonctions décrites ci-dessus.
8.2.2 Jeu de taquin
Un jeu de taquin est constitué d'une grille de 9 cases contenant
des jetons i.e. les entiers de 0 à 8 :
L'entier 0 correspond à une case vide qui peut être
déplacée en l'échangeant avec une case voisine. Ainsi,
en déplaçant la case vide vers la droite dans la position
ci-dessus, on obtient la position :
Le déplacement en diagonale n'est pas autorisé. L'objectif du jeu
est de parvenir à la position suivante (que l'on qualifie de
gagnante) :
Codage du jeu.
Pour continuer, il nous faut préciser ce que l'on entend par
position. Une position est une structure de type
position_t qui contient les champs suivants :
-
un tableau bidimensionnel grille représentant la
grille dont chaque case peut contenir un entier et donc un jeton.
Par convention on pose que la case correspondant à
grille[i][j] est à l'intersection de la (i+1)ième
ligne et de la (j+1)ième colonne ;
- un pointeur solution pointant sur une chaîne de
caractères. Notons qu'en cours d'exécution, cette chaîne
est uniquement constituée des caractères 'h', 'b', 'g' et 'd'.
Ces caractères représentent chacun un déplacement ('h' pour
haut, etc.) ;
- un tableau casevide de deux cellules contenant les
coordonnées de la case vide. Ainsi si casevide est {0,1} la
case vide se trouve à l'intersection de la première ligne et de
la seconde colonne.
Fonctions de manipulation.
Pour manipuler une position, on a besoin des fonctions suivantes :
-
int gagne(struct position_t *) retourne 1 si la
position est gagnante et 0 sinon ;
char * concat(char *, char) prend en entrée un début
de solution (disons "db"), un déplacement ('h') et
retourne un pointeur sur la nouvelle solution ainsi formée
("dbh") pour laquelle de la mémoire aura été
réservée (l'ancienne solution n'est pas modifiée) ;
char * deplacementpossible(int *) qui étant donnée
la case vide (dans la première position décrite dans cette
section par exemple) retourne une chaîne de caractères
regroupant l'ensemble des déplacements possibles ("hdb").
Pour faire simple, cette fonction peut recenser par des
conditionnelles l'ensemble des cas possibles ;
struct position_t nouvelleposition(struct position_t, char) retourne une nouvelle position déterminée par l'ancienne
position et le déplacement passé en paramètre (tous les
champs de la nouvelle position doivent être réactualisés et
l'ancienne position n'est pas affectée).
Pour résoudre le problème du taquin on propose d'utiliser
l'algorithme suivant :
-
Construisez une cellule à partir de la position initiale et
ajouter la dans une file vide.
- Examiner la position de tête de la file. Si elle est gagnante,
aller à l'étape 4. Sinon, aller à l'étape 3.
- Déterminer l'ensemble des déplacements possibles. Pour
chacun d'entre eux, créer une nouvelle position associée à ce
déplacement et une nouvelle cellule contenant cette dernière ;
ajouter cette cellule à la fille.
- C'est fini. Il ne reste qu'à afficher la solution trouvée.
Questions.
-
Donnez la déclaration du type position_t.
- Donnez les définitions des 3 fonctions de manipulation
décrites ci-dessus.
- Donnez la définition de la fonction
char * solve(struct position_t); qui résoud le problème
du taquin.
Pour tout commentaire : Alexandre Sedoglavic.