Page principale

Cette page permet de tester différents algorithmes de parcours afin de résoudre un taquin. Ces algorithmes, leurs enjeux d'optimalité, de complexité temporelle et d'utilisation de la mémoire, sont largement détaillés sur cette page.

Un taquin est un jeu, où, étant donné une position comme celle ci-dessous, on doit atteindre une position cible en faisant glisser les pièces.
Pour un taquin $n\times n$, le nombre d'états possibles est $(n^2)!$ - dont seulement la moitié permettent d'atteindre la position cible (cela se montre à coup d'étude de groupes de permutations). Pour $n=3$, on obtient $181\;440$ états accessibles - et il est encore possible de les loger en mémoire (un état est une suite de 9 chiffres entre $0$ et $8$, et peut donc être codé sur $9\times 4=36$ bits, ce qui donne environ 800Ko pour stocker l'ensemble des états). Pour $n=4$, le nombre d'états accessibles est environ $10^{13}$ et il faudrait environ $50 To$ pour stocker ces états, ce qui commence à être moins raisonnable.

Pour un taquin à 15 pièces (donc $4\times 4$), où la case vide est initialement l'une des cases centrales, le tableau suivant donne le nombre de positions accessibles au plus court en exactement $n$ coups :
 $n$  0  1 23456789101112131415161718
1 4 10 20 38 80 174 372 762 1540 3072 6196 12356 24516 48179 94356 183432 355330 682250 … 

Vous trouverez en dessous de l'application des précisions sur son implémentation.

Nouvelle position :


(Vous pouvez également permuter des cases de la position en cliquant dessus.)
Résoudre :





Positions possibles : 181 440
Cible :



Algorithme :
    Itérations :
    Temps :
    Mémoire utilisée :
    Longueur du chemin trouvé :





Répartition empirique du nombre de coups minimal pour résoudre un taquin $4\times 4$ (sur ~300 tirés au hasard). La moyenne empirique obtenue est proche de 52. Les trois quarts des positions tirées ont une distance à la position cible comprise entre 47 et 57.



Nombre d'itérations de l'algorithme A* (avec l'heuristique «motifs») en fonction de la distance à la position cible (sur ~100 exemples tirés au hasard).

Références