Le 15-puzzle — appelé aussi « jeu des quinze », « Mystic Square » ou simplement « taquin 4×4 » — est le taquin canonique. Plateau 4×4, quinze tuiles carrées numérotées, une case vide. On glisse les tuiles dans le trou, un coup à la fois, jusqu’à ce que les nombres soient ordonnés : 1‑2‑3‑4 en haut, 5‑6‑7‑8, 9‑10‑11‑12, 13‑14‑15 et la case vide en bas à droite.
D’où il vient
Le puzzle a été inventé en 1874 par un maître de poste de Canastota, New York, Noyes Palmer Chapman. En 1880 il a atteint les écoles de Boston, à l’été c’était une folie aux États-Unis, et à l’automne il avait traversé l’Atlantique pour gagner le Royaume-Uni, la France et l’Allemagne. Les journaux publiaient des colonnes de solutions. Des ouvriers délaissaient leur poste. Dans certaines villes allemandes les autorités l’auraient interdit dans l’espace public parce que les fonctionnaires ne faisaient plus rien d’autre.
Sam Loyd — l’auteur de casse-têtes new-yorkais, jamais à court d’une histoire à son sujet — prétendit l’avoir inventé (faux), et offrit 1000 dollars en espèces à qui résoudrait une variante précise avec le 14 et le 15 intervertis. La variante s’est révélée mathématiquement insoluble (preuve dans parité du 15-puzzle). Personne n’a gagné. Loyd était content.
Comment on joue
Trois règles :
- On ne peut glisser qu’une tuile adjacente à la case vide — au-dessus, dessous, à gauche ou à droite. Pas de diagonale.
- Le glissement fait passer la tuile dans le trou. Le trou se retrouve à la place qu’occupait la tuile.
- C’est fini quand les nombres sont dans l’ordre.
C’est tout. Pas de chrono, pas de score, pas de second objectif. Tout le jeu tient dans ces trois phrases.
À quel point est-ce dur ?
Le 15-puzzle a 16!/2 ≈ 10,46 billions de dispositions atteignables (la moitié de 16!, à cause de la parité). La solution la plus courte depuis la position la plus difficile fait 80 coups. La médiane tourne autour de 52.
Un débutant résout son premier 15-puzzle en 15 à 30 minutes par essai-erreur. Quelqu’un qui a appris la méthode rangée-et-colonne au 8-puzzle résout n’importe quel 15-puzzle en 3 à 7 minutes. Un speedsolver enchaîne des coups optimaux en moins de 90 secondes.
Pourquoi le 4×4 est le point d’équilibre
Il y a une raison pour que ce soit le 15-puzzle — pas le 8 ni le 24 — qui soit devenu un phénomène mondial. Le 4×4 est :
- Assez long pour satisfaire. Le 8-puzzle se résout si vite qu’il n’y a pas d’arc. Le 15 dure assez pour offrir le petit soulagement d’une partie terminée.
- Assez court pour ne pas lasser. Le 24-puzzle prend 15 minutes et plus à un bon joueur. Le 35-puzzle, 30+. Le 4×4 tient dans une pause café.
- Assez difficile pour qu’il faille y penser. La stratégie n’est pas évidente au premier contact. La manœuvre en L à l’angle doit être découverte ou apprise — et une fois acquise, tout le puzzle s’ouvre.
Ce point d’équilibre est la raison pour laquelle le 15-puzzle est la taille qui sert de synecdoque à toute la famille. On dit « taquin » et on imagine un 4×4.
En informatique
Pendant des décennies, le 15-puzzle a été le banc d’essai standard des algorithmes de recherche heuristique. L’article de Richard Korf de 1985 qui introduit IDA* utilise 100 15-puzzles aléatoires pour démontrer l’accélération sur A*. Les travaux modernes sur les bases de motifs publient encore leurs résultats sur le 15-puzzle. Assez petit pour rester traitable, assez grand pour faire planter les mauvais algorithmes.
Si vous avez suivi un cours d’introduction à l’IA, vous avez résolu un 15-puzzle comme exercice — probablement avec A* et la distance de Manhattan. (Pour aller plus loin, voir le guide du solveur.)
Variantes dans les apps modernes
Plusieurs variantes courantes aujourd’hui :
- Tuiles numérotées — l’original, chiffres unis sur les tuiles.
- Tuiles avec image — une photo découpée en N×N remplace les nombres. On résout en remontant l’image.
- Hybride — tuiles image avec petits nombres en surimpression, pour ceux qui veulent une indication.
Certaines apps vont plus loin : grilles hexagonales, plateaux plus grands (5×5 = 24-puzzle, 6×6 = 35-puzzle), puzzles à rotation, etc. La version numérique 4×4 reste la lingua franca.
Où jouer
Sur mobile, les apps natives offrent une expérience plus fluide — pas d’upload, pas d’analytique, pas de pub entre deux glissements. Slide Puzzle livre la version numérotée classique plus 300 visuels photographiques et quatre tailles (3×3, 4×4, 5×5, 6×6).
Sur le web, des dizaines de 15-puzzles dans le navigateur. Pratiques, mais ils téléchargent les photos importées et lancent des analytiques. Si vous voulez juste quelques parties et n’importez jamais, ça fait l’affaire.
Si vous n’en avez jamais résolu, commencez trente secondes par le 8-puzzle — pour sentir le coup — puis revenez au 15. La stratégie du petit plateau se transfère directement.