Puzzles coulissants : du taquin à Rush Hour

L’idée centrale est un cadre contenant des pièces et juste trop peu de place : on déplace seulement une pièce dans l’espace vide. Elle était déjà sur papier avant la version célèbre. Un brevet américain accordé à Ernest Kinsey en 1878 décrit des blocs glissant dans un cadre avec un seul vide.

Le jeu qui a rendu l’idée célèbre est le taquin : quinze tuiles numérotées dans un plateau quatre par quatre, avec un vide. Les longues recherches de Jerry Slocum et Dic Sonneveld, présentées dans leur livre The 15 Puzzle de 2006, remontent à Noyes Chapman, maître de poste à Canastota, dans l’État de New York. Des versions étaient vendues sous le nom Gem Puzzle fin 1879.

Sources1Source 1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2Source 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

Dans les premiers mois de 1880, le taquin devint une folie. Il traversa les États-Unis en quelques semaines puis l’Europe, dans les bureaux, salons et journaux. Les récits divergent sur les semaines exactes, mais au printemps il était partout, puis déclinait en été. Chapman demanda un brevet qui fut refusé ; la raison est incertaine ; une explication plausible est que des brevets antérieurs couvraient déjà l’idée.

Certaines positions semblaient impossibles, et l’étaient réellement. En 1879, William Woolsey Johnson et William Story publièrent des notes dans l’American Journal of Mathematics montrant qu’exactement la moitié des dispositions ne peuvent être résolues. L’argument repose sur la parité : chaque glissement garde fixe un décompte pair ou impair caché ; une position au mauvais décompte reste inaccessible, quelle que soit la durée des essais.

Cela explique le tour le plus célèbre : échangez seulement le 14 et le 15 d’un plateau terminé. La position semble à un coup du but, mais est inaccessible.

Sources3Source 3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

Pendant une grande partie du XXe siècle, le taquin fut attribué à Sam Loyd, l’auteur de puzzles le plus connu aux États-Unis. Il disait l’avoir inventé et offert un grand prix pour l’échange impossible 14–15. Slocum et Sonneveld ont trouvé que sa première revendication datait de 1891, plus de dix ans après l’engouement, et dura jusqu’à sa mort en 1911. Rien ne prouve son rôle dans l’invention ni l’existence du prix en 1880.

La revendication a persisté grâce à sa célébrité, aux réimpressions de ses livres et aux reprises ultérieures. Cela rappelle que l’histoire des puzzles, comme toute histoire, mérite vérification dans les archives.

Sources2Source 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

La grande famille suivante changea le but. Au lieu d’ordonner les tuiles, il fallait amener un grand bloc vers une sortie parmi de plus petits. Un brevet déposé par Lewis W. Hardy en 1907 et accordé en 1912 décrit dix blocs de tailles différentes dans une boîte, déplaçables seulement par glissement. Un modèle très proche fut vendu comme Pennant Puzzle.

Des jeux semblables suivirent sous divers noms. Le Smithsonian conserve un Dad’s Puzzler, protégé en 1926, avec un grand carré, plusieurs rectangles et deux petits carrés. Cette famille est souvent appelée Klotski ; en Chine, Huarong Dao raconte un général échappant à une embuscade. Les solutions minimales des dispositions classiques atteignent environ 80 coups, selon le mode de comptage.

Dans les années 1990 apparut sa forme moderne la plus réussie. Le Japonais Nob Yoshigahara créa Tokyo Parking, un puzzle de voitures coulissantes ; Binary Arts, devenu ThinkFun, le publia aux États-Unis en 1996 sous le nom Rush Hour. Voitures et camions encombrent une petite grille ; on les glisse jusqu’à pouvoir sortir sa voiture. Des cartes de difficulté graduée en firent une série, devenue habituelle en classe et en famille.

Sources4Source 4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5Source 5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6Source 6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

Ils ressemblent à des jouets, mais sont des objets sérieux en informatique. Il fallut attendre 1999 pour établir que toute position résoluble du taquin se termine en au plus 80 mouvements d’une tuile. Korf et Schultze l’ont confirmé par une recherche de 28 jours trouvant exactement dix-sept positions exigeant les 80.

En 2002, Gary Flake et Eric Baum ont prouvé que Rush Hour généralisé à toute taille de plateau est PSPACE-complet, classe réputée plus difficile que les célèbres problèmes NP-complets. Robert Hearn et Erik Demaine ont ensuite montré en 2005 que les puzzles coulissants généraux le sont aussi, même avec uniquement de petits dominos identiques. Aucun raccourci connu ne résout rapidement tous les plateaux : voilà pourquoi un bon puzzle reste intéressant.

Sources7Source 7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8Source 8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9Source 9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

OutBrick appartient à la branche de sortie des blocs, avec sa propre variation : chaque brique a une destination. Elle ne sort que par la porte de sa couleur, et aujourd’hui elle peut aussi s’échanger avec une voisine pour que trois briques d’une couleur s’alignent et disparaissent. Vider le plateau exige de trouver l’ordre, comme pour Hardy et Yoshigahara.

Les outils modernes auraient fait envie aux joueurs de 1880. Chacun des 2 000 plateaux d’OutBrick a été résolu par un solveur avant publication : personne ne rencontre un échange 14–15. Pour la pratique, notre guide comment résoudre les puzzles coulissants explique les stratégies, et vous pouvez essayer un plateau dans le navigateur.

• Fin des années 1870 : des blocs coulissants encadrés apparaissent dans les brevets américains.
• Fin 1879 : le taquin est vendu ; Johnson et Story prouvent la moitié des positions impossibles.
• 1880 : l’engouement traverse les États-Unis et l’Europe.
• 1891 : Sam Loyd revendique pour la première fois l’invention.
• 1907–1912 : le puzzle de sortie de Hardy est breveté.
• 1996 : Rush Hour sort aux États-Unis.
• 2002–2005 : Rush Hour et les puzzles coulissants sont prouvés PSPACE-complets.