8 Puzzles

Le « 8 Puzzle » est la version réduite du « 15 Puzzle » ; il se joue sur une grille 3x3 composée de tuiles numérotées de 1 à 8 et d’une case vide. Le but du jeu est de faire glisser les tuiles vers l'espace vide afin de les disposer dans l'ordre numérique. Malgré sa taille compacte, le puzzle à 8 tuiles offre un défi passionnant et occupe une place particulière en informatique, car il s'agit de l'un des problèmes les plus étudiés dans le domaine des algorithmes de recherche en intelligence artificielle.

Règles

1. Le plateau est une grille 3x3 composée de tuiles numérotées de 1 à 8 et d’une case vide.
2. Faites glisser n’importe quelle tuile adjacente à la case vide pour la placer dans cette case.
3. Une seule tuile peut être déplacée à la fois, horizontalement ou verticalement.
4. Disposez les tuiles dans l’ordre suivant : 1 à 3 dans la rangée du haut, 4 à 6 dans la rangée du milieu, 7 et 8 ainsi que la case vide dans la rangée du bas (case vide en bas à droite).

Stratégies

• Commencez par la rangée du haut : Placez les tuiles 1, 2 et 3 dans la rangée du haut. Une fois en place, elles ne devraient plus avoir besoin d'être déplacées.
• La colonne de gauche ensuite : Placez les tuiles 4 et 7 dans la colonne de gauche (si ce n'est pas déjà fait lors de la résolution de la rangée du haut).
• Terminez le coin : Les tuiles restantes (5, 6, 8) et l’espace vide forment une petite zone 2x2 qui peut être résolue en faisant tourner les tuiles en boucle.
• Mouvement en boucle : lorsque les dernières tuiles doivent être réorganisées, faites-les tourner autour de l’espace vide jusqu’à ce qu’elles atteignent leurs positions correctes.
• Vérification de la résolvabilité : exactement la moitié de toutes les configurations possibles sont résolubles. Comptez le nombre d’inversions (tuiles qui apparaissent avant leur prédécesseur naturel). Si ce nombre est pair, le casse-tête est résoluble ; s’il est impair, il ne l’est pas.
• Distance de Manhattan : pour chaque tuile, calculez le nombre de déplacements qui la séparent de sa position cible (horizontalement + verticalement). La somme donne une borne inférieure du nombre de déplacements nécessaires. Utilisez cette valeur pour évaluer à quel point vous êtes proche de la solution.

Le « 8 Puzzle » est un descendant direct du « 15 Puzzle », dont la grille est passée de 4×4 à 3×3. Alors que le puzzle à 15 pièces a captivé l'attention du grand public à partir de 1880, le puzzle à 8 pièces, plus petit, est devenu le sujet d'études universitaires, notamment dans le domaine de l'intelligence artificielle.

Dans les années 1960 et 1970, les chercheurs en IA ont adopté le puzzle à 8 pièces comme référence standard pour tester les algorithmes de recherche. Son espace d’états est suffisamment restreint pour être entièrement exploré (181 440 états accessibles sur 362 880 permutations possibles), tout en restant suffisamment complexe pour tester l’efficacité de différentes approches. Ce casse-tête a servi à démontrer et à comparer la recherche en largeur, la recherche en profondeur, l’approfondissement itératif et le célèbre algorithme A* développé par Peter Hart, Nils Nilsson et Bertram Raphael en 1968.

L’algorithme A*, lorsqu’il est combiné à l’heuristique de la distance de Manhattan, permet de résoudre de manière optimale n’importe quelle configuration solvable du puzzle 8, en trouvant le nombre minimal de coups. Le nombre maximal de coups nécessaires pour résoudre une configuration solvable est de 31, et la moyenne est d’environ 22 coups. Ces résultats ont été établis grâce à des recherches informatiques exhaustives.

Le « 8 Puzzle » reste un incontournable des cours d’introduction à l’IA et aux algorithmes dans les universités du monde entier. Les étudiants mettent en œuvre des algorithmes de recherche à l’aide de ce casse-tête pour comprendre des concepts tels que les heuristiques, les chemins optimaux et l’exploration de l’espace d’états. Il sert de point d’entrée pour appréhender des problèmes plus complexes dans les domaines de la planification, de la robotique et de l’optimisation. Au-delà du milieu universitaire, le « 8 Puzzle » est un casse-tête populaire que l’on trouve dans les magasins de jouets, les applications mobiles et sous forme de mini-jeu au sein de jeux vidéo plus importants.