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 ZugzahlArten von Verteilungen
5 Züge3
6 Züge8
7 Züge124
8 Züge741
9 Züge3.523
10 Züge11.070
11 Züge21.321
12 Züge26.778
13 Züge19.271
14 Züge6.635
15 Züge197
16 Züge4

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)

123456
Zug 1: 3→5 (2)
123456
Zug 2: 1→3 (2)
123456
Zug 3: 4→5 (2)
123456
Zug 4: 2→4 (2)
123456
Zug 5: 1→2 (2)
123456
Sortiert

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)

123456

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
123456
Zug 1: 1→5
123456
Zug 2: 1→6
123456
Zug 3: 2→5
123456
Zug 4: 2→6
123456
Zug 5: 1→2
123456
Zug 6: 1→5
123456
Zug 7: 2→1 (2)
123456
Zug 8: 2→5
123456
Zug 9: 3→2
123456
Zug 10: 3→6
123456
Zug 11: 3→1
123456
Zug 12: 2→3
123456
Zug 13: 4→3
123456
Zug 14: 4→6
123456
Zug 15: 4→1
123456
Zug 16: 3→4 (3)
123456
Sortiert

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.

  1. Zähle die Farbwechsel innerhalb der Röhrchen.
  2. 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).