Solveur de Taquin 5x5

Le taquin 5x5, ou 24-puzzle, est un jeu de réflexion constitué d'une grille carrée de 25 emplacements (5 lignes et 5 colonnes).

Cette grille contient 24 tuiles numérotées de 1 à 24 et un espace vide. L'objectif consiste à réorganiser les tuiles pour atteindre une configuration cible (généralement l'ordre numérique croissant de 1 à 24, laissant la case vide en dernière position).

Le mouvement s'effectue uniquement en faisant glisser une tuile adjacente vers l'espace vide (haut, bas, gauche ou droite), ce qui déplace l'espace vide à la position précédente de la tuile.

La solvabilité d'un taquin 5x5 repose sur la parité des permutations. Puisque la largeur de la grille est impaire, une configuration est soluble si et seulement si le nombre total d'inversions est pair.

Une inversion est définie par toute paire de tuiles $ (i, j) $ telle que $ i > j $ alors que $ i $ précède $ j $ lors d'une lecture linéaire de la grille (ligne par ligne, de gauche à droite).

Si le nombre d'inversions $ I $ est impair, la position appartient l'ensemble des configurations physiquement inaccessibles depuis l'état ordonné.

Plusieurs variantes modifient la structure combinatoire ou les règles de déplacement :

— Taquins $ N \times N $ : formats plus simples comme le 3x3 (8-puzzle) ou le 4x4 (15-puzzle) et plus complexes au-delà.

— Taquins avec contraintes : présence de cases fixes (murs) ou de tuiles de formes irrégulières.

— Taquin toroïdal : les bords sont connectés, permettant à une tuile sortant par la droite de réapparaître à gauche.

— Taquin graphique : utilisation d'une image découpée au lieu de chiffres, ce qui peut introduire des ambiguïtés de solvabilité si des tuiles sont visuellement identiques.

— Taquin 3D : utilisation de déplacement en 3 dimensions, souvent utilisée dans les casse-têtes en bois.

L'espace d'état d'un taquin 5x5 est immense. Pour 25 emplacements, il existe $ 25! $ arrangements théoriques. Comme seule la moitié de ces positions est accessible par glissement, le nombre de configurations solubles est défini par la formule $ \frac{25!}{2} $

Cela représente environ $ 7.7 \times 10^{24} $ configurations, soit plus que le nombre de configurations du Rubik's Cube classique ($ 4.3 \times 10^{19} $)

Le nombre maximal de coups nécessaires pour résoudre n'importe quelle configuration soluble (souvent appelé Nombre de Dieu) n'est pas encore connu précisément pour le format 5x5 mais des estimations suggèrent que le diamètre du graphe dépasse les 200 déplacements.