Das 15er-Spiel ist nicht kompliziert zu lösen: Man kann es zeilenweise lösen und muss sich nur den Trick für den jeweils letzten Stein merken. Und in den letzten beiden Zeilen muss man etwas herumprobieren, bis es klappt.
Wenn man das auf die Dauer langweilig findet, kann man sich mit der Theorie hinter dem Geduldspiel beschäftigen und sich z.B. bemühen, das Geduldspiel möglichst schnell zu lösen. Schnell bedeutet entweder in möglichst kurzer Zeit oder mit möglichst wenigen Zügen. Wir wollen uns für die zweite Variante entscheiden und möglichst wenige Züge verwenden. Unter einem Zug wollen wir dabei verstehen, dass jeweils ein Nachbarstein auf das Leerfeld geschoben wird. Wenn wir gleichzeitig zwei oder drei Steine verschieben, dann zählt das als zwei bzw. drei Züge.
Wieviel Züge dieser Art benötigen wir, um ein 15er-Spiel zu lösen? Versuchen wir eine grobe Abschätzung dieser Zugzahl, nur für die obere Zeile: Um die 1 an ihren Platz zu bringen, brauchen wir im Mittel reichlich vier Bewegungen für die Ziffer 1, dazu muss jedesmal das Leerfeld an die richtige Position gebracht werden, was zwei bis vier weitere Züge kostet. Für die Ziffern 2 und 3 sind die Wege etwas kürzer. Insgesamt benötigt der menschliche Puzzlelöser rund 50 Züge für die oberste Reihe und noch einmal fast genausolange für die zweite Zeile. Auch YouTube-Erklärvideos benötigen meist so lange.
Was sagt eine Computer-Analyse? Da genau die Hälfte aller Startkombinationen lösbar ist, gibt es 16!/2 = 10.461.394.944.000 lösbare Start-Anordnungen (mit dem Leerfeld an einer beliebigen Position). Im Jahr 2005 haben Richard Korf und Peter Schulze [1] gezeigt, dass für jede Position maximal 80 Züge ausreichen und dass es genau 17 Startpositionen gibt, die diese maximale Zugzahl benötigen. Die mittlere Lösungslänge beträgt rund 53 Züge, das optimale Vorgehen führt also wesentlich schneller zum Ziel.
Wir können dem Computer auch bei der optimalen Lösung zusehen: Dazu gibt es den 15-Puzzle Optimal Solver von Herbert Kociemba. Mit dem Windows-Programm können Sie sich jedes lösbare 15er-Spiel lösen lassen, und die 17 Konfigurationen mit der längstmöglichen Lösung von 80 Zügen werden auf der Seite [2] ebenfalls angegeben.
Wenn wir dem Programm bei der Ausführung der Lösung zuschauen ("Apply Solution"), dann können wir oft beobachten, dass die optimale Strategie scheinbar so ähnlich funktioniert wie unser Vorgehen: Zuerst wird die obere Reihe gelöst, danach kommt die zweite Reihe dran. Dabei hat sich der Algorithmus allerdings schon einige Steine "zurechtgelegt", so dass die zweite Reihe recht schnell fertig ist. Und oft sind im gleichen Moment auch die dritte und vierte Reihe fertig: Die Position der Steine wurde auch gleich mit vorbereitet, so dass bei Fertigstellung der zweiten Reihe sich die dritte und vierte Reihe "wie von selbst" ergeben. Bei der Lösung der obersten Reihe ist also viel mehr passiert, als wir beim Zuschauen wahrgenommen haben!
Mehr Informationen:
[1] Richard E. Korf, Peter Schultze: Large-Scale Parallel Breadth-First Search. In: Proceedings of the 20th national conference on Artificial intelligence. 3, 2005, S. 1380-1385
