14-15-Puzzle

15-Puzzle-Spiel aus Plastik
(Ordne die Zahlen aufsteigend von 1 bis 15.)

Das 15-Puzzle, auch 14-15-Puzzle oder Ohne-Fleiß-kein-Preis-Spiel genannt, ist ein in seiner ursprünglichen Aufgabenstellung unlösbares Geduldsspiel. Es wurde zwischen 1870 und 1880 in den Vereinigten Staaten vom Postangestellten Noyes Palmer Chapman erfunden. Das Spiel besteht aus 15 in einem Vier-mal-vier-Quadrat angeordneten Zahlen, die durch Verschiebungen aufsteigend geordnet werden müssen.

Heutige Ausgaben sind abgewandelte Formen des ursprünglichen Spiels mit geänderter Anfangsanordnung, durch die sie lösbar sind. Es gibt auch Ausführungen in anderen Größen, so das 8-Puzzle in einem Drei-mal-drei-Quadrat und das 31-Puzzle in einem Vier-mal-acht-Rechteck.

Geschichte

Das Spiel wurde von dem Postangestellten Noyes Palmer Chapman erfunden, der seinen Freunden im Jahr 1874 ein ähnliches Puzzle zeigte. Bei diesem ging es darum, 16 nummerierte Blöcke in die Form eines magischen Quadrates zu bringen. Die ersten Kopien des 15-Puzzles gelangten nach Syracuse im Staat New York zu Frank Chapman, dem Sohn von Noyes. Von dort verbreitete sich das Spiel weiter nach Watch Hill und schließlich nach Hartford in Connecticut, wo Schüler der amerikanischen Schule für Hörbehinderte das Puzzle in großen Auflagen fertigten und im Dezember 1879 als Weihnachtsgeschenke in Boston, Massachusetts verkauften. Matthias Rice, der Besitzer eines Geschäftes für ausgefallene Holzgegenstände, entdeckte eines dieser Puzzles und fing an, diese umgehend selbst herzustellen und als „Gem Puzzle“ auf den Markt zu bringen. Gegen Ende Januar 1880 setzte der Zahnarzt Charles Pevey ein Preisgeld für die Lösung des 15-Puzzles aus. Der erste Megatrend für das Spiel war in den USA im Februar, in Kanada im März und in Europa im April 1880 zu sehen. Der Trend war bereits im Juli desselben Jahres aber wieder im Rückgang. Erst neun Jahre später wurde das Spiel in Japan eingeführt.^[1]

Chapman wollte das 15-Puzzle am 21. Februar 1880 als „Block Solitaire Puzzle“ zum Patent anmelden, stieß beim Patentamt aber auf Ablehnung, da sich sein Spiel nicht ausreichend von dem am 20. August 1878 erteilten Patent für das von Ernest U. Kinsey entwickelte Spiel „Puzzle-Blocks“ zu unterscheiden schien.^[1]

Der Rätselspezialist Samuel Loyd behauptete von 1891 bis zu seinem Tod im Jahr 1911, dass er der Erfinder dieses Rätsels sei, konnte dies aber niemals belegen. Neueren Untersuchungen zufolge wurde er sogar als Lügner entlarvt.^[1][2]

Ursprüngliche Aufgabenstellung

In einem quadratischen Rahmen der Größe vier mal vier liegen 15 Steine, die von 1 bis 15 durchnummeriert sind. In der Ausgangsposition sind die Steine mit Ausnahme der Steine 14 und 15 in aufsteigender Reihenfolge sortiert, das letzte Feld bleibt frei.

Dadurch ergibt sich folgendes Bild:

Die Aufgabe besteht nun darin, die Steine durch eine Folge von Zügen in die richtige Reihenfolge zu bringen:

Erlaubt sind nur solche Züge, bei denen ein Stein, der horizontal oder vertikal direkt neben dem freien Feld liegt, dorthin verschoben wird.

Das Spiel ist aus dieser Ausgangsstellung nicht lösbar.

Skizze des Beweises für die Unlösbarkeit

