Es gibt eine Methode, Schiebepuzzles per Hand zu lösen. Sie hängt nicht von der Brettgröße ab. Sobald Sie sie für 3×3 haben, haben Sie sie auch für 4×4, 5×5, 6×6 und jede größere Größe. Hier ist die Methode.
Der Plan
Für ein N×N-Puzzle:
- Zeile 1 lösen — Plättchen 1, 2, …, N in die obere Zeile platzieren.
- Spalte 1 lösen — Plättchen N+1, 2N+1, … in die erste Spalte unter Zeile 1 platzieren.
- Sie haben jetzt ein (N−1)×(N−1)-Puzzle. Rekursion.
- Basisfall — wenn Sie ein 2×2 erreichen, sind die verbleibenden Plättchen entweder in Position, oder Sie brauchen eine Paritätsprüfung.
Das ist der ganze Algorithmus. Drei Sätze. Der Rest ist Mechanik.
Die Mechanik: Ecken
Die ersten Plättchen einer Zeile oder Spalte zu platzieren ist einfach. Der Trick ist, das letzte Plättchen — das Eckplättchen — zu platzieren.
Für die rechte obere Ecke von Zeile 1 (Plättchen N auf einem N×N-Puzzle):
- Versuchen Sie nicht, Plättchen N direkt in die Ecke zu schieben. Es bleibt dort nicht.
- Setzen Sie das vorherige Plättchen (N−1) zuerst in die Ecke.
- Setzen Sie Plättchen N direkt unter N−1.
- Drehen Sie nun das Paar: Lücke in die Ecke (N−1 verdrängend), N−1 nach unten-und-links schieben, N nach oben in die Ecke schieben, N−1 nach rechts.
Effekt: N−1 und N enden korrekt platziert, ohne dass etwas links von ihnen gestört wird.
Das ist das L-förmige Eckmanöver. Der gleiche Trick, gespiegelt, funktioniert in der linken unteren Ecke von Spalte 1.
Wenn Sie sich nur ein Stück Schiebepuzzle-Technik merken, merken Sie sich dieses. Alles andere folgt daraus.
Die Mechanik: Mitte
Für das Innere einer Zeile (Plättchen 1 bis N−2 in der oberen Zeile) ist das Platzieren direkt:
- Finden Sie das Plättchen.
- Bringen Sie es an eine Position, die neben seinem Ziel liegt.
- Verwenden Sie die Lücke, um es einzuschieben.
Sie müssen vielleicht andere nicht platzierte Plättchen beiseite schieben. Das ist okay — sie sind nicht platziert. Solange Sie bereits platzierte Plättchen links nicht stören, baut sich die Zeile sauber auf.
Die Regel, die Sie sicher hält: Lassen Sie die Lücke nie über ein platziertes Plättchen wandern. Wenn die Lücke von der rechten Seite des Bretts links neben ein platziertes Plättchen muss, müssen Sie sie um das platzierte Plättchen herum durch nicht platzierte Zellen leiten.
Warum „Zeile, dann Spalte“
Zwei Gründe:
- Spiegelsymmetrie. Das Zeilen-Eckmanöver und das Spalten-Eckmanöver sind exakt derselbe Trick, gespiegelt. Eines zu lernen lehrt das andere.
- Die Lücke hat Raum zum Arbeiten. Nach dem Lösen von Zeile 1 hat die Lücke die unteren (N−1) Zeilen zum Manövrieren. Nach dem Lösen von Spalte 1 hat sie einen (N−1)×(N−1)-Bereich. Der Arbeitsbereich schrumpft elegant.
Sie könnten alternieren (Zeile 1, Spalte 1, Zeile 2, Spalte 2, ...), aber der natürliche Rhythmus ist, sie paarweise außen zu machen und zu rekursieren.
Die Rekursion
Wenn Zeile 1 und Spalte 1 fertig sind, enthält das verbleibende (N−1)×(N−1)-Puzzle Plättchen, die in eine andere Zielkonfiguration müssen — dieselbe numerische Folge, aber in anderen Positionen. Die gute Nachricht: der Methode ist das egal. Neue obere Zeile lösen, neue linke Spalte, rekursieren. Irgendwann erreichen Sie einen 2×2- oder 3×3-Basisfall.
Für den 3×3-Basisfall können die letzten drei Plättchen mit wiederholten Einzelzügen in Position gedreht werden. Für einen 2×2-Basisfall (der am Ende großer Puzzles auftreten kann) gilt dasselbe.
Warum das auf jeder Größe funktioniert
Die Schiebepuzzle-Familie hat eine nützliche rekursive Eigenschaft: Das Lösen einer Zeile-und-Spalte reduziert das Puzzle auf ein kleineres Puzzle gleicher Art. Die Mathematik ist geradlinig. Nach Platzieren von N Plättchen in Zeile 1 (und ohne sie wieder anzufassen) lebt das verbleibende Spiel auf einem (N−1)-breiten Raster, dem eine Zeile fehlt. Nach Platzieren der linken Spalte lebt es auf einem (N−1)×(N−1).
Diese Reduktion lässt sich in jedem Schritt anwenden. Das 6×6 reduziert sich auf 5×5, das sich auf 4×4 reduziert, das sich auf das 3×3-Endspiel reduziert. Das 3×3-Endspiel ist das einzige mit einer spezialisierten Technik; alles Größere reduziert sich darauf.
Diese rekursive Struktur ist, warum Schiebepuzzles in Programmierkursen oft verwendet werden, um Divide-and-Conquer zu lehren. Der Korrektheitsbeweis ist ein Absatz; die Implementierung ist der Algorithmuskörper.
Wie schnell Sie werden
Ein neuer Löser, der die Methode buchstäblich anwendet, braucht:
Innerhalb weniger Partien pro Größe halbieren sich diese Zeiten. Die Methode ist dieselbe; es ist nur das Motorgedächtnis für das Eckmanöver.
Wofür diese Methode nicht gut ist
Optimale Lösungen. Ein Computer mit einem echten Solver findet Folgen, die 30–50 % kürzer sind als die Zeilen-und-Spalten-Methode liefert. Menschen können diese Algorithmen nicht im Kopf laufen lassen.
Speedsolving-Wettbewerbe. Top-menschliche Speedsolver verwenden die Zeilen-und-Spalten-Methode als Basis, schneiden aber aggressiv Ecken ab, machen partielle Platzierungen, die sie später rückgängig machen. Schneller, aber schwerer zu lernen.
Für alle anderen — die Zeilen-und-Spalten-Methode ist die Methode.