Das 15-Puzzle
Das 15-Puzzle ist ein Rahmen mit fünfzehn nummerierten Steinen und einer Lücke. Schieben Sie die Steine wieder in die richtige Reihenfolge, und es ist gelöst. Es sieht einfach aus, löste aber 1880 ein Puzzle-Fieber aus, und dahinter steckt einer der elegantesten Beweise der Unterhaltungsmathematik: Die Hälfte aller Stellungen ist niemals lösbar.
Das Puzzle-Fieber von 1880
Das Puzzle stammt aus dem Bundesstaat New York der 1870er-Jahre; als Erfinder wird meist Noyes Chapman genannt, ein Postmeister in Canastota. Anfang 1880 löste es ein Fieber aus, zuerst überall in den Vereinigten Staaten und dann in Europa.
Sam Loyds 14-15
Der amerikanische Rätselautor Sam Loyd behauptete später, er habe das Puzzle erfunden, und erzählte von einem Preis von 1.000 Dollar für jeden, der es lösen könnte, wenn nur 14 und 15 vertauscht sind. Niemand gewann den Preis, und niemand konnte es: Diese Stellung ist unlösbar. Auch seine Behauptung, das Puzzle erfunden zu haben, stimmte nicht.
Warum die Hälfte der Stellungen unmöglich ist
Betrachten Sie die Lücke als sechzehnten Stein. Jeder Schiebezug vertauscht die Lücke mit einem Stein. Um in ihre Ecke zurückzukehren, muss die Lücke genauso oft nach links wie nach rechts und genauso oft nach oben wie nach unten wandern. Eine Stellung mit der Lücke in ihrer Ecke ist deshalb immer eine gerade Zahl von Vertauschungen von der gelösten Reihenfolge entfernt. 14 und 15 zu tauschen ist eine einzige Vertauschung, also ungerade, und so kann kein Schieben diese Stellung erreichen. 1879 bewiesen William Johnson und William Story, dass genau die Hälfte aller Anordnungen erreichbar ist.
Ein Test für jede Stellung
Zählen Sie die Paare von Steinen, die in falscher Reihenfolge stehen, wenn Sie den Rahmen Reihe für Reihe lesen. Auf einem 3×3- oder 5×5-Brett ist eine Stellung lösbar, wenn diese Zahl gerade ist. Auf einem 4×4-Brett addieren Sie die Reihe der Lücke, von unten gezählt: Die Stellung ist lösbar, wenn die Summe ungerade ist.
Lösen per Computer
Ein Computer kann mit A* nach einem Weg zurück suchen, einem Verfahren, das immer zuerst die vielversprechendste Stellung betrachtet. Es schätzt die noch nötigen Züge danach, wie weit jeder Stein von seinem Zielfeld entfernt ist, plus zwei Züge für jedes Paar von Steinen, die sich in ihrer eigenen Reihe oder Spalte gegenseitig blockieren. Die kürzeste Lösung zu finden wird auf großen Brettern sehr schwer. Die schwierigsten Stellungen des 15-Puzzles brauchen 80 Züge, und das 8-Puzzle braucht nie mehr als 31.
In PictorX ausprobieren
Öffnen Sie das 15-Puzzle und klicken Sie auf einen Stein, um ihn zu schieben. Mischen bringt die Steine in eine neue, lösbare Stellung, Lösen spielt eine Lösung Zug für Zug ab, und „Richtige Steine anzeigen“ färbt die Zahlen der Steine, die schon an ihrem Platz sind. Wählen Sie „Loyds 14-15“, um die unmögliche Stellung zu sehen, und wechseln Sie mit Größe zwischen 3×3, 4×4 und 5×5.
Häufig gestellte Fragen
Wer hat das 15-Puzzle erfunden?
Als Erfinder wird meist Noyes Chapman genannt, ein Postmeister in Canastota, New York, in den 1870er-Jahren. Sam Loyds spätere Behauptung, er sei der Erfinder, war falsch.
Ist das 14-15-Puzzle lösbar?
Nein. Die Stellung ist eine Vertauschung von der gelösten Reihenfolge entfernt, und jede Stellung, die das Schieben erreichen kann, ist eine gerade Zahl von Vertauschungen entfernt.
Wie viele Stellungen hat das 15-Puzzle?
Die 16 Felder lassen sich auf 20.922.789.888.000 Arten füllen. Genau die Hälfte davon, 10.461.394.944.000, ist durch Schieben erreichbar.
Lädt PictorX etwas hoch?
Nein. Das Puzzle wird auf einer Leinwand in Ihrem Browser gezeichnet. Speichern lädt ein PNG herunter, und Bearbeiten öffnet das Bild im PictorX-Editor.
Verwandte Tools
15-Puzzle
Spielen Sie das klassische 15-Puzzle, das Schiebepuzzle mit Holzsteinen, im Browser auf 3×3, 4×4 oder 5×5. Mischen Sie, schieben Sie ganze Reihen auf einmal, probieren Sie Sam Loyds unmögliches 14-15, oder sehen Sie zu, wie Lösen es zu Ende bringt.
Türme von Hanoi
Versetzen Sie im Browser einen Turm aus Scheiben über drei Stäbe. Immer nur eine Scheibe, nie eine größere auf eine kleinere. Die kürzeste Lösung hat 2ⁿ − 1 Züge.
Türme von Hanoi
Die Türme von Hanoi: drei Stäbe, immer nur eine Scheibe und nie eine größere auf einer kleineren. Die kürzeste Lösung hat 2ⁿ−1 Züge. Édouard Lucas stellte das Rätsel 1883 vor.
Springerproblem
Springen Sie mit dem Springer genau einmal auf jedes Feld des Bretts. Spielen Sie selbst mit Warnsdorff-Hinweisen, oder sehen Sie zu, wie Lösen eine offene oder geschlossene Tour vollendet. Speichern Sie den Weg als PNG.
Acht Damen
Setzen Sie acht Damen so auf ein Schachbrett, dass keine eine andere angreift. Probieren Sie es selbst, sehen Sie zu, wie die Backtracking-Suche Schritt für Schritt eine Lösung findet, und gehen Sie alle 92 Lösungen durch.
Langtons Ameise
Starten Sie Langtons Ameise im Browser. Sehen Sie Symmetrie, Chaos und die 104-Schritte-Autobahn, und probieren Sie dann mehrfarbige Regeln, mehrere Ameisen, ein Sechseckgitter und Turmiten.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
15-Puzzle spielen