Wie viele Züge braucht man mindestens, um Sort Puzzle zu lösen? Bei ★1 (4 Farben, 2 leer) der App „Sort Puzzle“ lassen sich alle Verteilungen prüfen. Wir haben für alle Verteilungen mit „Gießen“-Zügen die minimale Zugzahl gezählt.
So haben wir geprüft
- Wir prüfen nur „faire Verteilungen“ ohne Röhrchen mit 3 oder mehr gleichen Farben hintereinander (die App gibt nur solche aus).
- Verteilungen, die sich nur durch die Reihenfolge der Röhrchen oder eine andere Färbung unterscheiden, zählen wir als gleich. Dann bleiben 89.675 Arten (Auf wie viele Arten kann ausgeteilt werden?).
- Für jede Verteilung erweitern wir alle Stellungen nach 1 Zug, nach 2 Zügen und so weiter und ermitteln die Zugzahl, bei der zum ersten Mal alles sortiert ist (Breitensuche).
Verteilung der minimalen Zugzahl
| Minimale Zugzahl | Arten von Verteilungen |
|---|---|
| 5 Züge | 3 |
| 6 Züge | 8 |
| 7 Züge | 124 |
| 8 Züge | 741 |
| 9 Züge | 3.523 |
| 10 Züge | 11.070 |
| 11 Züge | 21.321 |
| 12 Züge | 26.778 |
| 13 Züge | 19.271 |
| 14 Züge | 6.635 |
| 15 Züge | 197 |
| 16 Züge | 4 |
Am häufigsten sind 12 Züge, und 10 bis 13 Züge machen mehr als 80 % aus. Nur 3 Arten sind in 5 Zügen lösbar, und nur 4 Arten brauchen 16 Züge.
(Die Zahlen hier sind „Arten“. Die Wahrscheinlichkeit, dass die App eine bestimmte Art tatsächlich austeilt, unterscheidet sich von Art zu Art ein wenig.)
Das kürzeste Feld (5 Züge)
In jedem Röhrchen liegen zwei gleiche Farben übereinander. Mit den zwei leeren Röhrchen ist es in 5 Zügen sortiert.
Das Feld mit den meisten Zügen (16 Züge)
Röhrchen 1 und 2 sowie Röhrchen 3 und 4 sind genau gleich aufgebaut. In jedem Röhrchen sind alle benachbarten Farben verschieden, und Rot und Hellgrün liegen jeweils am Boden von zwei Röhrchen.
Die Lösung in 16 Zügen ansehen
Die Untergrenze finden
Die minimale Zugzahl musst du nicht durch Ausprobieren aller Züge finden, denn eine Untergrenze (eine Zahl, die nicht unterschritten wird) siehst du schon am Feld.
- Zähle die Farbwechsel innerhalb der Röhrchen.
- Liegt dieselbe Farbe am Boden mehrerer Röhrchen, addiere „diese Anzahl minus 1“.
Diese Summe sinkt mit jedem Gießen um höchstens 1 und ist deshalb nie größer als die minimale Zugzahl (Der Computer löst das Puzzle).
- Feld mit 5 Zügen: 4 Wechsel, Rot liegt am Boden von 2 Röhrchen, also plus 1, die Untergrenze ist 5. Das ist genau die minimale Zugzahl.
- Feld mit 16 Zügen: 12 Wechsel, Rot und Hellgrün liegen jeweils am Boden von 2 Röhrchen, also plus 2, die Untergrenze ist 14. Tatsächlich braucht man 16 Züge.
Bei den 89.675 Arten stimmten Untergrenze und minimale Zugzahl bei 38.571 Arten (etwa 43 %) genau überein. Bei den übrigen braucht man mehr als die Untergrenze.
Bei größeren Feldern
Mit mehr Farben gibt es zu viele Verteilungen, um alle zu prüfen. Bei je 20 Aufgaben, erzeugt wie in der App, lag die durchschnittliche minimale Zugzahl bei ★1 bei 11,8 Zügen und bei ★2 (6 Farben) bei 18,1 Zügen. Ab ★3 dauert es schon bei einer einzigen Aufgabe lange, die minimale Zugzahl zu finden.
Der „Tipp“ der App zeigt nicht die minimale Zugzahl, sondern eine Lösung, die schnell gefunden wird. Willst du die minimale Zugzahl erreichen, überlege dir mit der Untergrenze als Anhaltspunkt selbst eine Zugfolge (So nutzt du den Tipp).
