Fünfzehnerspiel, 14  - 15 - Spiel, Boss Puzzle
Inhalt dieser Seite
Was ist das Fünfzehnerspiel?
Lösen des Puzzles
Programm
Etwas Mathematik
Schiebepuzzles
Achterspiel
Schiebepuzzles mit verschieden Klötzen
Zauberturm
Fünfzehnerspiel im Internet
Referenzen.
Zur Hauptseite  "Mathematische Basteleien"
Was ist das Fünfzehnerspiel
.. .. Das Fünfzehnerspiel besteht aus 15 Steinen mit den Nummern 1 bis 15. Sie liegen in einem quadratischen Rahmen. Die Steine kann man nicht herausnehmen und wegen eines freien Feldes nur verschieben. Zu Beginn sind die Zahlen gemischt (links). Es muss versucht werden, die Ordnung rechts durch Verschieben zu erreichen.  .. ..
Das Spiel heißt auch 14-15-Puzzle oder Boss Puzzle.

Lösen des Puzzles top
Zum Kennenlernen und zum Üben eines Lösungsweges hat sich ein kleines Modell bewährt, bei dem die Zahlen leicht bewegt werden können. Das lästige Verkanten der Steine beim Verschieben fällt weg.

Man zeichnet mit freier Hand auf ein Stück Pappe ein 4x4-Quadrat, schneidet passende 15 Kärtchen aus, beschriftet sie und legt mit ihnen das Quadrat aus (links).



Es gibt viele Möglichkeiten, das Puzzle zu lösen. 
...... Der übliche Weg besteht darin die Zahlen von 1 bis 15 nacheinander Zeile für Zeile an die richtige Stelle zu bringen. 

Eine vollständige Zeile sollte man nie zerstören, zumindest sollte man die Reihenfolge der Zahlen beibehalten.


......
Als erstes bringt man die 1 in die Ecke oben links.

Dazu muss man jeweils vor der 1 ein freies Feld schaffen, damit 1 vorrücken kann. Es ist günstig andere Zahlen mitzunehmen.

Dann folgen der Reihe nach die nächsten Zahlen...
......
Das ist ein Grundzug, der Kreis: Eine Zahl wird auf einem 2x2-Quadrat im Kreis bewegt. 

Hier wird gezeigt, wie man 7 an die richtige Stelle bringt. 
Dreht man im Gegensinn, erreicht auch 8 den richtigen Platz.

......
Manchmal steht für das Verschieben eines Steins kein 2x2-Quadrat zur Verfügung. 

Am Beispiel der 8 wird gezeigt, wie man eine (evtl. unvollständige) Zeile nach links und unten wegschiebt und dann eine Zahl in einem 2x2-Quadrat bewegen kann.

...... Wenn man die dritte Zeile gelöst hat, ist oft auch die vierte Zeile fertig.

Sonst sind die letzten drei Zahlen in einer falschen Reihenfolge (1). Dann ist es sinnvoll, die dritte Zeile nach links zu einem 2x2-Quadrat zu komprimieren (2), um die letzte Zeile dann umzuordnen.


...... Die Lösung hat mehr System, wenn man die Züge in einem 2x3-Rechteck beherrscht.

Man kann nämlich innerhalb eines 2x3 Rechtecks immer erreichen, dass zwei beliebige Zahlen (hier a und b) immer an ein Ende gebracht werden können, auch getauscht (Buch 09). 


Programme   top
...... Hat man das Puzzle gelöst, kann man sich als nächstes vornehmen, gemischte Steine mit einer möglichst kleinen Anzahl von Zügen wieder in die normale Reihenfolge zu bringen. Ich habe dazu ein kleines Programm in Visual Basic V3 geschrieben, das die Züge simuliert und zählt. Nach dem Start des Programms sind die Steine schon gemischt. 
 

Man kann das Programm mit  Download  in den eigenen Computer holen. Man braucht Vbrun300.dll.

Im Internet gibt es viele Umsetzungen des 15er-Spiels für den Computer. Man kann sie online oder offline spielen.
Es gibt aber auch Programme zum Herunterladen, die einen Algorithmus besitzen, um die kleinste Anzahl von Zügen herauszufinden. Das auf meiner Webseite angegebene Muster kann in 59 Zügen geordnet werden, wie das Programm von Ken'ichiro Takahashi (takaken) [URL unten] ermittelte: 9, 1, 6, 9, 1, 14, 12, 1, 2, 15, 11, 5, 1, 2, 15, 7, 9, 4, 10, 3, 13, 9, 3, 10, 8, 6, 14, 15, 4, 3, 7, 11, 5, 1, 2, 4, 3, 8, 6, 14, 15, 12, 4, 3, 8, 6, 14, 15, 12, 8, 6, 7, 11, 6, 7, 11, 10, 14, 15.

