„Schiebeplättchen-Puzzle“ ist der Dachbegriff. Darunter sitzt ein halbes Dutzend benannter Puzzles, die alle eine Regel teilen — ein Plättchen kann sich nur in eine benachbarte leere Zelle bewegen — und alles andere variieren: Brettform, Plättchenzahl, Anzahl leerer Zellen, ob Plättchen rotieren können. Dieser Artikel geht den Stammbaum durch.
Der Quadratraster-Zweig: N-Puzzles
Die Hauptlinie der Familie. Ein quadratisches Brett mit N² − 1 nummerierten (oder bebilderten) Plättchen und einer leeren Zelle.
| Name | Brett | Plättchen | Schwerste optimale Lösung |
|---|---|---|---|
| 8-Puzzle | 3×3 | 8 | 31 Züge |
| 15-Puzzle | 4×4 | 15 | 80 Züge |
| 24-Puzzle | 5×5 | 24 | 152 Züge |
| 35-Puzzle | 6×6 | 35 | ~245 Züge |
| 48-Puzzle | 7×7 | 48 | unbekannt (Forschung) |
| 80-Puzzle | 9×9 | 80 | unbekannt |
Dieselbe Strategie — obere Zeile lösen, linke Spalte lösen, rekursiv — funktioniert in jeder Größe dieser Spalte. Größere Bretter bedeuten längere Lösungszeiten, nicht andere Puzzles.
Das sind die Puzzles, an die die meisten denken, wenn sie „Schiebepuzzle“ sagen. Es sind auch die, an denen Informatiker ihre Algorithmen benchmarken.
Nicht-quadratische Raster
Seltener, aber interessant:
Rechteckige — 3×4-, 4×5-, 5×6-Bretter. Manche kommerziellen Versionen, einschließlich hölzerner aus dem 19. Jahrhundert, waren rechteckig. Dieselbe Strategie funktioniert; das L-Eckmanöver ist an der asymmetrischen Kante leicht anders.
Hexagonal — Plättchen auf einem hexagonalen Raster, sechs mögliche Nachbarn pro Zelle statt vier. Mathematisch erlaubter (mehr Zugoptionen pro Zustand), psychologisch verwirrender. Eine Nische.
Dreieckig — Plättchen auf einem Dreiecksraster. Noch seltener. Die Mathematik geht, das Gameplay ist unhandlich.
Mehr als eine leere Zelle
Die Version mit einer leeren Zelle ist der Standard. Es gibt kommerzielle Puzzles mit zwei oder mehr leeren Zellen — am bekanntesten Klotski und seine Verwandten, bei denen Plättchen unterschiedlicher Größen (1×1, 1×2, 2×2) auf einem Brett mit ein paar leeren Zellen herumrutschen. Klotski ist strategisch ein anderes Spiel: Sie versuchen nicht, Plättchen zu ordnen, sondern ein bestimmtes Plättchen zum Ausgang zu manövrieren.
Klotski wird manchmal unter „Schiebeplättchen-Puzzle“ zusammengefasst. Tatsächlich ist es nicht ganz Teil der Familie — anderes Ziel, andere Strategie, andere mathematische Struktur.
Schieben plus Rotation
Kombinieren Sie die Schiebe-Regel mit einer Rotations-Mechanik, und Sie erhalten eine breite Vielfalt physischer Puzzles: die Hungarian Rings, bestimmte Rubik's-Cube-nahe Produkte und die sogenannten „Loopover“-Puzzles. Sie überschneiden sich mit der Schiebepuzzle-Familie, sind aber wiederum strategisch anders.
Für einen Spieler vom 15-Puzzle ist der nächste solche Cousin Rubik's 15 — ein kleines physisches Spielzeug mit dem 15-Puzzle-Layout, aber mit der Einschränkung, dass benachbarte Paare auch getauscht werden können.
Was die Familie zusammenhält
Zwei mathematische Tatsachen machen die Schiebepuzzle-Familie kohärent:
-
Zustandsgraph-Struktur. Jede Variante kann als Graph modelliert werden: Knoten sind Brettzustände, Kanten sind legale Züge. Optimales Lösen ist Kürzester-Weg in diesem Graphen. Der Graph ist riesig, aber wohlartig, und das ist, warum heuristische Suche so gut funktioniert.
-
Paritäts-Invarianten. Die meisten Varianten — einschließlich aller Standard-N-Puzzles — haben eine Paritätsregel, die die erreichbaren Zustände in zwei Hälften teilt. Eine Hälfte ist vom Ziel aus erreichbar; eine nicht. Apps, die zufällige Startpositionen erzeugen, prüfen entweder mit dem Paritätstest vor oder generieren durch Rückwärtslaufen vom Ziel.
Was spielen, je nach Stimmung
Wenn Sie noch keins davon ausprobiert haben:
- Beginnen Sie mit dem 8-Puzzle für zehn Minuten. Schnell genug, um die Regel aufzunehmen und die Strategie zu probieren.
- Wechseln Sie zum 15-Puzzle, wenn 8 trivial wirkt. Das ist die kanonische Erfahrung.
- Probieren Sie das 24-Puzzle, wenn Sie länger sitzen wollen.
- Probieren Sie Klotski, wenn Sie ein anderes Schiebepuzzle wollen — dieselbe Mechanik, anderes Ziel.
- Probieren Sie hexagonale Raster, wenn Sie sich wieder wie ein Anfänger fühlen wollen. Sie machen demütig.
Die meisten modernen Apps, unsere eingeschlossen, liefern 8, 15, 24 und 35-Puzzles in einem Paket. Das ist der zentrale Stamm der Familie, und am zentralen Stamm spielen fast alle.