Das 15-Puzzle (1880) — Der unlösbare Zug, mit dem Sam Loyd die Welt täuschte

Einleitung

Im Winter 1880 war ganz Amerika von einer kleinen Schachtel besessen, die in eine Handfläche passte. In einem quadratischen Rahmen lagen Plättchen mit den Zahlen 1 bis 15, und durch Schieben über das einzige leere Feld musste man die durcheinander geratenen Zahlen wieder in die richtige Reihenfolge bringen. Dieses schlichte Spielzeug hielt die Finger in Schenken, Büros und Eisenbahnwaggons an, und Zeitungen klagten, das Fieber lähme die ehrliche Arbeit. Das war die erste weltweite Begeisterung für das Schiebespiel, das später als das 15-Puzzle bekannt werden sollte.

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.

Doch was ich hier ausgraben möchte, ist weniger die Manie selbst als die Identität des Mannes, den die Welt lange als den Erfinder des Spiels in Erinnerung behielt. Sein Name war Samuel Loyd (1841-1911). Als Amerikas bekanntester Puzzle-Autor und ehemaliger Schachproblemist behauptete er, genau er habe die Manie ausgelöst, und setzte sogar eine Belohnung von tausend Dollar aus für jeden, der das Rätsel löse. In dieser Behauptung war jedoch eine entscheidende Lüge verborgen.

In diesem Artikel verfolge ich den wahren Ursprung der Manie von 1880 und fördere die Tatsache zutage, dass die Stellung, auf die Loyd seinen Preis setzte, bereits 1879 — bevor er das Wort ergriff — als „mathematisch unerreichbar" bewiesen worden war. Und ich möchte von der Seite der Geschichte aus die Frage neu lesen, die diese alte Holzschachtel sogar an die digitalen Puzzles von heute weitergegeben hat: Wie garantiert man, dass ein Puzzle überhaupt lösbar ist?

Der zeitgeschichtliche Kontext

Der Schiebemechanismus selbst wurde vermutlich um 1874 von Noyes Palmer Chapman, einem Postmeister in Canastota (New York), erdacht. In den folgenden Jahren verbreitete er sich durch Mundpropaganda, und nachdem er als Massenware produziert wurde, entfachte er im Januar 1880 in den USA eine explosive Begeisterung. Die Welle schwappte im April desselben Jahres nach Europa über und verebbte dann um Juli abrupt wieder. Die Manie war ein kurzes, aber heftiges Fieber von etwa einem halben Jahr.

Sam Loyd begann das Puzzle „meine Erfindung" zu nennen, erst lange nachdem die Manie vorbei war. Sein erster veröffentlichter Artikel über das 15-Puzzle erschien 1896, sechzehn Jahre nach dem Höhepunkt der Manie. Es gibt keinerlei Hinweis auf seine Beteiligung am damaligen Hype. Dennoch behauptete Loyd über die langen Jahre bis zu seinem Tod immer wieder seine Urheberschaft.

Diese Hochstapelei wurde erst in jüngerer Zeit vollständig entwirrt. Die Puzzle-Historiker Jerry Slocum und Dic Sonneveld stellen in ihrem Buch The 15 Puzzle von 2006 die zeitgenössischen Primärquellen gegenüber und wiesen akribisch nach, dass Loyds Behauptung eine hundertfünfzehn Jahre andauernde Erfindung gewesen war. Die Ehre der Erfindung gebührt stattdessen einem unbekannten Postmeister.

Die Mechanik

Die Regeln könnten nicht einfacher sein. In einem 4×4-Rahmen liegen fünfzehn Plättchen und ein leeres Feld; nur ein Plättchen, das an das leere Feld angrenzt, darf hineingeschoben werden. Das Ziel ist, die Zahlen der Reihe nach von 1 bis 15 zu ordnen und das leere Feld in seine vorgesehene Ecke zu bringen. Es gibt keine Zuglimitierung, und jeder kann es aufgreifen. Genau diese Schlichtheit war der Reiz, der die Menschen von 1880 in seinen Bann zog.

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.

Doch das Spiel barg eine unsichtbare Mauer. Die amerikanischen Mathematiker William Woolsey Johnson und William E. Story veröffentlichten 1879 im American Journal of Mathematics „Anmerkungen zum '15'-Puzzle" und bewiesen durch ein Paritätsargument (die Parität einer Permutation), dass die Hälfte aller Ausgangsstellungen niemals geordnet werden kann, egal wie viele Züge man macht. Mit anderen Worten: Ob eine Stellung lösbar ist, steht von Anfang an mathematisch fest — nicht durch Glück oder Ausdauer.

