Schiebepuzzle-Geschichte: Vom 15er-Puzzle bis Rush Hour

Die Kernidee eines Schiebepuzzles ist ein Rahmen mit Teilen und nicht ganz genug Platz: Ein Teil kann nur in den leeren Raum bewegt werden. Diese Idee stand schon auf Papier, bevor die berühmte Version erschien. Ein US-Patent für Ernest Kinsey von 1878 beschreibt Puzzleblöcke, die in einem Rahmen mit einer Lücke gleiten.

Berühmt machte die Idee das 15er-Puzzle: fünfzehn nummerierte Kacheln in einer Vier-mal-vier-Schale mit einem Leerraum. Jerry Slocums und Dic Sonnevelds langjährige Forschung, dargestellt in ihrem Buch The 15 Puzzle von 2006, führt es auf Noyes Chapman zurück, den Postmeister von Canastota im Bundesstaat New York. Ende 1879 wurden Varianten als Gem Puzzle verkauft.

Quellen1Quelle 1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2Quelle 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

In den ersten Monaten 1880 wurde das 15er-Puzzle zur Begeisterungswelle. Innerhalb von Wochen verbreitete es sich in den USA und weiter nach Europa, in Büros, Salons und Zeitungsspalten. Über die genauen Wochen unterscheiden sich Berichte; im Frühjahr war es überall und im Sommer flaute der Boom ab. Chapman beantragte ein Patent, das abgelehnt wurde. Der Grund ist unsicher; eine plausible Erklärung ist, dass frühere Schiebeblockpatente die Idee bereits abdeckten.

Ein Teil der Faszination war, dass manche Startstellungen unmöglich wirkten – und es waren. 1879 veröffentlichten William Woolsey Johnson und William Story im American Journal of Mathematics Notizen, die zeigten, dass genau die Hälfte aller Anordnungen niemals lösbar ist. Das Argument beruht auf Parität: Jeder Zug verändert die Anordnung so, dass ein versteckter Gerade-oder-Ungerade-Wert erhalten bleibt. Eine Stellung mit dem falschen Wert ist unerreichbar, egal wie lange man versucht.

Das erklärt den berühmtesten Trick dieser Puzzle-Geschichte. Vertausche in einer fertigen Schale nur 14 und 15: Die Stellung scheint einen Zug vom Ziel entfernt, ist aber tatsächlich unerreichbar.

Quellen3Quelle 3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

Für den größten Teil des 20. Jahrhunderts wurde das 15er-Puzzle Sam Loyd zugeschrieben, Amerikas bekanntestem Rätselautor. Loyd sagte, er habe es erfunden, und bot einen hohen Preis für die Lösung der unmöglichen Vertauschung von 14 und 15. Slocum und Sonneveld fanden, dass Loyd dies erstmals 1891 behauptete, über ein Jahrzehnt nach dem Boom, und bis zu seinem Tod 1911 dabei blieb. Es gibt keinen Beleg, dass er an der Erfindung beteiligt war oder dass sein Preis schon 1880 angeboten wurde.

Die Behauptung blieb, weil Loyd berühmt war, seine Rätselbücher oft nachgedruckt wurden und spätere Autoren sie wiederholten. Das erinnert daran, dass Puzzle-Geschichte wie jede Geschichte anhand von Aufzeichnungen geprüft werden sollte.

Quellen2Quelle 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

Die nächste große Familie änderte das Ziel. Statt Kacheln zu ordnen, musste ein großer Block durch kleinere hindurch zum Ausgang bewegt werden. Ein 1907 von Lewis W. Hardy eingereichtes und 1912 erteiltes Patent beschreibt zehn unterschiedlich große Blöcke in einer Schachtel, die nur verschoben werden dürfen. Ein eng verwandtes Design wurde als Pennant Puzzle verkauft.

