1880 kündigte der amerikanische Rätselmacher Sam Loyd einen Preis von 1000 Dollar für jeden an, der ein bestimmtes 15-Puzzle löste: die Standardanordnung 1‑bis‑15 mit vertauschten 14 und 15. Die Puzzle-Manie hatte Amerika und Europa bereits erfasst; Loyds Stunt fügte Raketentreibstoff hinzu. Tausende versuchten es. Niemand gewann.
Es gab einen Grund, warum niemand gewann. Loyds Brett war beweisbar unlösbar, und der Beweis ist elementar genug, um auf eine Seite zu passen. Dieser Artikel ist diese Seite.
Die Behauptung
Genau die Hälfte aller 16!/2 ≈ 10.461.394.944.000 Wege, fünfzehn Plättchen und eine Lücke auf einem 4×4-Brett anzuordnen, kann zum Standardziel gelöst werden. Die andere Hälfte kann nicht gelöst werden. Loyds „14 und 15 vertauscht“ sitzt in der unlösbaren Hälfte.
Das verallgemeinert sich. Auf jedem N×N-Schiebepuzzle ist die Hälfte aller Anordnungen unlösbar. Das 3×3-8-Puzzle hat 9!/2 = 181.440 lösbare Bretter von insgesamt 362.880; die 24-, 35- und so weiter folgen derselben Regel.
Inversionen
Der Beweis braucht eine Definition. Lesen Sie die Plättchen in Lesereihenfolge — von links nach rechts entlang Zeile 1, dann Zeile 2, dann Zeile 3, dann Zeile 4 — und ignorieren Sie die Lücke. Sie bekommen eine Folge von fünfzehn Zahlen.
Eine Inversion ist ein Paar (a, b), wo a früher in der Folge erscheint als b, aber a > b. Zählen Sie jedes solche Paar über die ganze Folge. Diese Zahl ist die Inversionszahl des Bretts.
Beispiel: Der Zielzustand 1, 2, 3, …, 15 hat null Inversionen. Loyds „14 und 15 vertauscht“ hat die Folge 1, 2, 3, …, 13, 15, 14, mit genau einer Inversion (Paar 15, 14).
Das Schlüssel-Lemma: ein Schub ändert Parität kontrolliert
Was passiert mit der Inversionszahl bei einem legalen Zug?
-
Horizontale Schübe (Plättchen rutscht eine Zelle nach links oder rechts): Das bewegte Plättchen ändert seine Position in der Lese-Folge um einen Slot. Sein relativer Rang gegenüber jedem anderen Plättchen in der Folge bleibt exakt gleich — weil horizontale Bewegung weder die Zeile des Plättchens noch die Plättchen vor oder nach ihm in der Zeilenreihenfolge ändert. Die Inversionszahl bleibt unverändert.
-
Vertikale Schübe (Plättchen rutscht eine Zelle nach oben oder unten): Das bewegte Plättchen überspringt drei andere Plättchen in der Lese-Folge — die drei Plättchen in der Zeile, durch die es geht. Jedes der drei wechselt von „nach“ zu „vor“ oder umgekehrt, was bedeutet, dass jedes ±1 zur Inversionszahl beiträgt. Die Summe von drei ±1 ist immer ungerade. Die Inversionszahl ändert sich um eine ungerade Zahl.
Zusammenfassung: Ein horizontaler Schub erhält die Parität der Inversionszahl (gerade oder ungerade). Ein vertikaler kippt sie.
Die Zeile der Lücke kippt ebenfalls bei vertikalen Schüben
Verfolgen Sie die Zeile der Lücke, von oben gezählt. Ein horizontaler Schub lässt die Lücke in derselben Zeile. Ein vertikaler bewegt sie um eine Zeile, ihre Parität wechselt (gerade ↔ ungerade).
Wir haben jetzt zwei Dinge, die sich zusammen ändern:
- Inversions-Paritätskippen ⇔ vertikaler Schub.
- Zeilen-Paritätskippen ⇔ vertikaler Schub.
Ihre Summe ist daher unter jedem legalen Schub invariant. Wir haben eine erhaltene Größe gefunden.
Der Paritätssatz
Definieren Sie die Invariante:
P = (Inversionszahl) + (Zeilennummer der Lücke, von unten ab 1 gezählt)
Das ist die erhaltene Größe. Bei jedem legalen Schub ändert sich P um eine gerade Zahl, also bleibt seine Parität (gerade oder ungerade) gleich.
Der Zielzustand hat null Inversionen und die Lücke in Zeile 1 von unten — also P = 1 (ungerade). Jedes Brett mit geradem P ist vom Ziel aus unerreichbar, und umgekehrt ist das Ziel von jedem solchen Brett unerreichbar.
Das ergibt einen sauberen Lösbarkeitstest für das 15-Puzzle:
- Plättchen in Zeilenreihenfolge lesen, Lücke ignorierend.
- Inversionen zählen.
- Zeile der Lücke von unten zählen (1, 2, 3 oder 4).
- Addieren. Ist die Summe ungerade, ist das Brett lösbar. Ist sie gerade, nicht.
Loyds „14 und 15 vertauscht“ hat 1 Inversion und die Lücke in Zeile 1 von unten — Summe 2, gerade, unlösbar.
Wie das für andere Größen aussieht
Die N×N-Paritätsregel hängt davon ab, ob N gerade oder ungerade ist. Die allgemeine Aussage:
- N ungerade (3×3, 5×5, …): Brett ist lösbar genau dann, wenn die Inversionszahl gerade ist. Die Zeile der Lücke spielt keine Rolle, weil die Paritätsparität der Zeile aus Symmetriegründen durch die Inversions-Parität bestimmt ist.
- N gerade (4×4, 6×6, …): Brett ist lösbar genau dann, wenn (Inversionszahl) + (Zeile der Lücke von unten) ungerade ist.
Für 3×3 ist der Test einfach „ist die Anzahl der Inversionen gerade?“. Das ist einfacher als die 4×4-Version und in einer Minute zu merken.
Eine schöne Folge
Da genau die Hälfte aller Anordnungen lösbar ist, ist ein zufälliges Mischen plus Paritätsprüfung schneller als ein zufälliges Mischen plus Lösungsversuch. Apps, die lösbare Startpositionen garantieren müssen, entweder:
- Voraus mit dem Paritätstest prüfen und bei Fehlschlag neu mischen.
- Durch Rückwärtslaufen vom Ziel erzeugen, indem zufällige legale Schübe angewendet werden. Das garantiert Lösbarkeit per Konstruktion, und das machen die meisten Apps, unsere eingeschlossen.
Wenn Sie je ein Schiebepuzzle spielen und es trotz aller Versuche unmöglich finden, hat die App es schlecht erzeugt — nicht Ihr Fehler, und kein Puzzle aus dem Universum.
Die Sam-Loyd-Fußnote
Loyds 1000-Dollar-Preis ist einer der besser dokumentierten praktischen Scherze der Rätselgeschichte. Der Mathematiker, der die Unlösbarkeit bewies — unabhängig — war entweder William Johnson und William Story (1879, American Journal of Mathematics) oder Loyd selbst, je nachdem, wem man glaubt. Loyd war eine berüchtigt selbstvermarktende Figur, die mehrere Erfindungen für sich beanspruchte, die er nicht erfunden hatte; das 15-Puzzle selbst wurde von Noyes Chapman 1874 erfunden, sechs Jahre vor Loyds Preis-Stunt.
Was Loyd wirklich beitrug, waren der Preis, die Publicity und die unlösbare Variante — ein nützlicher Beitrag, wenn auch nicht der, den er bewarb.