Die Berechnung von Lösungen mit möglichst wenigen Zügen ist ein schwieriges mathematisches Problem (12). So weiß man heute, dass nach höchstens 80 Zügen das 15 puzzle gelöst werden kann. (12).  Damit werden Computerprogramme mit der großen Anzahl von Ausgangsstellungen fertig. 



 
 

Etwas Mathematik  top
Man betrachte der Einfachheit halber ein 2x2-Quadrat, in dem nur 3 Steine ausgelegt sind. Das freie Feld sei immer unten rechts.
...... Unter dieser Bedingung gibt es drei Möglichkeiten, die Position der Steine durch Verschieben zu ändern. Sie können geschrieben werden als 123, 312 und 231. 
...... Aus drei Zahlen kann man 3!=6 Vertauschungen (Permutationen) bilden. Es gibt noch die Möglichkeiten 132, 213 und 321. Sie führen zu nebenstehenden Stellungen der Steine, die bei einem Puzzle aber nicht angenommen werden.
Wie unterscheiden sich die Permutationen? 
Man bildet alle Paare in den Permutationen, bei denen eine größere Zahl vor einer kleineren liegt ('Inversion'). 
 
Permutation:

123
312
231

Alle Paare:

12 13 23
31 32 12
23 21 31

Inversionen:

kein Paar
2 Paare: 31 32
2 Paare: 21 31

Da die Anzahl der Paare rechts immer gerade ist, heißen diese Permutationen gerade. (Die geraden Permutationen bilden die alternierende Untergruppe der Ordnung 3 der symmetrischen Gruppe. Die vorgegebene Menge muss eine Grundordnung haben.)

Die anderen Permutationen sind ungerade:
 
Permutation:

132
213
321

Alle Paare:

13 12 32
21 23 13
32 31 21

Inversionen:

1 Paar: 32
1 Paar: 21
3 Paare: 32 31 21

top

Diesen Sachverhalt kann man auf das 4x4-Quadrat übertragen.
Es gibt 15 Steine, folglich gibt es 15! = 1 307 674 368 000 Permutationen. Nur die Hälfte der Permutationen ist gerade und wird als Position angenommen. 
Zählt man das leere Feld mit, gibt es 16! = 20 922 789 888 000 Möglichkeiten. 


Schiebepuzzles  top
..........
In Italien habe ich ein unlösbares Fünfzehnerspiel entdeckt, bei dem in der letzten Zeile 14 und 15 vertauscht sind. 
Dieses Puzzle ist jedoch unlösbar. Wegen des Paares (15,14) ist die Permutation (1,2,...,13,15,14) ungerade und lässt sich nicht durch Verschieben in die gerade Permutation (1,2,...,13,14,15)  verwandeln. 


Ich hatte gedacht, dass es Absicht ist das Puzzle unlösbar zu machen. Nun schrieb mir Martin Beckenkamp im August 2004, dass er ein Handy mit installiertem 15er-Puzzle besitzt und dass es "gelöst" anzeigt, wenn die Zahlen in die Reihenfolge 
01 02 03 __
04 05 06 07
08 09 10 11
12 13 14 15
gebracht würden. Das entspricht der Anordnung des italienischen Puzzles oben, bei dem 14 und 15 vertauscht sind.

Die meisten Fünfzehnerspiele, die man heute kaufen kann, tragen statt Zahlen Bildteile. Man muss die Bilder finden. 
Es folgen zwei Beispiele, Reklame von Mc Donald's  und von Kaiser Bier.
.........

Übrigens kann man bei Puzzles mit Rahmen die 15 Steine mit etwas Gewalt herausnehmen. Man muss dazu die Mitte anheben.

Achterspiel   top
....... Problem: 
Man sollte mit möglichst wenigen Zügen die rückwärts laufenden Zahlen links in die natürliche Reihenfolge 1 bis 8  mit einer Leerstelle unten rechts bringen. 
Das Problem stammt von Henry Ernest Dudeney. Martin Gardner stellte den Lesern der amerikanischen Zeitschrift  "Scientific American" diese Aufgabe. Zahlreiche Lösungen wurden eingesandt. 
......
......
...... Ergebnis: Man benötigt nur 30 Züge. - Es gibt 10 Lösungen. Zwei Lösungen (links und in der Mitte) bilden Paare und sind zueinander revers. Das erkennt man, wenn man die Züge der zweiten Lösung rückwärts laufen lässt (rechts).


......
Das entsprechende 16er-Spiel ist unlösbar. 
Vertauscht man aber 1 und 2, so wird das Puzzle lösbar. Man schafft es in 70 Zügen: 2, 5, 9, 13, 14, 10, 11, 7, 3, 1, 6, 11, 10, 15, 7 ,3, 1, 6, 5, 9, 13, 14, 15, 7, 3, 1, 6, 5, 9, 13, 14, 15, 12, 8, 4, 14, 15, 12, 8, 4, 12, 8, 7, 3, 1, 6, 5, 9, 13, 15, 14, 2, 15, 14, 2, 12, 8, 2, 11, 10, 2, 7, 3, 2, 6, 5, 9, 13, 14, 15. 

