Dans ce TP, on propose l'architecture suivante sur plusieurs fichiers :

• main.c contient le lancement des résolutions ;
• plateau.(h|c) contiennent le type des plateaux et les fonctions liées au graphe implicite des mouvements ;
• tablehachage.(h|c) des tables de hachage en adressage ouvert (sondage linéaire) avec pour clés des plateaux et des valeurs associées quelconques ;
• liste.(h|c) une implémentation des listes chaînées avec ajout sur le dernier maillon en \(O(1)\) ;
• file.(h|c) une implémentation des files avec des listes chaînées ;
• fileprio.(h|c) une implémentation des files de priorité avec des tas ;
• bruteforce.(h|c) du retour sur trace pour résoudre le puzzle ;
• aetoile.(h|c) l'algorithme A* et le parcours en largeur pour la résolution.

Tous les .h sont fournis, et on vous demande d'écrire les .c. Ce document décrit ce qui est attendu des différentes fonctions.

On pourra ainsi récupérer l'archive TP_15puzzle.zip qui contient les .h. Les .c solutions sont dans le répertoire solutions de l'archive et vous pouvez les récupérer pour sauter certaines parties.

Présentation du puzzle et fonctions sur le plateau

On va écrire ici plateau.c.

Le 15-puzzle (ou taquin) est un puzzle constitué de 15 tuiles numérotées de 1 à 15 et d'une case vide agencées dans un carré \(4 \times 4\).

Le puzzle résolu correspond au plateau suivant, la case vide étant en gris :

Plateau résolu ; la case vide est en gris.

Un mouvement valide consiste à déplacer une tuile voisine de la case vide dans celle-ci, ce qui place la case vide à sa place.

Les deux mouvements valides sur le plateau précédent mènent à :

Le 15 a glissé vers la droite.

Le 12 a glissé vers le bas.

Un plateau se représente naturellement par un tableau de 16 entiers, la valeur 0 étant donnée pour la case vide, en lisant le plateau ligne par ligne. Le plateau résolu est donc le tableau { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 }.

On va faire beaucoup de manipulations de plateaux, et il est plus simple d'avoir des plateaux immuables passés par copie. Pour cela, on pourrait les définir uniquement comme des tableaux statiques :

#define N 4 // pour pouvoir changer la taille
typedef int plateau[N*N];

Problème : tout passage d'un plateau en paramètre se fera alors par référence, en tant que pointeur, et sans aucune copie du tableau lui-même.

Il existe une astuce classique en C : les structures peuvent être passées par valeur et recopiées. On va donc définir :

#define N 4
struct plateau {
    int t[N*N];
};
typedef struct plateau plateau;

Cela permettra d'avoir directement des plateau comme argument ou valeur de retour sans poser aucun problème.

Question 1. Écrire une fonction

void plateau_affiche(plateau p);

qui affiche un plateau sur la sortie standard.

Question 2. Écrire une fonction

plateau plateau_resolu(void);

qui renvoie le plateau résolu.

Question 3. Écrire une fonction

bool plateau_eq(plateau p1, plateau p2);

qui teste si deux plateaux sont égaux.

Question 4. Écrire une fonction

int position_vide(plateau p);

qui renvoie l'indice de la case vide.

Question 5. Écrire une fonction

bool mouvement_valide(plateau p, int src, int dst);

qui indique si échanger les cases d'indices src et dst est un mouvement valide, où src est l'indice de la case vide.

Question 6. Écrire une fonction

plateau mouvement_effectue(plateau p, int src, int dst);

qui effectue l'échange de deux cases. On suppose que le mouvement est valide.

Question 7. Écrire une fonction

void mouvements(plateau p, int *mouv, int *n);

qui prend en entrée un pointeur sur un tableau de 4 entiers et place dedans les indices des cases qu'on peut échanger avec la case vide, en indiquant, par passage par référence, le nombre de mouvements valides dans l'entier n passé par pointeur.

Question 8. Écrire une fonction

plateau mouvement_aleatoire(plateau p);

qui effectue un mouvement valide aléatoire et renvoie le nouveau plateau.

Question 9. Écrire une fonction

plateau plateau_melange(int n);

qui effectue n mouvements aléatoires depuis le plateau résolu et renvoie le plateau correspondant.

Remarque

En partant du plateau résolu, on est sûr d'obtenir un plateau qu'on peut résoudre en au plus n mouvements. Ce n'est pas le cas de n'importe quelle permutation des tuiles : on peut montrer que la moitié seulement des configurations sont accessibles depuis le plateau résolu.

Files de priorité

On va écrire ici fileprio.c.

On implémente ici des files de min-priorité avec un tas redimensionnable, où on double la capacité en cas de dépassement.

Pour cela, on considère les types :

struct element {
    T valeur;
    int priorite;
};

typedef struct element element;

struct fileprio {
    element *elements;
    unsigned int taille;
    unsigned int capacite;
};

typedef struct fileprio fileprio;

Le type T ne peut être polymorphe comme en OCaml, on a donc défini en tête de fileprio.h :

typedef plateau T;

Question 10. Écrire une fonction

fileprio *fileprio_cree(unsigned int capacite);

qui crée une file de priorité de capacité initiale capacite.

Question 11. Écrire une fonction

void fileprio_libere(fileprio *f);

qui libère la file de priorité f.

Question 12. Écrire une fonction

void fileprio_insere(fileprio *t, T valeur, int prio);

qui insère la valeur valeur avec la priorité prio.

