Die App „Sort Puzzle“ prüft vor jeder Aufgabe mit dem Computer, dass sie lösbar ist. Auch der nächste Zug beim „Tipp“ ist der erste Zug der Lösung, die derselbe Löser gefunden hat. Hier erklären wir, wie dieser Löser funktioniert.

Stellungen und Züge verfolgen

Den Zustand des Felds (welche Farben in welchem Röhrchen stecken) nennen wir Stellung. Mit einem Zug entsteht eine andere Stellung. Verfolgt man die Züge von der Anfangsstellung aus und erreicht eine sortierte Stellung, ist der verfolgte Weg die Lösung.

Die einfachste Art zu suchen ist die Breitensuche: erst alle Stellungen, die mit 1 Zug erreichbar sind, dann alle mit 2 Zügen und so weiter. Sie findet immer eine Lösung mit der minimalen Zugzahl, aber bei vielen Farben sind es riesig viele Stellungen.

Die „Entfernung“ bis zur Sortierung schätzen

Deshalb zählt die App für jede Stellung eine Schätzung der Entfernung bis zur Sortierung und untersucht zuerst die Stellungen, die näher aussehen. Die Schätzung ist die Summe aus zwei Zahlen:

  1. Anzahl der Farbwechsel in den Röhrchen: wie oft sich die Farbe von unten nach oben ändert.
  2. Überlappung der Böden: Liegt dieselbe Farbe am Boden mehrerer Röhrchen, deren Anzahl minus 1.
123456

Bei diesem Feld gibt es in Röhrchen 1 zwei Wechsel, in Röhrchen 2 zwei, in Röhrchen 3 drei und in Röhrchen 4 drei, zusammen 10. Himmelblau liegt am Boden von Röhrchen 3 und 4, also ist die Überlappung 1. Die Schätzung ist 11. Bei einer sortierten Stellung gibt es weder Wechsel noch Überlappung, also ist die Schätzung 0.

Die Schätzung ist nie größer als die minimale Zugzahl

Diese Schätzung hat eine gute Eigenschaft: Mit einem Zug sinkt sie um höchstens 1.

  • Mit einmal Gießen sinkt die Zahl der Wechsel im Ausgangsröhrchen um höchstens 1. Das Ziel ist dieselbe Farbe oder ein leeres Röhrchen, also nehmen die Wechsel dort weder zu noch ab.
  • Dass ein Röhrchen leer wird und die Überlappung der Böden um 1 sinkt, passiert nur, wenn du den letzten zusammenhängenden Teil umfüllst, und dabei sinkt die Zahl der Wechsel nicht.

Ein Feld mit Schätzung 11 braucht also mindestens 11 Züge. Wir haben bei verschiedenen Feldern über 120.000 Züge geprüft, und kein einziger Zug senkte die Schätzung um 2 oder mehr. Die minimale Zugzahl des Felds oben beträgt genau 11 Züge.

Die gewichtete A*-Suche

Die App gibt jeder Stellung die Punktzahl „bisherige Zugzahl + 3 × Schätzung“ und untersucht zuerst die Stellungen mit der kleinsten Punktzahl. Das heißt gewichtete A*-Suche (gesprochen „A-Stern“).

  • Bei Gewicht 1 (die normale A*-Suche) ist die Schätzung eine Untergrenze der minimalen Zugzahl, also findest du immer eine Lösung mit der minimalen Zugzahl.
  • Bei Gewicht 3 werden Stellungen mit kleiner Schätzung konsequent zuerst untersucht, und die Lösung wird viel schneller gefunden. Dafür ist die Lösung manchmal etwas länger als die minimale Zugzahl.

Bei je 20 Aufgaben, erzeugt wie in der App, haben wir die Zahl der bis zur Sortierung untersuchten Stellungen und die Zugzahl der gefundenen Lösung verglichen (die Breitensuche bei ★3 haben wir nicht gezählt, weil es zu viele Stellungen sind).

★1 (4 Farben, 2 leer)Untersuchte StellungenZugzahl der Lösung
Breitensuche53711,8
A* (Gewicht 1)20311,8
A* (Gewicht 3)3911,9
★2 (6 Farben, 2 leer)Untersuchte StellungenZugzahl der Lösung
Breitensuche293418,1
A* (Gewicht 1)62218,1
A* (Gewicht 3)6418,8

Beides sind Durchschnitte über 20 Aufgaben. Mit Gewicht 3 fand die Suche die Lösung mit einem Bruchteil der Stellungen der Breitensuche, und die Zugzahl stieg nur wenig.

Kniffe, um weniger Züge zu untersuchen

Der Löser der App senkt die Zahl der untersuchten Stellungen noch durch weitere Kniffe.

  • Die Reihenfolge der Röhrchen wird nicht unterschieden: Sind die Inhalte gleich, gilt die Stellung als dieselbe, egal in welcher Reihenfolge die Röhrchen stehen.
  • Sinnlose Züge werden nicht untersucht: Züge, die ein Röhrchen mit nur einer Farbe in ein leeres Röhrchen setzen (die Form ändert sich nicht), und Züge in das zweite und jedes weitere leere Röhrchen (dieselbe Stellung wie beim ersten) fallen weg.
  • Gesucht wird nur mit „Gießen“-Zügen: Auch bei Aufgaben der Spielart „Stapeln“ wird geprüft, ob sie mit Gießen-Zügen lösbar sind (Der Unterschied zwischen „Gießen“ und „Stapeln“).
  • Es gibt eine Obergrenze: Findet der Löser auch nach 60.000 Stellungen nichts, gilt die Verteilung als „unbekannt“ und wird nicht verwendet.

Mit diesem Löser deckt die App beides ab: die „Prüfung der Lösbarkeit“ bei der Erzeugung der Aufgaben (So entstehen Aufgaben, die immer lösbar sind) und den „Tipp“ (So nutzt du den Tipp). Den Gedanken mit der Farbe am Boden erklärt auch Mit welcher Farbe fängst du an?.