Eine kurze Geschichte des 15-Puzzles

Das 15-Puzzle wirkt zeitlos, hat aber so etwas wie einen Geburtstag: den Winter 1879/1880, als eine kleine Holzschachtel mit nummerierten Klötzchen in wenigen Monaten von einer Kuriosität im Norden des Staates New York zu einem Fieber wurde, das Amerika und Europa erfasste.

Wer hat es erfunden?

Lange galt Sam Loyd als Erfinder, der berühmte amerikanische Rätselmacher, der ab den 1890er-Jahren behauptete, es erfunden zu haben. Das stimmte nicht. Die Historiker Jerry Slocum und Dic Sonneveld verfolgten das Puzzle zurück bis zu Noyes Chapman, einem Postmeister in Canastota im Staat New York, der Mitte der 1870er-Jahre Freunden eine Version davon zeigte. Kopien kamen nach Syracuse, dann nach Boston, wo Tischler sie Ende 1879 herzustellen und zu verkaufen begannen. Chapman beantragte 1880 ein Patent, es wurde aber abgelehnt.

Das Fieber von 1880

Anfang 1880 war das „Gem Puzzle“ oder „Boss Puzzle“, wie es verkauft wurde, überall. Zeitungen druckten Karikaturen von Leuten, die über dem Kästchen hingen; Arbeitgeber klagten über verlorene Arbeitsstunden; manche Läden verboten es. Innerhalb weniger Wochen überquerte es den Atlantik nach Großbritannien, Frankreich und Deutschland. Und fast so schnell, wie die Mode gekommen war, verschwand sie bis zum Sommer wieder.

Das 14–15-Puzzle und der Preis

Ein Teil des Fiebers kam von einem gemeinen Kniff. Die Puzzles wurden oft geordnet verkauft, nur 14 und 15 waren vertauscht, und man forderte die Spieler heraus, das zu richten. Für eine Lösung wurden Preise ausgesetzt. Sam Loyd erzählte später von einem eigenen Preis über 1.000 Dollar; es gibt keinen Beleg, dass er ihn je ausgesetzt hat, aber die Geschichte blieb hängen.

Niemand hat je einen Preis abgeholt, denn niemand konnte es schaffen. 1879 hatten die amerikanischen Mathematiker William Johnson und William Story im American Journal of Mathematics einen Beweis veröffentlicht: Jeder Zug lässt eine bestimmte Zählung (gerade oder ungerade) unverändert, also ist genau die Hälfte aller Anordnungen vom gelösten Brett aus erreichbar und die andere Hälfte nicht. Das 14–15-Brett liegt in der falschen Hälfte. Es war eines der ersten Male, dass ein beliebtes Spiel durch einen mathematischen Beweis entschieden wurde.

Die Bretter zählen

Es gibt 16! (etwa 20,9 Billionen) Arten, fünfzehn Steine und eine Lücke in den Kasten zu legen, also sind etwa 10,5 Billionen Bretter lösbar. Das sind viel zu viele, um sie mit Papier und Bleistift einzeln zu prüfen, und ein Jahrhundert lang blieb die Frage offen: Wie viele Züge braucht das schwerste Brett?

Computer änderten das. 1985 stellte Richard Korf am 15-Puzzle IDA* vor, ein Suchverfahren, das bis heute verwendet wird (der Löser auf dieser Seite nutzt es). In den 1990er-Jahren zeigten Forscher in Zürich, dass sich jedes 15-Puzzle in höchstens 80 Zügen lösen lässt und dass manche Bretter tatsächlich alle 80 brauchen. Das kleinere 8-Puzzle braucht nie mehr als 31. Beim 24-Puzzle auf einem 5×5-Brett ist die genaue Zahl noch unbekannt.

数字华容道 und andere Namen

In China heißt das 15-Puzzle 数字华容道, „Zahlen-Huarong-Weg“. Der Name stammt von einem älteren chinesischen Schiebeblock-Rätsel, 华容道, bei dem der Feldherr Cao Cao sich aus einem Hinterhalt bei Huarong herausschieben muss. In Japan ist es das 15パズル, in Frankreich der taquin. Ganz verschwunden ist das Puzzle nie: Billige Plastikversionen wurden zum klassischen Taschenspielzeug, und Speedsolver lösen ein 4×4-Brett heute in wenigen Sekunden.

Lust bekommen? Spiel das 15-Puzzle oder lerne, wie man es löst.