Solveur de Taquin 4x4

Un taquin 4×4 aussi appelé 15-puzzle est un jeu composé d'une grille de 16 cases (4 lignes × 4 colonnes) contenant 15 tuiles numérotées de 1 à 15 et une case vide.

L'objectif est de réorganiser les tuiles dans l'ordre croissant en faisant coulisser successivement une tuile voisine dans la case vide (haut, bas, gauche ou droite).

Un taquin 4×4 (grille de largeur paire) est soluble si et seulement si la condition suivante est vérifiée : $ I + r $ est impair, avec $ I $ est le nombre total d'inversions (paires de tuiles $ (i, j) $ telles que $ i > j $ avec $ i $ apparaissant avant $ j $ dans la grille lue ligne par ligne), et $ r $ est la position de la case vide en comptant les lignes depuis le bas (1 pour la dernière ligne, 2 pour l'avant-dernière, etc.).

Oui, plusieurs variantes existent :

— Taquin N×N : grilles plus grandes (par exemple 5×5 ou 6×6), dont la complexité croît de manière exponentielle avec $ N $.

— Taquin avec contraintes : certaines cases sont bloquées ou certaines tuiles ne peuvent se déplacer que selon des règles spécifiques.

— Taquin toroïdal (wrap-around) : les bords sont connectés, ce qui modifie profondément la structure du graphe d'états.

— Taquin 3D : extension en cube, comme le Rubik's Slide ici (lien affilié) où les déplacements se font dans trois dimensions.

L'espace théorique des configurations est de $ 16! $, mais seules $ \frac{16!}{2} = 10461394944000 \approx 10^{13} $ configurations sont atteignables en pratique à cause d'une contrainte de parité.

Le nombre maximal de coups optimaux nécessaires pour résoudre n'importe quelle position soluble est 80 déplacements. Cette borne a été établie par analyse exhaustive assistée par ordinateur.

Il existe 17 positions initiales nécessitant 80 coups.

Plusieurs algorithmes sont adaptés, avec des compromis entre optimalité, temps de calcul et mémoire :

— A* : algorithme de recherche heuristique optimal et complet si l'heuristique est admissible et cohérente. Il utilise $ f(n) = g(n) + h(n) $, où $ g(n) $ est le coût du chemin depuis l'état initial et $ h(n) $ une estimation du coût restant (par exemple distance de Manhattan enrichie par le Linear Conflict, qui demeure admissible lorsqu'elle est correctement calculée).

— IDA* : variante de A* qui effectue des recherches en profondeur avec un seuil de coût croissant ; elle explore moins de nœuds en mémoire au prix de ré-explorations.

— BFS (Breadth-First Search) : théoriquement optimal et complet, mais impraticable pour le 4×4 à cause de l'explosion combinatoire de l'espace d'états.

— Méthodes métaheuristiques : algorithmes génétiques ou recuit simulé permettant d'obtenir des solutions approchées plus rapidement, sans garantie d'optimalité.