Das 15-Puzzle — manchmal „Fünfzehnerspiel“, „Boss-Puzzle“ oder einfach „der 4×4-Schieber“ — ist das kanonische Schiebepuzzle. Ein 4×4-Brett, fünfzehn nummerierte quadratische Plättchen, eine leere Zelle. Sie schieben Plättchen in die Lücke, einen Zug nach dem anderen, bis die Zahlen geordnet sind: 1‑2‑3‑4 oben, 5‑6‑7‑8, 9‑10‑11‑12, 13‑14‑15 und die Lücke in der rechten unteren Ecke.
Woher es kommt
Das Puzzle wurde 1874 von Noyes Palmer Chapman, einem Postmeister aus Canastota, New York, erfunden. Bis 1880 hatte es die Bostoner Schulen erreicht, Mitte 1880 war es in den USA eine Massenbewegung, und im Herbst überquerte es den Atlantik und ergriff Großbritannien, Frankreich und Deutschland. Zeitungen druckten Spalten mit Lösungen. Arbeiter ließen ihre Arbeit liegen, um zu puzzeln. Behörden in manchen deutschen Städten verboten es Berichten zufolge im öffentlichen Raum, weil Beamte nichts anderes mehr taten.
Sam Loyd — der New Yorker Rätselmacher, dem nie eine selbstinszenierte Geschichte fehlte — behauptete, er habe es erfunden (hatte er nicht), und bot 1000 Dollar in bar demjenigen an, der eine bestimmte Variante mit vertauschten 14 und 15 löste. Diese Variante stellte sich als mathematisch unlösbar heraus (Beweis siehe 15-Puzzle-Parität). Niemand gewann. Loyd war zufrieden.
Wie man spielt
Drei Regeln:
- Sie können nur ein Plättchen verschieben, das benachbart zum leeren Feld ist — direkt darüber, darunter, links oder rechts davon. Keine Diagonalen.
- Der Zug bewegt das Plättchen ins leere Feld. Das leere Feld ist jetzt dort, wo das Plättchen war.
- Fertig, wenn die Plättchen in numerischer Reihenfolge sind.
Das war's. Kein Zeitlimit, keine Wertung, kein zweites Ziel. Das ganze Spiel steckt in diesen drei Sätzen.
Wie schwer ist es?
Das 15-Puzzle hat 16!/2 ≈ 10,46 Billionen erreichbare Anordnungen (die Hälfte aller 16! wegen der Paritätsregel). Die kürzeste Lösung von der schwierigsten Startposition aus beträgt 80 Züge. Der Median liegt bei etwa 52.
Ein Anfänger löst sein erstes 15-Puzzle in 15–30 Minuten durch Versuch und Irrtum. Ein Spieler, der die Zeilen-und-Spalten-Methode vom 8-Puzzle gelernt hat, löst jedes 15-Puzzle in 3–7 Minuten. Ein Speedsolver, der optimale Züge rennt, schafft es unter 90 Sekunden.
Was das 4×4 zum Sweetspot macht
Es hat einen Grund, dass das 15-Puzzle — und nicht das 8 oder das 24 — zum Weltphänomen wurde. Das 4×4-Brett ist:
- Lang genug, um befriedigend zu sein. Das 8-Puzzle löst sich so schnell, dass es keinen Spannungsbogen hat. Das 15 dauert lange genug, um die kleine Erleichterung eines fertigen Bretts zu geben.
- Kurz genug, um nicht zu nerven. Das 24-Puzzle braucht für einen sicheren Spieler 15+ Minuten. Das 35-Puzzle 30+. Das 4×4 passt in eine Kaffeepause.
- Gerade schwierig genug, um darüber nachzudenken. Die Strategie ist beim ersten Kontakt nicht offensichtlich. Das L-Manöver in der Ecke muss entdeckt oder gelehrt werden — und sobald das passiert, öffnet sich das ganze Puzzle.
Dieser Sweetspot ist der Grund, dass das 15-Puzzle die Größe ist, die als Kürzel für die ganze Familie steht. Leute sagen „Schiebepuzzle“ und stellen sich ein 4×4 vor.
In der Informatik
Jahrzehntelang war das 15-Puzzle der Standard-Benchmark für heuristische Suchalgorithmen. Richard Korfs Arbeit von 1985, die IDA* einführte, verwendete 100 zufällige 15-Puzzles, um die Beschleunigung gegenüber A* zu demonstrieren. Moderne Mustertabellen-Arbeiten berichten ihre Ergebnisse bis heute am 15-Puzzle. Das Puzzle ist gerade klein genug, um lösbar zu sein, gerade groß genug, dass schlechte Algorithmen ein Timeout erreichen.
Wer einen Einführungskurs in KI besucht hat, hat ein 15-Puzzle als Programmieraufgabe gelöst — vermutlich mit A* und der Manhattan-Distanz-Heuristik. (Für tiefer gehendes Material siehe den Solver-Artikel.)
Varianten in modernen Apps
Das 15-Puzzle hat in heutigen Apps einige gängige moderne Varianten:
- Zahlenplättchen — das Original, schlichte Ziffern auf den Plättchen.
- Bildplättchen — ein in N×N geschnittenes Foto ersetzt die Zahlen. Sie lösen, indem Sie das Bild zusammensetzen.
- Hybrid — Bildplättchen mit optional eingeblendeten kleinen Zahlen, für Spieler, die einen Hinweis darauf wollen, wo jedes Plättchen hingehört.
Manche Apps gehen weiter: hexagonale Raster, größere Bretter (5×5 = 24-Puzzle, 6×6 = 35-Puzzle), Rotationspuzzles, in denen Plättchen sich drehen können, und so weiter. Aber die nummerische 4×4-Version ist die Lingua franca.
Wo spielen
Auf dem Handy sind native Apps das geschmeidigere Erlebnis — kein Upload, keine Analytik, keine Werbung mitten in einem Plättchen-Schub. Slide Puzzle kommt mit der klassischen nummerierten Version plus 300 fotografischen Motiven und vier Größen (3×3, 4×4, 5×5, 6×6).
Im Web gibt es Dutzende browserbasierter 15-Puzzles. Sie sind praktisch, laden aber importierte Fotos meist auf einen Server und führen Analytik aus. Wenn Sie nur ein paar Partien spielen und nie ein eigenes Foto importieren wollen, reicht das.
Wenn Sie noch keins gelöst haben, beginnen Sie dreißig Sekunden lang mit dem 8-Puzzle — nur um den Zug zu spüren — und kommen dann zum 15 zurück. Die Strategie, die Sie am kleineren Brett aufgreifen, lässt sich direkt übertragen.