À propos du taquin | Histoire, parité et le 14-15 de Sam Loyd

L’engouement de 1880

Le casse-tête vient de l’État de New York, dans les années 1870 ; Noyes Chapman, maître de poste à Canastota, est généralement désigné comme son inventeur. Au début de 1880, il a suscité un engouement, d’abord dans tous les États-Unis, puis en Europe.

Le 14-15 de Sam Loyd

Le créateur américain de casse-têtes Sam Loyd a prétendu plus tard qu’il avait inventé le jeu, et a parlé d’un prix de 1 000 dollars pour quiconque le résoudrait avec seulement le 14 et le 15 échangés. Personne n’a gagné le prix, et personne ne le pouvait : cette position n’a pas de solution. Sa prétention à l’invention n’était pas fondée non plus.

Pourquoi la moitié des positions sont impossibles

Considérez la case vide comme une seizième pièce. Chaque glissement échange la case vide avec une pièce. Pour revenir dans son coin, la case vide doit se déplacer autant de fois vers la gauche que vers la droite, et autant de fois vers le haut que vers le bas : une position avec la case vide dans son coin est donc toujours à un nombre pair d’échanges de l’ordre résolu. Échanger le 14 et le 15 représente un seul échange, ce qui est impair, et aucun glissement ne peut donc y mener. En 1879, William Johnson et William Story ont prouvé qu’exactement la moitié de toutes les dispositions peuvent être atteintes.

Un test pour n’importe quelle position

Comptez les paires de pièces qui sont dans le mauvais ordre quand vous lisez le cadre ligne par ligne. Sur un plateau 3×3 ou 5×5, une position peut être résolue quand ce nombre est pair. Sur un plateau 4×4, ajoutez la ligne de la case vide comptée depuis le bas : la position peut être résolue quand la somme est impaire.

La résolution par ordinateur

Un ordinateur peut chercher un chemin de retour avec A*, qui examine toujours en premier la position la plus prometteuse. Il estime les coups encore nécessaires à partir de la distance entre chaque pièce et sa case cible, plus deux coups pour chaque paire de pièces qui se bloquent dans leur propre ligne ou colonne. Trouver la solution la plus courte devient très difficile sur les grands plateaux. Les positions les plus difficiles du taquin 15 demandent 80 coups, et le taquin 8 n’en demande jamais plus de 31.

Essayez dans PictorX

Ouvrez le taquin et cliquez sur une pièce pour la faire glisser. Mélanger répartit les pièces dans une nouvelle position qui peut être résolue, Résoudre joue une solution coup par coup, et « Afficher les pièces bien placées » colore les numéros des pièces déjà à leur place. Choisissez « 14-15 de Loyd » pour voir la position impossible, et utilisez Taille pour choisir entre 3×3, 4×4 et 5×5.

Questions fréquemment posées

Qui a inventé le taquin ?

Noyes Chapman, maître de poste à Canastota, dans l’État de New York, est généralement désigné comme l’inventeur, dans les années 1870. Sam Loyd a plus tard revendiqué l’invention, à tort.

Le casse-tête 14-15 a-t-il une solution ?

Non. Il est à un échange de l’ordre résolu, et toute position que les glissements peuvent atteindre en est à un nombre pair d’échanges.

Combien de positions le taquin compte-t-il ?

Les 16 cases peuvent être remplies de 20 922 789 888 000 façons. Exactement la moitié d’entre elles, 10 461 394 944 000, peuvent être atteintes en faisant glisser les pièces.

PictorX envoie-t-il quelque chose ?

Non. Le taquin est dessiné sur un canevas dans votre navigateur. Enregistrer télécharge un PNG, et Modifier ouvre cette image dans l’éditeur PictorX.