Jede Stellung des Spiels ist entweder lösbar oder unlösbar, das heißt, sie kann in die Endstellung überführt werden oder nicht. Zum Beweis wird die so genannte Parität jeder Stellung betrachtet. Sie bleibt bei einem Zug immer erhalten. Die Parität ergibt sich aus der Anzahl der ungeordneten Zahlenpaare. Dabei ist N₁ die Anzahl der Zahlenpaare, die sich in falscher Reihenfolge befinden und N₂ die Nummer der Reihe, in der sich das leere Feld befindet. Die Summe N = N₁ + N₂ ist entweder gerade oder ungerade. Bei allen erlaubten Zügen bleibt diese Parität erhalten, das heißt eine gerade Spielstellung kann nie in eine ungerade überführt werden und umgekehrt. Da die ursprüngliche Aufgabenstellung ungerade ist, kann sie nie in den geraden Endzustand führen.

Ein andere Beweisidee verwendet das Signum der als Permutation, also als Vertauschung betrachteten Stellung, welches mit jedem Zug das Vorzeichen wechselt.

Beispiel

Um zu überprüfen, ob eine Konstellation von Steinen mittels erlaubter Züge in eine andere überführt werden kann, ist zwischen Rahmengrößen mit geradzahliger (wie der vorliegenden) und solchen mit ungeradzahliger Spaltenanzahl zu unterscheiden. Grundvoraussetzung ist, dass die Quadrate in der gezeigten Weise nummeriert sind oder bei Puzzles, deren Lösung in der Erstellung eines Bildes liegt, für den Nachweis nummeriert werden. Bei Puzzles, die mehrere Lösungen erlauben, etwa Symbole, die nach bestimmten Regeln angeordnet werden sollen, ist nachzuweisen, dass keine der Lösungsvarianten durch erlaubte Züge erreicht werden kann.

Zur Ermittlung des Unordnungsparameters N₁ zählt man alle Zahlenpaare, bei denen eine kleinere Zahl auf eine größere folgt, gleich wieviele Steine dazwischen liegen; die absolute Größe der jeweiligen Zahlen ist unerheblich, Zahlen können in mehreren Paaren vorkommen. Verglichen werden die Steine so, als wären alle in einer horizontalen Reihe aufgelistet. Bei einer Konstellation von beispielsweise 1, 4, 2, 6, 7, 8, 3, 5 gibt es also folgende Paare (2|4), (3|8), (3|7), (3|6), (3|4), (5|8), (5|7), (5|6). Man iteriert von links nach rechts und vergleicht eine Zahl mit allen links stehenden Zahlen. Sobald eine links stehende Zahl dann größer ist, wurde ein unordentliches Paar gefunden.

In der Konstellation dieses Bildes beträgt N₁=3; die unordentlichen Paare sind (11|12), (11|13), (11|14).

Wird ein Stein in horizontaler Richtung verschoben, ändern sich weder der Unordnungsparameter N₁ noch der Reihenparameter N₂, da man diese Bewegung als Austausch des bewegten Steins durch das freie Feld auffassen kann, das in der Berechnung des Unordnungsparameters nicht berücksichtigt wird.

Wird ein Stein in vertikaler Richtung verschoben, ändert sich der Reihenparameter N₂ um +/− 1. Die vertikale Verschiebung betrifft immer genau drei Zahlenpaare, denn es kann nur Änderungen in der Ordnung zwischen dem verschobenen Stein und den drei eingeschlossenen Feldern geben. Dabei hat sich für jeden eingeschlossenen Stein der Unordnungsparameter um 1 vergrößert oder verkleinert, da der zu verschiebende Stein seinen Platz getauscht hat, haben nun alle Paare, welche mit dem verschiebenden Stein gebildet wurden, ihre Ordnung geändert. Unordentliche Paare sind nun ordentliche und umgekehrt.

Beim oben stehenden Beispiel ändern also alle drei ordentlichen Paare (7|8), (7|9), (7|10) durch das Verschieben in einen unordentlichen Zustand. N₁ wird also um drei erhöht.

N war von Anfang an gerade (N=4). Da der Reihenparameter N₂ bei jedem Schritt eine ungerade Veränderung erfährt (+1, −1) und der Ordnungsparameter N₁ ebenfalls nur eine ungerade Veränderung erfährt (+3, +1, −1, −3), kann N jeweils nur eine gerade Änderung erfahren (+4, +2, 0, −2, −4). Es ist also nicht möglich von der ursprünglichen Aufgabenstellung (15 mit 14 getauscht) in eine sortiere Reihenfolge zu gelangen, da die ursprüngliche Reihenfolge (N = 5) eine ungerade Parität hat und nicht mit dem Verschieben von Steinen in eine gerade Parität überführt werden kann.

