Solveur de Taquin 3x3

Un taquin 3x3, aussi appelé 8-puzzle, est un jeu composé d'une grille de 9 cases (3 lignes et 3 colonnes) contenant 8 tuiles numérotées de 1 à 8 et une case vide.

L'objectif est de réorganiser les tuiles dans l'ordre croissant (généralement de 1 à 8, la case vide en dernière position) en faisant glisser successivement une tuile voisine vers la case vide, dans n'importe quelle direction (haut, bas, gauche ou droite).

Une configuration 3x3 est soluble si le nombre total d'inversions dans la séquence des tuiles (en ignorant la case vide) est pair.

Une inversion est une paire de tuiles $ (i, j) $ telle que $ i > j $ et que $ i $ apparaît avant $ j $ dans la lecture ligne par ligne (de gauche à droite, puis de haut en bas), en ignorant la case vide.

Si $ I $ est pair, la configuration a une solution

Si $ I $ est impair, la configuration est insoluble et n'a pas de solution

Plusieurs variantes existent :

— Taquin $ N \times N $ : grilles plus grandes (taquin 4x4, taquin 5x5, etc.). La complexité de recherche augmente rapidement.

— Taquin avec contraintes : certaines cases peuvent être bloquées ou certains mouvements interdits.

— Taquin toroïdal : les bords gauche/droite et haut/bas sont connectés.

— Taquin en dimension supérieure : extensions en 3D où les déplacements se font dans un espace volumique.

Chaque variante modifie la structure combinatoire du problème et les propriétés de solvabilité.

L'espace théorique total des arrangements des 9 cases est $ 9! = 362880 $. Cependant, seule la moitié de ces configurations est atteignable à cause de la contrainte de parité des permutations. Le nombre exact de configurations solubles est donc : $ \frac{9!}{2} = 181440 $ Cela signifie qu'il existe 181440 positions distinctes de départ.

Pour le taquin 3x3 (8-puzzle), le nombre maximal de coups optimaux nécessaires pour résoudre une position soluble est 31 déplacements. Cette borne a été déterminée par exploration exhaustive assistée par ordinateur.