Schiebepuzzles mit verschieden Klötzen   top
...... Im Fahrwasser des Fünfzehnerspiels wurden zahlreiche Puzzles entwickelt, bei denen unterschiedlich große Klötze verschoben werden mussten. 

Bei diesem Spiel soll man den quadratischen Klotz oben links mit möglichst wenigen Zügen nach unten links bringen.

Man braucht mindestens 59 Züge (Lösung in Buch 07)

Das Schiebepuzzle heißt Dad's Puzzle.


Zauberturm (Englisch: Tower of Babylon) top

Im Fahrwasser des Zauberwürfels (Rubik's Cube) kam in den achtziger Jahren ein Puzzle auf den Markt, das im Prinzip ein Schiebepuzzle ist.
Man muss 36 Kugeln so ordnen, dass in einer Spalte 6 Kugeln der gleichen Farbe liegen und dass sie darüber hinaus noch nach  Farbtönen geordnet sind. Man kann sie leicht horizontal verschieben, da sich jeweils sechs Kugeln auf  einem Kreisring bewegen lassen. Die Bewegung in der Vertikalen klappt nur mit einem Trick: Man kann unten eine Kugel in die Mitte drücken (linker Pfeil), dann rutschen die Kugeln von oben nach und lassen eine Lücke (rechter Pfeil). Hält man den Turm horizontal, so kann man die Lücke an jede Stelle bringen und so Kugeln verschieben. Das reicht zum Lösen. Wegen der Vielzahl der Kugeln ist das eine stupide Tätigkeit. 

Da mein Turm oben eine Schraube hat, kann ich den Turm leicht auseinandernehmen, die Kugeln ordnen und den Turm dann zusammensetzen ;-). Leider sind dabei offenbar die "Kugellager" zwischen den Ringen verloren gegangen :-(.


Fünfzehnerspiel im Internet    top

Deutsch

tan-gram
boss

Wikipedia
15-Puzzle



English

Alexander Bogomolny (cut-the-knot)
Sam Loyd's FifteenHistory, Lucky7, Happy8, Slider

Don Taylor
The 14-15 Puzzle

Ed Pegg Jr. (MAA online)
sliding-block Puzzles
 
gamedesign.jp
Sliding Block Puzzle online

Harry Broeders
15puzzle

Herbert Kociemba
Fifteen Puzzle Optimal Solver

Jaap Scherphuis
14-15 puzzle / Boss puzzle

Jerry Slocum & Dic Sonneveld
The 15 Puzzle

Jim Loy 
The 15 Puzzle (The possible puzzle; The impossible puzzle) 

Karl Hörnell's Applet Center
The 15 Puzzle

Nick Baxter
Sliding Block Home Page

Ken'ichiro Takahashi (takaken) 
15Puzzle Optimal Solver

Wikipedia
Fifteen puzzle, Sliding puzzle


Referenzen   top
(00) Hermann Schubert: Mathematische Mußestunden, Walter de Gruyter Verlag Berlin 1941 (1.Auflage 1897)
(01) W.Ahrens: Mathematische Unterhaltungen und Spiele, Leipzig 1918
(02) G.Kowalewski: Mathematica delectans, Band 1 , Leipzig 1921
(03) G.Kowalewski: Alte und neue Spiele, Leipzig 1930 (Nachdruck: Martin Sändig, Walluf 1978 (ISBN 3-500-19830-9)
(04) Martin Gardner: Mathematical Puzzles & Diversions, New York 1959 
(05) Walter Lietzmann: Lustiges und Merkwürdiges von Zahlen und Formen, Göttingen 1961
(06) Bruno Kerst: Mathematische Spiele, Berlin 1933 (Nachdruck: Martin Sändig, Wiesbaden 1968)
(07) Martin Gardner: Mathematisches Labyrinth, Braunschweig 1979 (ISBN 3-528-08402-2)
(08) Michael Mrowka: Zauberturm, Teufelstonne und Magische Pyramide, Niedernhausen/Ts.1981 (ISBN 3-8068-0606-3)
(09) Monika Dewess und Günter Dewess: Summa Summarum, Thun;Frankfurt am Main, 1986 (ISBN 3-87144-898-2)
(10) Johannes Lehmann (Hrsg.): Rechnen und Raten , Köln 1986 (ISBN 3-7614-0930-3). 
(11) L. Edward Hordern: Sliding Piece Puzzles, 249pp, hb, Oxford, England, 1993, Oxford University Press
(12) F. R. W. Karlemo and P. R. J. Östergård : On sliding block puzzles, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
(13) Jerry Slocum & Dic Sonneveld: The 15 Puzzle, Slocum Puzzle Foundation, 257 South Palm Drive, Beverly Hills, CA 90212, 2006


Feedback: Emailadresse auf meiner Hauptseite

Diese Seite ist auch in Englisch vorhanden.

URL meiner Homepage:
http://www.mathematische-basteleien.de/

©  2000 Jürgen Köller

top