Allgemeine Überlegungen

In einem a × b großen Puzzle mit ungeradzahliger Spaltenanzahl a beträgt die Anzahl der eingeschlossenen Steine a−1, also eine gerade Zahl; der Unordnungsparameter ändert sich also mit einem horizontalen Zug gar nicht und mit einem vertikalen Zug um eine gerade Zahl. Die Parität des Unordnungsparameter N₁ bleibt mit jedem Zug erhalten.

In einem a × b großen Puzzle mit geradzahliger Spaltenanzahl a (wie dem vorliegenden) beträgt die Anzahl der eingeschlossenen Steine a−1, a ist in diesem Fall eine ungerade Zahl, der Unordnungsparameter N₁ ändert sich mit einem vertikalen Zug um eine ungerade Zahl. Der Reihenparameter N₂ vergrößert oder verkleinert sich mit jedem vertikalen Zug um 1; N₁+N₂ ist also die Summe aus zwei ungeraden Zahlen und damit gerade. Die Parität von (N₁+N₂) bleibt mit jedem Zug erhalten.

Da die Parität von N₁ bei ungeradzahliger oder (N₁+N₂) bei geradzahliger Spaltenanzahl stets erhalten bleibt, kann man durch einfaches Abzählen prüfen, ob eine zufällige Konstellation K₁ in eine andere bestimmte Konstellation K₂ mittels erlaubter Züge überführt werden kann. Bei der klassischen Aufgabestellung des 15-Puzzles ist das nicht möglich, da bei geradzahliger Spaltenanzahl a=4 die Summe (N₁+N₂)=(1+4)=5 in (N₁+N₂)=(0+4)=4 überführt werden müsste.

Des Weiteren zeigen diese Überlegungen, dass höchstens die Hälfte aller denkbaren Konstellationen aus der Grundkonstellation heraus erreicht werden kann, weil nur Anordnungen von geraden in gerade oder ungeraden in ungerade Paritäten überführt werden können. Faktisch ist von der Grundkonstellation genau diese Hälfte immer erreichbar, was aber durch den hier vorgestellten Beweis nicht nachgewiesen werden kann, da die Parität lediglich eine notwendige, nicht aber eine hinreichende Bedingung für die allgemeine Lösbarkeit ist. Dass alle Konstellationen von geraden Paritäten tatsächlich ineinander überführt werden können oder alle Konstellationen mit ungeraden Paritäten ineinander überführt werden können, ist eine Aufgabe vom Aufzeigen von allgemein gültigen Algorithmen für dieses Spiel.

Heutige Spiele

15-Puzzle als Schlüsselanhänger

Die heutigen Spiele haben das Spielprinzip abgewandelt. Da es nicht möglich ist, das ursprüngliche 15-Puzzle zu lösen, sind viele Puzzles im Handel, die bereits richtig sortiert sind. Das Ziel des Spieles ist es nun, ein gemischtes Puzzle wieder in den Originalzustand zu versetzen, d. h. die Aufgabenstellung ist vergleichbar mit der des Zauberwürfels.

Im Handel findet man viele Formen dieses Spiels. Es gibt sie beispielsweise als Schlüsselanhänger aus Plastik oder Holz gefertigt. Es gibt auch Spiele, die nicht mehr das Ziel haben, Zahlen zu sortieren, sondern aus einem Bild bestehen, das nur komplett zu sehen ist, wenn alle Quadrate in einer richtigen Reihenfolge sortiert werden.

Weblinks

• 8-Puzzles-Applet – Deutschsprachige Seite, welche ein selbstlösendes Schiebepuzzle als Java-Applet und als Mashup anbietet.
• The 14-15-Puzzle – Englischsprachige Seite, die den Beweis der Unlösbarkeit des ursprünglichen 15-Puzzles anhand interaktiver Beispiele illustriert.

Einzelnachweise

1. ↑ ^{a b c} Jerry Slocum & Dic Sonneveld, The 15 Puzzle. ISBN 1-890980-15-3
2. ↑ Sam Loyd's Fifteen Englischsprachige Seite mit Java-Applet und Beweis der Unlösbarkeit des Problems. Abgerufen 16.11.2007