Ähnliche Puzzles folgten unter vielen Namen. Die Smithsonian-Sammlung besitzt ein Dad’s Puzzler mit Copyright von 1926, mit einem großen Quadrat, mehreren Rechtecken und zwei kleinen Quadraten. In vielen Ländern heißt die Familie heute Klotski; in China erzählt Huarong Dao von einem General, der einem Hinterhalt entkommt. Minimallösungen klassischer Anordnungen liegen bei etwa 80 Zügen, je nach Zugzählung.

In den 1990ern fand die Idee ihre erfolgreichste moderne Form. Der japanische Puzzledesigner Nob Yoshigahara schuf ein Schiebeautopuzzle namens Tokyo Parking. Binary Arts, später ThinkFun, veröffentlichte es 1996 in den USA als Rush Hour. Autos und Lastwagen blockieren ein kleines Raster; man schiebt sie hin und her, bis das eigene Auto hinausfahren kann. Abgestufte Aufgabenkarten machten aus einem Einzelpuzzle eine Serie, die in Klassenzimmern und auf Familientischen heimisch wurde.

Quellen4Quelle 4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5Quelle 5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6Quelle 6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

Schiebepuzzles sehen wie Spielzeug aus, sind aber ernsthafte Gegenstände der Informatik. Erst 1999 wurde festgestellt, dass jede lösbare Stellung des 15er-Puzzles in höchstens 80 Einzelkachelzügen lösbar ist; Korf und Schultze bestätigten dies später durch eine 28 Tage dauernde Suche, die genau 17 Stellungen fand, die alle 80 benötigen.

2002 bewiesen Gary Flake und Eric Baum, dass die allgemeine Rush-Hour-Form auf beliebig großen Feldern PSPACE-vollständig ist, eine Problemklasse, die vermutlich noch schwieriger als die bekannten NP-vollständigen Probleme ist. Robert Hearn und Erik Demaine zeigten 2005 auch PSPACE-Vollständigkeit allgemeiner Schiebepuzzles, selbst wenn jeder Block derselbe kleine Dominostein ist. Einfach gesagt: Es gibt keine bekannte Abkürzung, die jedes Feld schnell löst. Genau deshalb bleibt ein gutes Schiebepuzzle interessant.

Quellen7Quelle 7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8Quelle 8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9Quelle 9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

OutBrick gehört zum Familienzweig ‚einen Block hinausbringen‘, mit einer eigenen Wendung: Jeder Stein hat ein Ziel. Ein Stein verlässt das Feld nur durch sein farblich passendes Tor, und heute kann er auch mit einem Nachbarn tauschen, damit drei einer Farbe in einer Reihe stehen und verschwinden. Ein Feld zu lösen heißt die Reihenfolge herauszufinden, wie bei Hardys Blöcken und Yoshigaharas Autos.

Moderne Werkzeuge helfen auf eine Weise, die die Spieler von 1880 beneidet hätten. Jedes der 2.000 OutBrick-Felder wurde vor Veröffentlichung von einem Solver gelöst; kein Spieler trifft deshalb auf eine Vertauschung von 14 und 15. Zur praktischen Seite dieser Geschichte erklärt unser Ratgeber wie man Schiebepuzzles löst Strategien; du kannst auch ein Feld im Browser ausprobieren.

• Späte 1870er: Schiebeblöcke in Rahmen erscheinen in US-Patenten.
• Ende 1879: Das 15er-Puzzle wird verkauft; Johnson und Story beweisen die Unlösbarkeit der Hälfte aller Stellungen.
• 1880: Der 15er-Puzzle-Boom erfasst die USA und Europa.
• 1891: Sam Loyd behauptet erstmals, es erfunden zu haben.
• 1907–1912: Hardys Puzzle zum Herausbringen eines Blocks wird patentiert.
• 1996: Rush Hour erscheint in den USA.
• 2002–2005: Rush Hour und Schiebepuzzles werden als PSPACE-vollständig bewiesen.