Die Stellung, auf die Loyd seinen tausend Dollar setzte, gehörte genau zu dieser „unlösbaren Hälfte". Was er als Aufgabe stellte, war eine fast vollständige Anordnung, in der nur die 14 und die 15 vertauscht waren. Es sieht einen Schritt von der Lösung entfernt aus, doch weil die Parität umgekehrt ist, kann die Lösung nie erreicht werden. Das Preisgeld war sicher. Er verkaufte eine mathematische Unmöglichkeit als „lösbares schwieriges Problem" und ließ die Massen um eine ewige Vergeblichkeit wetteifern. Das war keine Erfindung, sondern die Inszenierung der Unlösbarkeit.

Die Linie bis in die Gegenwart

Die Perspektive, die Johnson und Story eröffneten — den Zustandsraum eines Spielfeldes durch Mathematik zu lesen — zieht sich direkt in die spätere Informatik. Im Jahr 1990 zeigten Daniel Ratner und Manfred Warmuth, dass die Verallgemeinerung des 15-Puzzles auf ein n×n-Brett das Finden einer kürzesten Lösung NP-schwer macht (erstmals vorgestellt auf der AAAI 1986). Je größer das Brett, desto rechnerisch unlösbarer wird die Suche nach der optimalen Lösung. Die Paritätsfrage von 1879 war kontinuierlich mit der modernen Komplexitätstheorie.

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.'

Und dieses Erbe lastet heute still, aber schwer auf jedem, der Schiebeplättchen in digitaler Form benutzt. Wer ein Puzzle implementiert, das Plättchen zufällig mischt, muss das Johnson-Story-Theorem berücksichtigen; denn verteilt man naiv die Plättchen, reicht man dem Spieler jedes zweite Mal eine Stellung, die absolut unlösbar ist. Deshalb prüfen moderne Schiebepuzzle-Generatoren die Parität intern und verteilen nur lösbare Felder. Der Beweis von 1879 lebt als Voraussetzung der Implementierung fort.

Was Loyd hinterließ, war nicht die Ehre der Erfindung, sondern eine unbequemere Lektion. Die Schwierigkeit eines Puzzles kann manchmal über „schwierig" hinausgehen und „unmöglich" erreichen; und wer diese Unmöglichkeit nicht erkennen kann, dem ist eine unlösbare Stellung von einer bloß schwierigen nicht zu unterscheiden. Die Ethik des modernen Puzzle-Designs — dass der Aufgabensteller die Verantwortung trägt zu garantieren, dass eine Lösung existiert — wird ironischerweise am hellsten von seiner Tausend-Dollar-Lüge beleuchtet.

Quellen

In diesem Artikel verwendete Quellen:

・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, Nr. 4 (1879), S. 397–404

・D. Ratner & M. Warmuth, „The (n²−1)-puzzle and related relocation problems", Journal of Symbolic Computation, vol. 10 (1990), S. 111–138 (erstmals vorgestellt auf der AAAI 1986)

・Wolfram MathWorld: 15 Puzzle

Zum Abschluss

Das 15-Puzzle hat historisch, glaube ich, zwei Dinge gezeigt. Erstens: Ein absolut einfacher Satz von Schieberegeln legte ein Objekt der modernen Mathematik — den Zustandsraum — in die Handflächen der breiten Öffentlichkeit. Die Menschen von 1880 rieben ihre Finger an einer Wand aus reiner Logik ab, ohne zu wissen, dass sie die Grenze zwischen geraden und ungeraden Permutationen nachzeichneten. Das war ein seltener Moment, in dem ein Puzzle die Mathematik demokratisierte.

Zweitens gibt es die Frage der Ehrlichkeit des Aufgabenstellers. Sam Loyd war kein Erfinder, aber das „unlösbare Feld", das er in seine Belohnung pflanzte, drängte ironischerweise den Kern der Puzzle-Gestaltung der Nachwelt auf. Eine Aufgabe, deren Lösbarkeit nicht garantiert werden kann, ist kein schwieriges Problem, sondern eine Täuschung. Der Beweis von 1879 und die Manie von 1880 stellen auch heute, nach hundertundvierzig Jahren, jedem, der Plättchen mischt, dieselbe Frage: Ist dieses Feld wirklich lösbar?