Le Taquin (1880) — Le coup insoluble dont Sam Loyd trompa le monde entier

Introduction

En hiver 1880, toute l'Amérique était possédée par une petite boîte tenant dans la paume de la main. Dans un cadre carré s'alignaient des tuiles numérotées de 1 à 15 ; en les faisant glisser dans la case vide, il fallait remettre les chiffres dans l'ordre. Ce seul jouet arrêtait les doigts dans les saloons, les bureaux et les wagons de chemin de fer, et les journaux se plaignaient que « la fièvre paralysait le travail ». Ce fut la première folie mondiale pour le jeu de glissement de tuiles qui serait connu sous le nom de « 15-puzzle ».

The goal state. Tiles run 1 to 15 in order, with the blank settled in the bottom-right. In 1880 the whole world was gripped by this simple act of rearrangement.

Mais ce que je souhaite exhumer ici, c'est moins la folie elle-même que l'identité de l'homme dont le monde se souvint longtemps comme de l'inventeur du jeu. Son nom était Samuel Loyd (1841-1911). Auteur de puzzles le plus réputé d'Amérique et ancien problemiste d'échecs, il affirmait être celui qui avait déclenché la manie, et offrit même une récompense de mille dollars à quiconque saurait le résoudre. Or, une imposture décisive était tapie dans cette affirmation.

Dans cet article, je retrace la véritable origine de la folie de 1880 et mets au jour le fait que la disposition même sur laquelle Loyd misait son prix avait été prouvée « mathématiquement impossible à atteindre » en 1879, avant même qu'il n'élève la voix. Et je veux relire, depuis l'histoire, la question que cette vieille boîte en bois a transmise jusqu'aux puzzles numériques d'aujourd'hui : comment garantir qu'un puzzle est soluble ?

Le contexte de l'époque

Le mécanisme coulissant lui-même aurait été imaginé vers 1874 par Noyes Palmer Chapman, directeur de la poste de Canastota (New York). Au fil des quelques années suivantes, il se répandit de bouche à oreille, et une fois fabriqué en série, il déclencha une fièvre explosive aux États-Unis en janvier 1880. La vague gagna l'Europe en avril de la même année, puis reflua brusquement vers juillet. La manie fut une fièvre courte mais violente de six mois environ.

Sam Loyd commença à appeler le puzzle « mon invention » bien longtemps après que la folie fut passée. Son premier article publié sur le 15-puzzle parut en 1896, soit seize ans après le sommet de la manie. Rien ne témoigne de son implication dans la vogue réelle. Et pourtant, jusqu'à sa mort, Loyd continua d'affirmer sa paternité.

Cette imposture ne fut totalement démêlée que bien plus tard. Les historiens du puzzle Jerry Slocum et Dic Sonneveld, dans leur livre de 2006 The 15 Puzzle, confrontèrent les sources primaires de l'époque et démontrèrent minutieusement que la revendication de Loyd avait été une invention soutenue pendant cent quinze ans. L'honneur de l'invention appartenait en réalité à un obscur directeur de poste.

Les mécaniques

Les règles sont d'une simplicité absolue. Dans un cadre 4×4 se trouvent quinze tuiles et une case vide ; seule une tuile adjacente à la case peut y être glissée. Le but est d'ordonner les chiffres de 1 à 15 et de placer la case vide dans son coin désigné. Il n'y a pas de limite de coups, et n'importe qui peut s'y essayer. Cette simplicité même était le charme qui avait saisi les gens de 1880.

The board Loyd offered as his prize. Tiles 1–13 sit in order, with only the 14 and 15 swapped (dashed). The goal is to sequence them from the top-left and send the blank to the bottom-right — yet this arrangement has reversed parity and can never be reached, however you slide.

Et pourtant, le jeu recèle un mur invisible. Les mathématiciens américains William Woolsey Johnson et William E. Story publièrent en 1879 dans l'American Journal of Mathematics des « Notes sur le puzzle à 15 » et prouvèrent, par un argument de parité (la parité d'une permutation), que la moitié de toutes les configurations initiales ne peut jamais être ordonnée, quel que soit le nombre de coups. Autrement dit, qu'une disposition soit soluble ou non est fixé mathématiquement dès le départ, non par la chance ou la persévérance.

