Une brève histoire du taquin

Le taquin semble avoir toujours existé, mais il a une sorte de date de naissance : l’hiver 1879–1880, quand une petite boîte en bois remplie de blocs numérotés est passée en quelques mois du statut de curiosité du nord de l’État de New York à celui de folie qui a balayé l’Amérique et l’Europe.

Qui l’a inventé ?

Longtemps, on en a attribué le mérite à Sam Loyd, le célèbre créateur d’énigmes américain, qui affirmait depuis les années 1890 l’avoir inventé. Ce n’était pas vrai. Les historiens Jerry Slocum et Dic Sonneveld ont remonté la piste jusqu’à Noyes Chapman, receveur des postes à Canastota, dans l’État de New York, qui en montrait déjà une version à ses amis au milieu des années 1870. Des copies ont gagné Syracuse, puis Boston, où des menuisiers ont commencé à les fabriquer et à les vendre fin 1879. Chapman a demandé un brevet en 1880, qui lui a été refusé.

La folie de 1880

Début 1880, le « Gem Puzzle » ou « Boss Puzzle », comme on le vendait, était partout. Les journaux publiaient des caricatures de gens penchés sur la petite boîte ; les patrons se plaignaient des heures de travail perdues ; certaines boutiques l’ont interdit. En quelques semaines, il a traversé l’Atlantique vers la Grande-Bretagne, la France et l’Allemagne. Puis, presque aussi vite qu’elle était venue, la mode est retombée avant l’été.

Le taquin 14–15 et le prix

Une partie de la fièvre venait d’un piège cruel. Les taquins étaient souvent vendus avec les pièces en ordre, sauf le 14 et le 15, inversés, et on mettait les joueurs au défi de les remettre en place. Des prix étaient promis pour une solution. Sam Loyd a raconté plus tard l’histoire d’un prix de 1 000 dollars qu’il aurait offert ; rien ne prouve qu’il l’ait fait, mais l’histoire est restée.

Personne n’a jamais touché de prix, car personne ne pouvait réussir. En 1879, deux mathématiciens américains, William Johnson et William Story, avaient publié une démonstration dans l’American Journal of Mathematics : chaque coup conserve un certain compte (pair ou impair), donc exactement la moitié des positions peut être atteinte depuis le plateau résolu, et l’autre moitié non. Le plateau 14–15 est dans la mauvaise moitié. Ce fut l’une des premières fois qu’un jeu populaire fut tranché par une démonstration mathématique.

Compter les plateaux

Il y a 16! (environ 20 900 milliards) façons de placer quinze pièces et un trou dans la boîte, donc environ 10 500 milliards de plateaux ont une solution. C’est bien trop pour les vérifier un par un au crayon, et pendant un siècle la question « combien de coups demande le plateau le plus difficile ? » est restée ouverte.

Les ordinateurs ont tout changé. En 1985, Richard Korf a présenté IDA*, une méthode de recherche toujours utilisée aujourd’hui, en prenant le taquin pour exemple (c’est elle qui fait tourner le solveur de ce site). Dans les années 1990, des chercheurs de Zurich ont montré que tout taquin 15 se résout en 80 coups au plus, et que certains plateaux en demandent bien 80. Le petit taquin 8 n’en demande jamais plus de 31. Pour le taquin 24, sur un plateau 5×5, le nombre exact est encore inconnu.

数字华容道 et autres noms

En Chine, le taquin s’appelle 数字华容道, « la route de Huarong des nombres ». Le nom vient d’un casse-tête chinois plus ancien à blocs coulissants, 华容道, où le général Cao Cao doit se frayer un chemin pour échapper à une embuscade à Huarong. Au Japon, c’est le 15パズル ; en Espagne et en Amérique latine, le juego del 15. Le taquin n’a jamais vraiment disparu : les versions en plastique bon marché sont devenues un jouet de poche classique, et les plus rapides résolvent aujourd’hui un 4×4 en quelques secondes.

Envie d’essayer ? Jouez au taquin ou apprenez comment le résoudre.