En 1880, l’auteur de casse-têtes Sam Loyd annonce un prix de 1000 $ à qui résout un 15-puzzle précis : disposition standard 1‑à‑15 avec 14 et 15 intervertis. La folie du puzzle gagne déjà l’Amérique ; le coup de Loyd y met du carburant. Des milliers essaient. Personne ne gagne.
Il y a une raison. Le plateau de Loyd était démontrablement insoluble, et la démonstration tient sur une page. Cet article est cette page.
L’énoncé
Exactement la moitié des 16!/2 ≈ 10 461 394 944 000 façons de disposer quinze tuiles et un vide sur un 4×4 peut être résolue. L’autre moitié, non. Le « 14 et 15 intervertis » de Loyd appartient à la moitié insoluble.
Cela se généralise. Sur tout taquin N×N, la moitié des dispositions est insoluble. Le 3×3 8-puzzle a 9!/2 = 181 440 plateaux résolubles sur 362 880 ; les 24, 35, etc. suivent la même règle.
Inversions
La démonstration a besoin d’une définition. Lisez les tuiles dans l’ordre de lecture — gauche à droite par rangée 1, puis 2, 3, 4 — en ignorant le vide. Vous obtenez une suite de quinze nombres.
Une inversion est une paire (a, b) où a apparaît avant b mais a > b. Comptez chaque paire de la sorte. Ce compte est le nombre d’inversions du plateau.
Exemple : l’état but 1, 2, 3, …, 15 a zéro inversion. « 14 et 15 intervertis » donne la suite 1, 2, 3, …, 13, 15, 14, avec exactement une (paire 15, 14).
Lemme clé : un coup change la parité de façon contrôlée
Que se passe-t-il pour le nombre d’inversions à un coup légal ?
-
Coups horizontaux : la tuile change sa position dans la suite de lecture d’un cran. Son rang relatif avec chaque autre tuile reste identique. Le compte est inchangé.
-
Coups verticaux : la tuile saute trois autres tuiles dans la suite — les trois tuiles de la rangée traversée. Chacune passe de « après » à « avant » ou inverse, contribuant ±1. Somme de trois ±1 = impair. Le compte change d’un nombre impair.
Résumé : horizontal préserve la parité du compte ; vertical la retourne.
La rangée du vide se retourne aussi sur les verticaux
Suivez la rangée du vide comptée depuis le haut. Horizontal : même rangée. Vertical : rangée change d’une — sa parité change.
Deux choses changent ensemble :
- Parité d’inversions ⇔ coup vertical.
- Parité de rangée du vide ⇔ coup vertical.
Leur somme est invariante. On a trouvé une quantité conservée.
Le théorème de parité
Définissez l’invariant :
P = (nombre d’inversions) + (numéro de rangée du vide, comptée depuis le bas, à partir de 1)
C’est la quantité conservée. Chaque coup légal change P d’une quantité paire, donc sa parité (paire ou impaire) ne change jamais.
L’état but a zéro inversion et le vide en rangée 1 depuis le bas — donc P = 1 (impair). Tout plateau de P pair est inatteignable depuis le but, et inversement.
D’où un test de solvabilité propre :
- Lire les tuiles en ordre de rangée, sans le vide.
- Compter les inversions.
- Compter la rangée du vide depuis le bas (1, 2, 3 ou 4).
- Sommer. Impair = soluble. Pair = non.
« 14 et 15 intervertis » de Loyd : 1 inversion, vide en rangée 1 depuis le bas — somme 2, pair, insoluble.
Pour les autres tailles
Dépend de N pair ou impair :
- N impair (3×3, 5×5, …) : résoluble ssi inversions paires. Rangée du vide non pertinente (parité déterminée par celle des inversions par symétrie).
- N pair (4×4, 6×6, …) : résoluble ssi (inversions) + (rangée depuis le bas) impair.
Pour 3×3 le test est simplement « nombre pair d’inversions ? ». Plus simple, mémorisable en une minute.
Conséquence sympa
La moitié des dispositions étant solubles, un mélange aléatoire + vérification de parité est plus rapide qu’un mélange aléatoire + tentative de résolution. Les apps qui garantissent des départs solubles :
- Filtrent à l’avance par parité et remélangent à l’échec.
- Génèrent par marche arrière depuis le but, en appliquant des coups valides aléatoires. Solvabilité garantie par construction, et c’est ce que font la plupart des apps, la nôtre comprise.
Si vous tombez sur un puzzle impossible à résoudre, l’app l’a mal généré — pas votre faute, pas un puzzle venu de l’univers.
Note Sam Loyd
Le prix de 1000 $ de Loyd est l’une des farces pratiques les mieux documentées de l’histoire du puzzle. Le mathématicien qui a prouvé l’insolvabilité — indépendamment — fut soit William Johnson et William Story (1879, American Journal of Mathematics), soit Loyd lui-même, selon les sources. Loyd, figure auto-promotrice, revendiquait plusieurs inventions qui n’étaient pas les siennes ; le 15-puzzle a été inventé par Noyes Chapman en 1874, six ans avant le prix de Loyd.
Ce que Loyd a apporté : le prix, la publicité et la variante insoluble — utile, mais pas ce qu’il annonçait.