15 puzzles

Le « 15 Puzzle » (également appelé « Fifteen Puzzle », « Gem Puzzle » ou « Sliding Puzzle ») se compose d’un cadre 4x4 contenant 15 tuiles carrées numérotées et un emplacement vide. Les tuiles sont mélangées, et le joueur doit les faire glisser une à une vers l'espace vide afin de les disposer dans l'ordre numérique, généralement de 1 à 15, de gauche à droite et de haut en bas, l'espace vide se trouvant dans le coin inférieur droit. Seules les tuiles adjacentes à l'espace vide peuvent être déplacées.

Règles

1. Le plateau est une grille 4x4 composée de tuiles numérotées de 1 à 15 et d’une case vide.
2. Vous pouvez faire glisser n’importe quelle tuile adjacente à la case vide (vers le haut, le bas, la gauche ou la droite) pour la placer dans cette case.
3. Une seule tuile peut être déplacée à la fois.
4. Le but est de disposer toutes les tuiles dans l’ordre suivant : 1 à 4 dans la rangée du haut, 5 à 8 dans la deuxième, 9 à 12 dans la troisième et 13 à 15 dans la quatrième, la case vide se trouvant à la position 16 (en bas à droite).

Stratégies

• Résoudre ligne par ligne : commencez par résoudre la ligne du haut (1 à 4), puis la deuxième ligne (5 à 8), et enfin les tuiles restantes.
• Technique des coins pour les rangées du haut : pour placer une tuile dans le coin en haut à droite sans déranger les tuiles déjà placées, utilisez une séquence spécifique : positionnez la tuile cible dans la deuxième rangée, puis faites glisser la tuile du coin vers le bas et la tuile cible vers le haut simultanément.
• Les deux dernières rangées ensemble : lorsque vous résolvez la troisième rangée, vous devez travailler simultanément sur la troisième et la quatrième rangées, car il est impossible de placer les tuiles du bas isolément.
• Approche 3-2-1 : lorsque vous approchez de la fin, travaillez sur les trois dernières tuiles ensemble, en les faisant pivoter pour les mettre en place.
• Compter les inversions : toutes les configurations ne sont pas résolubles. Le puzzle est résoluble si et seulement si le nombre d’inversions (paires de tuiles dont l’ordre relatif est inversé) plus le numéro de la rangée de l’espace vide (en comptant à partir du bas) est pair.
• Réduire le nombre de mouvements : Les joueurs confirmés cherchent à effectuer le moins de mouvements possible. La solution optimale est NP-difficile à calculer, mais des heuristiques telles que la distance de Manhattan (somme des distances de chaque tuile par rapport à sa destination) fournissent de bonnes estimations.

Le « 15 Puzzle » possède l’une des histoires les plus hautes en couleur parmi tous les casse-têtes. Il a fait une entrée fracassante aux États-Unis vers 1880, déclenchant un engouement national comparable à la fièvre du Rubik’s Cube des années 1980. Pendant des mois, partout — dans les bureaux, les usines et les foyers —, les gens se sont passionnés pour ce jeu consistant à mettre les tuiles dans le bon ordre.

Les origines de ce casse-tête font l'objet d'un débat. Pendant des décennies, le célèbre concepteur de casse-têtes Sam Loyd a affirmé en être l'inventeur, mais les recherches modernes attribuent cette invention à Noyes Chapman, un maître de poste de Canastota, dans l'État de New York, qui a créé une version du casse-tête vers 1874. Bien que sans fondement, la revendication de Loyd concernant l’invention de ce casse-tête a joué un rôle déterminant dans sa promotion. Loyd avait notamment offert une récompense de 1 000 dollars à quiconque parviendrait à résoudre une configuration spécifique dans laquelle les tuiles 14 et 15 étaient interverties — une configuration mathématiquement impossible à résoudre, ce que Loyd savait presque certainement.

L’analyse mathématique du « 15 Puzzle » a constitué l’une des toutes premières applications de la théorie des groupes aux casse-têtes. En 1879, les mathématiciens William Edward Story et William Woolsey Johnson ont prouvé indépendamment l’un de l’autre qu’exactement la moitié de toutes les configurations possibles du casse-tête sont résolubles à partir d’une position de départ donnée. Cette démonstration a marqué un tournant dans les mathématiques combinatoires.

Ce casse-tête perdure depuis plus de 140 ans et a donné lieu à d’innombrables variantes : différentes tailles (3x3, 5x5), des images à la place des chiffres, des versions circulaires et triangulaires, ainsi que des versions numériques. Le puzzle 8 (version 3x3) est devenu un problème classique en intelligence artificielle, utilisé pour enseigner et évaluer des algorithmes de recherche tels que A* et IDA*. Le puzzle 15 reste un sujet incontournable dans les cours d’informatique, les mathématiques ludiques et les compétitions de résolution rapide.