La disposition sur laquelle Loyd misait ses mille dollars appartenait précisément à cette « moitié insoluble ». Ce qu'il posa comme défi était un arrangement presque complet dans lequel seuls le 14 et le 15 étaient échangés. Cela semble à un pas de la solution, mais comme sa parité est inversée, elle ne peut jamais atteindre la solution. La récompense était sûre. Il vendait une impossibilité mathématique comme un « problème soluble difficile », invitant la foule à rivaliser dans une futilité éternelle. Ce n'était pas une invention, mais une mise en scène de l'impossibilité.

L'héritage jusqu'à aujourd'hui

La perspective qu'ouvrirent Johnson et Story — lire l'espace d'états d'un plateau par les mathématiques — se prolonge directement dans l'informatique ultérieure. En 1990, Daniel Ratner et Manfred Warmuth montrèrent que pour la généralisation du 15-puzzle à un plateau n×n, trouver une solution de longueur minimale est NP-difficile (présenté d'abord à l'AAAI en 1986). Agrandir le plateau rend la recherche d'une solution optimale computationnellement intraitable. La question de parité de 1879 était continue avec la théorie moderne de la difficulté.

Generalize the board to n×n and finding a shortest solution becomes computationally intractable (NP-hard). The parity question of 1879 runs continuous with the modern theory of 'hardness.'

Et cet héritage repose aujourd'hui silencieusement, mais lourdement, sur quiconque manipule des tuiles coulissantes sous forme numérique. Quiconque implémente un puzzle qui mélange des tuiles au hasard doit tenir compte du théorème de Johnson-Story ; car si l'on disperse naïvement les tuiles, on remet une fois sur deux au joueur un plateau absolument insoluble. C'est pourquoi les générateurs de puzzles coulissants modernes vérifient la parité en interne et ne distribuent que des plateaux solubles. La preuve de 1879 survit comme précondition de l'implémentation.

Ce que Loyd laissa derrière lui n'est pas l'honneur de l'invention, mais une leçon plus épineuse. La difficulté d'un puzzle peut parfois dépasser le « difficile » pour atteindre « l'impossible » ; et pour qui ne peut discerner cette impossibilité, un plateau insoluble est indiscernable d'un plateau simplement difficile. L'éthique de la conception de puzzles modernes — que le proposeur est responsable de garantir l'existence d'une solution — est, ironiquement, éclairée le plus vivement par son mensonge à mille dollars.

Références

Sources consultées pour cet article :

・Wikipedia : 15 puzzle

・Cut the Knot : Sam Loyd's Fifteen, the history of the puzzle

・David Richeson : A picture of frustration — Sam Loyd's 15 puzzle

・MacTutor History of Mathematics : Samuel Loyd (1841-1911)

・Wikipedia : Sam Loyd

・Jerry Slocum & Dic Sonneveld, The 15 Puzzle: How It Drove the World Crazy (Slocum Puzzle Foundation, 2006)

・W. W. Johnson & W. E. Story, « Notes on the '15' Puzzle », American Journal of Mathematics, vol. 2, n° 4 (1879), pp. 397–404

・D. Ratner & M. Warmuth, « The (n²−1)-puzzle and related relocation problems », Journal of Symbolic Computation, vol. 10 (1990), pp. 111–138 (présenté d'abord à AAAI 1986)

・Wolfram MathWorld : 15 Puzzle

En guise de conclusion

Le 15-puzzle a démontré historiquement, je crois, deux choses. Premièrement, qu'un ensemble de règles de glissement absolument simples a placé un objet des mathématiques modernes — l'espace d'états — dans les paumes du grand public. Les gens de 1880 usaient leurs doigts contre un mur de logique pure, sans savoir qu'ils traçaient la frontière entre permutations paires et impaires. Ce fut un moment rare où un puzzle a démocratisé les mathématiques.

Deuxièmement, il y a la question de l'honnêteté du proposeur. Sam Loyd n'était pas l'inventeur, mais le « plateau insoluble » qu'il planta dans sa récompense imposa ironiquement le cœur même de la conception de puzzles à la postérité. Un défi dont on ne peut garantir l'existence d'une solution n'est pas un problème difficile, mais une tromperie. La preuve de 1879 et la folie de 1880, même après cent quarante ans, posent la même question à quiconque mélange des tuiles : ce plateau est-il vraiment soluble ?