/* Exercice de colles d'informatique */

/* Titre : Bilan mémoire en C : le taquin */

#define N 4
/* Un jeu de taquin est la donnée d'une matrice (N x N) dont les cases (à
 * l'exception d'une) contiennent un jeton annoté par une coordonnée valide
 * de la matrice (pas nécessairement la coordonnée de la case dans laquelle
 * se trouve le jeton). Chaque coordonnée (à l'exception de celle du coin
 * en bas à droite) apparaît une et seule fois dans la matrice.
 *
 * +------+------+------+------+
 * |(0, 2)|      |(1, 1)|(1, 2)|
 * +------+------+------+------+
 * |(1, 0)|(2, 0)|(2, 2)|(0, 1)|
 * +------+------+------+------+
 * |(0, 0)|(3, 0)|(1, 3)|(2, 3)|
 * +------+------+------+------+
 * |(3, 1)|(3, 3)|(3, 2)|(2, 1)|
 * +------+------+------+------+
 *     Une grille de taquin
 *
 * Dans le jeu de taquin ci-dessous la case de coordonnées (0, 1) est la
 * case ne contenant pas de jeton annoté, on l'appellera le "trou". Le jeu
 * se joue seul, par coup. Un coup est le déplacement d'un jeton se
 * trouvant dans une case adjacente au trou dans le trou.
 * Aussi la grille ci-dessus donne lieu à trois coups possibles :
 * - (2, 0) est déplacé vers le haut :
 * +------+------+------+------+
 * |(0, 2)|(2, 0)|(1, 1)|(1, 2)|
 * +------+------+------+------+
 * |(1, 0)|      |(2, 2)|(0, 1)|
 * +------+------+------+------+
 * |(0, 0)|(3, 0)|(1, 3)|(2, 3)|
 * +------+------+------+------+
 * |(3, 1)|(3, 3)|(3, 2)|(2, 1)|
 * +------+------+------+------+
 *
 * - (0, 2) est déplacé vers la droite :
 * +------+------+------+------+
 * |      |(0, 2)|(1, 1)|(1, 2)|
 * +------+------+------+------+
 * |(1, 0)|(2, 0)|(2, 2)|(0, 1)|
 * +------+------+------+------+
 * |(0, 0)|(3, 0)|(1, 3)|(2, 3)|
 * +------+------+------+------+
 * |(3, 1)|(3, 3)|(3, 2)|(2, 1)|
 * +------+------+------+------+
 *
 * - (1, 1) est déplacé vers la gauche :
 * +------+------+------+------+
 * |(0, 2)|(1, 1)|      |(1, 2)|
 * +------+------+------+------+
 * |(1, 0)|(2, 0)|(2, 2)|(0, 1)|
 * +------+------+------+------+
 * |(0, 0)|(3, 0)|(1, 3)|(2, 3)|
 * +------+------+------+------+
 * |(3, 1)|(3, 3)|(3, 2)|(2, 1)|
 * +------+------+------+------+
 *
 * Le but du jeu est de trouver une suite de coup conduisant à une
 * situation où chaque case (à l'exception de celle en bas à droite)
 * contient le jeton contenant ses coordonnées.
 */

/* Q1. Proposer et implémenter un type structuré permettant la
 * représentation d'une coordonnée. */

/* Q2. Proposer et implémenter un type structuré permettant la
 * représentation d'une case d'un jeu de taquin */

/* Q3. Proposer et implémenter permettant la représentation d'un jeu de
 * taquin. */

/* Q4. Définir une fonction est_taquin_valide vérifiant qu'un jeu de taquin
 * est valide : chaque coordonnée (à l'exception de ...) apparaît une et
 * une seule fois, et il y a exactement un trou. */

/* Q5. Définir une fonction joue_coup prenant en paramètre un coup (haut,
 * bas, gauche ou droite, représenté par un entier 0, 1, 2, 3) et un jeu de
 * taquin et le modifiant selon le coup joué. */

/* Q6. Proposer et implémenter un type permettant la représentation d'un
 * enchaînement de coups dont la longueur n'est pas connue à l'avance. */

/* Q7. Définir une fonction joue_coups prenant en paramètre un tel
 * enchaînement de coup et un jeu de taquin et les appliquant au jeu de
 * taquin. */