Solveur de Taquin

Le taquin est un jeu de permutation se déroulant sur une grille de taille $ n \times n $ (généralement 4x4). Il se compose de $ n^2 - 1 $ tuiles numérotées et d'une case vide.

L'objectif est d'atteindre une configuration cible (souvent l'ordre croissant) en faisant glisser les tuiles de manière orthogonale.

Pour résoudre le taquin efficacement à la main, utiliser une stratégie de réduction progressive du problème.

— Résoudre la première ligne : placer les tuiles $ 1, 2, 3, \dots $ dans l'ordre. Les deux dernières tuiles de la ligne doivent être positionnées conjointement afin d'éviter un blocage.

— Résoudre ensuite la première colonne restante selon le même principe.

— Répéter ce procédé : après fixation d'une ligne et d'une colonne, le problème se réduit à une grille de taille $ (n-1) \times (n-1) $

Lorsque la taille atteint $ 3 \times 2 $, utiliser des cycles locaux (rotations de blocs) pour permuter les dernières tuiles jusqu'à obtention de l'état cible.

Cette méthode est constructive et simple à exécuter, mais elle ne garantit pas un nombre minimal de mouvements.

Pour obtenir une solution optimale (nombre minimal de mouvements), l'algorithme de référence est A*. Il repose sur une fonction d'évaluation $ f(n) = g(n) + h(n) $ où :

$ g(n) $ est le coût réel depuis l'état initial (nombre de mouvements effectués),

$ h(n) $ est une estimation heuristique du coût restant.

Si $ h $ est admissible (ne surestime jamais le coût réel), A* garantit l'optimalité.

Cependant, pour un taquin 4x4, l'espace d'états atteint environ $ 10^{13} $ configurations accessibles. A* nécessite de mémoriser un grand nombre d'états ouverts et fermés, ce qui devient prohibitif en mémoire.

La variante IDA* (Iterative Deepening A*) combine la borne de coût de A* avec une exploration en profondeur limitée. Elle effectue plusieurs recherches successives en augmentant progressivement le seuil de $ f(n) $. Elle consomme beaucoup moins de mémoire tout en conservant l'optimalité avec une heuristique admissible.

La performance d'A* ou d'IDA* dépend fortement de la qualité de l'heuristique $ h $.

— Distance de Manhattan : $ h = \sum_i \left( |x_i - x_i^| + |y_i - y_i^| \right) $ : elle additionne les distances horizontales et verticales de chaque tuile par rapport à sa position cible. Elle est admissible et cohérente, mais ignore les interactions entre tuiles.

— Conflit linéaire : extension de Manhattan : si deux tuiles sont dans leur ligne (ou colonne) cible mais dans l'ordre inversé, au moins deux mouvements supplémentaires seront nécessaires. Ajouter $ +2 $ par conflit détecté. Cette heuristique reste admissible.

— Pattern Databases (PDB) : elles consistent à précalculer exactement, par recherche inverse, le coût minimal pour placer un sous-ensemble de tuiles donné. Les valeurs sont stockées dans une table indexée. En combinant plusieurs bases disjointes, il est possible d'obtenir des heuristiques très informatives tout en restant admissible.

Partir de l'état final (résolu), appliquer un certain nombre de mouvements aléatoires à la case vide. La solubilité est garantie car chaque mouvement correspond à une permutation autorisée dans le groupe des états atteignables.

Vérifier si un état est résolu est trivial et s'effectue en $ O(n^2) $.

En revanche, déterminer une solution optimale pour un taquin généralisé de taille variable $ n \times n $ est NP-difficile.

Pour la grille classique 4x4, le nombre maximal de mouvements nécessaires pour atteindre la solution optimale (appelé parfois Nombre de Dieu) est de $ 80 $ (contre $ 31 $ pour le 3x3).

Le nombre total de permutations des $ n^2 $ positions est $ (n^2)! $.

Cependant, seule la moitié est atteignable depuis un état donné à cause de la contrainte de parité.

Le nombre d'états accessibles est donc : $ \frac{(n^2)!}{2} $