Question 13. Écrire une fonction

element fileprio_extrait_minimum(fileprio *t);

qui extrait et renvoie le couple (valeur, priorité) de priorité minimale.

Note : ici, on aurait pu renvoyer un T et placer la priorité dans un pointeur optionnel.

Tables de hachage sur les plateaux

On va écrire ici tablehachage.c.

On va utiliser des plateaux comme clés, mais pour les valeurs associées, on propose du polymorphisme light à l'aide de void * :

struct baquet {
    bool remplit;
    plateau valeur;
    void *assoc;
};
typedef struct baquet baquet;

struct table {
    baquet *elements;
    unsigned int taille;
    unsigned int capacite;
};
typedef struct table table;

Et on fournit la fonction de hachage suivante sur les plateaux :

uint64_t plateau_hache(table *t, plateau p)
{
    uint64_t n = 0;
    uint64_t m = 1;
    for(int i = 0; i < N*N; i++)
    {
        n += p.t[i] * m;
        m *= N*N;
    }
    return n % t->capacite;
}

Remarque

Avant le modulo, n est l'entier dont l'écriture en base \(N^2 = 16\) est donnée par les cases du plateau. Comme un plateau comporte 16 chiffres hexadécimaux, soit \(64\) bits, deux plateaux différents donnent deux valeurs de n différentes : les collisions ne viennent que du modulo.

Attention : on supposera que les valeurs void *assoc ne sont pas possédées par la table. C'est donc à l'utilisateur de s'assurer de les libérer. C'est la raison pour laquelle la fonction de remplacement ci-dessous va renvoyer l'ancienne valeur.

Question 14. Écrire une fonction

table *table_cree(int capacite);

qui crée une table de hachage de capacité initiale capacite.

Question 15. Écrire une fonction

void table_libere(table *t, bool libere_assoc);

qui libère la table t, ainsi que les valeurs associées si libere_assoc est vrai.

Question 16. Écrire une fonction

bool table_contient(table *t, plateau p);

qui indique si le plateau p est une clé de la table t.

Question 17. Écrire une fonction

void table_ajoute(table *t, plateau p, void *assoc);

qui ajoute une association.

Si la taille de la table dépasse la moitié de la capacité, on doublera la capacité en créant une nouvelle table et en réinsérant toutes les paires.

Question 18. Écrire une fonction

void *table_remplace(table *t, plateau p, void *assoc);

qui remplace l'association si p est dans la table et renvoie l'ancienne valeur. Si p n'est pas dans la table, cette fonction appellera juste table_ajoute et renverra NULL.

Question 19. Écrire une fonction

void *table_cherche(table *t, plateau p);

qui renvoie la valeur void * associée au plateau p.

Algorithme A*

On va écrire ici aetoile.c.

Question 20. Écrire une fonction

void resout_aetoile(plateau p);

qui résout le puzzle avec l'algorithme A*.

On affichera la solution sous la forme de la succession des plateaux et on indiquera la longueur de la solution.

On pourra procéder ainsi :

• définir une fonction d'heuristique qui compte le nombre de cases non vides mal placées ;
• on va utiliser une file de priorité ;
• pour stocker les distances minimales et les parents, on pourra utiliser une table de hachage avec des valeurs associées qui seront des donnee * où donnee est :

struct donnee {
    int distance;
    plateau parent;
};

typedef struct donnee donnee;

Remarque

Un mouvement déplace une seule tuile : il change donc le nombre de tuiles mal placées d'au plus 1. Cette heuristique ne surestime jamais le nombre de mouvements restants (chaque tuile mal placée doit bouger au moins une fois) et vérifie \(h(p) \le 1 + h(p')\) pour tout mouvement de \(p\) vers \(p'\) : A* renvoie donc bien une solution de longueur minimale. La somme des distances de Manhattan de chaque tuile à sa place est une heuristique plus précise qui a les mêmes propriétés.

Stratégies par force brute

On va écrire ici bruteforce.c.

Question 21. Écrire une fonction

void resout_retoursurtrace(plateau p, int recursion_limit);

qui trouve une solution par retour sur trace sans jamais descendre dans l'arbre à une profondeur plus grande que recursion_limit.

On affichera la solution.

Question 22. Écrire une fonction

int resout_retoursurtrace_meilleur(plateau p, int recursion_limit);

qui renvoie la longueur minimale d'une solution par retour sur trace sans jamais descendre dans l'arbre à une profondeur plus grande que recursion_limit.

Si on ne peut trouver une solution dans cette limite, on renverra -1.

Note : ici, pas la peine d'afficher la solution, ce qui demanderait beaucoup plus de travail.

Optimisations

Question 23. Écrire une fonction

int resout_retoursurtrace_meilleur_borne(plateau p, int recursion_limit);

qui optimise la fonction précédente en ne descendant jamais plus profondément que la profondeur minimale d'une solution déjà trouvée.

Question 24. À rajouter dans aetoile.c pour avoir les fonctions communes.

Écrire une fonction

void resout_largeur(plateau p);

qui résout le puzzle par un parcours en largeur.

Note : on pourra implémenter liste.c et file.c, et utiliser le type des tables de hachage en plaçant directement des entiers castés en void * pour les distances.

Remarque

Pour comparer les deux approches : sur un plateau obtenu par 40 mouvements aléatoires dont la solution optimale est de longueur 16, le parcours en largeur de la correction a évalué environ 440 000 positions contre 166 pour A*.