Wer je dreißig Minuten an einem 15-Puzzle saß, das einfach nicht fertig wird — jeder Zug führt am Ende zu zwei vertauschten Plättchen —, dem ist eine Chance, dass das Puzzle mathematisch unlösbar ist. Genau die Hälfte aller 15-Puzzle-Anordnungen ist es. Eine schlecht geschriebene App kann eine versehentlich erzeugen.
Dieser Artikel ist die praktische Prüfung. Die volle mathematische Begründung lebt im Paritätssatz; diese hier bleibt schlicht.
Die 30-Sekunden-Prüfung
Betrachten Sie die Plättchen in Lesereihenfolge — von links nach rechts entlang jeder Zeile, von oben nach unten — und ignorieren Sie die Lücke.
Zählen Sie für jedes Paar Plättchen, wie oft eine größere Zahl vor einer kleineren erscheint. Diese Zahl ist die Inversionszahl.
Dann merken Sie sich, in welcher Zeile die Lücke ist, von unten gezählt (die unterste Zeile ist 1, darüber 2, dann 3, dann 4 oben).
Addieren Sie Inversionszahl und Lücken-Zeile-von-unten. Ist das Ergebnis ungerade, ist das Puzzle lösbar. Ist es gerade, nicht.
Das ist es. Das ist die ganze Prüfung.
Ein durchgearbeitetes Beispiel
Angenommen, Ihr Brett sieht so aus:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Lesereihenfolge: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Inversionen zählen. Wir müssen jedes Paar finden, in dem eine größere Zahl vor einer kleineren steht. Durchgehen: 15 erscheint vor 14, und das ist die einzige Inversion. Also Inversionszahl = 1.
Die Lücke ist in der untersten Zeile → Zeile 1 von unten.
Summe: 1 + 1 = 2. Gerade. Dieses Brett ist unlösbar.
Das ist tatsächlich Sam Loyds Preisrätsel von 1880. Der Mann bot 1000 Dollar dem, der es löste. Das Rätsel war unlösbar; er behielt sein Geld.
Ein anderes Beispiel
Angenommen, Ihr Brett:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Lesereihenfolge: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Inversionen zählen:
- 5 vor 1 → 1 Inversion (5 > 1, und 5 kommt zuerst)
- 5 vor 3 → 1 Inversion
- 5 vor 4 → 1 Inversion
- 5 vor 2 → 1 Inversion
- 3 vor 2 → 1 Inversion
- 4 vor 2 → 1 Inversion
Gesamt-Inversionen: 6.
Lücke in unterster Zeile → Zeile 1.
Summe: 6 + 1 = 7. Ungerade. Lösbar.
Warum das funktioniert (kurz)
Ein legaler Schub bewegt ein Plättchen entweder horizontal (keine Änderung der Inversionen, keine der Lücken-Zeile) oder vertikal (Inversionen um eine ungerade Zahl, Lücken-Zeile um 1).
In jedem Fall bleibt die Summe aus Inversionen + Lücken-Zeile gerade-oder-ungerade so, wie sie begann. Diese Summe ist eine Invariante — eine Eigenschaft des Puzzles, die legale Züge nicht ändern können.
Der Zielzustand (1‑2‑3‑...‑15 mit Lücke unten rechts) hat 0 Inversionen und die Lücke in Zeile 1 von unten. Summe: 1, ungerade. Also hat jedes lösbare Puzzle eine ungerade Summe. Jedes mit gerader Summe kann das Ziel nicht erreichen.
Für den vollen Beweis mit allen Fällen siehe die Paritätssatz-Seite.
Was ist mit 8-Puzzles (3×3)?
Für 3×3 ist die Prüfung einfacher:
- Inversionen in Lesereihenfolge zählen.
- Wenn gerade, lösbar.
- Wenn ungerade, unlösbar.
Sie müssen die Zeile der Lücke für 3×3 nicht verfolgen — die Symmetrie des Puzzles macht die Zeilen-Abhängigkeit redundant.
(Für 5×5 — gleiche Regel wie für 3×3. Für 6×6 — gleiche Regel wie für 4×4. Die Regel lautet „Zeile der Lücke zählt, wenn N gerade ist“.)
Was tun, wenn Ihre App unlösbare Puzzles erzeugt
Das sollte nie passieren. Eine gut geschriebene App verwendet eine von zwei Methoden, um es zu vermeiden:
Durch Rückwärtslaufen vom Ziel erzeugen. Mit dem Zielzustand starten, zufällige legale Züge anwenden, und der resultierende Zustand ist die Startposition. Jede so erzeugte Position ist per Konstruktion lösbar.
Zufällig erzeugen, dann mit Parität testen. Plättchen gleichverteilt zufällig mischen; Paritätstest berechnen; ist sie gerade, zwei beliebige Plättchen tauschen, um es zu korrigieren. Die resultierende Position ist garantiert lösbar.
Wenn Sie auf ein unlösbares Puzzle in einer App stoßen, ist diese App kaputt. Bug melden, App wechseln. Slide Puzzle verwendet die Rückwärtslauf-vom-Ziel-Methode und kann keine unlösbaren Startpositionen produzieren.
Was tun, wenn Sie Ihr physisches Puzzle für unlösbar halten
Zwei Dinge:
- Die Prüfung machen. Inversionen plus Lücken-Zeile. Wenn gerade, wurden die Stücke falsch zusammengesetzt. Ein Plättchen herausnehmen, mit einem benachbarten tauschen, und das Puzzle ist lösbar.
- Wenn auch nach einem Tausch das Puzzle Ihnen widersteht — der Widerstand ist Ihre Strategie, nicht das Puzzle.
Die Paritätsprüfung dauert etwa dreißig Sekunden. Sie zu machen, bevor Sie eine weitere Stunde in ein festsitzendes Brett versenken, ist ein vernünftiger Gebrauch dieser Sekunden.