Die Aufgaben der App „Sort Puzzle“ sind nicht vorbereitet, sondern werden bei jedem Spiel direkt erzeugt. Trotzdem wird jede Aufgabe erst ausgegeben, nachdem geprüft wurde, dass sie lösbar ist. Hier zeigen wir, wie das geht.
Die Schritte
- Farben wählen: Aus 10 Farben werden so viele gewählt, wie der Schwierigkeitsgrad verlangt (bei ★1 sind es 4).
- Mischen und austeilen: Von den gewählten Farben werden je 4 Teile gesammelt und gemischt und mit je 4 in die Röhrchen mit Farben gefüllt. Die leeren Röhrchen stehen rechts daneben.
- Fast sortierte Röhrchen verwerfen: Gibt es ein Röhrchen mit 3 oder mehr gleichen Farben hintereinander, wird diese Verteilung nicht verwendet. Ein Röhrchen, das von Anfang an fast sortiert ist, wäre langweilig.
- Lösbarkeit prüfen: Der Löser des Computers sucht eine Zugfolge bis zur Sortierung. Findet er keine, wird diese Verteilung nicht verwendet.
- Bedingung für Fallen prüfen: Ab ★3 wird geprüft, ob es eine Falle gibt, bei der du feststeckst, wenn du immer den auf den ersten Blick guten Zug wählst, und es wird neu ausgeteilt, bis die Bedingung des Schwierigkeitsgrads erfüllt ist (Aufgaben mit Fallen).
Bei jeder Aufgabe wiederholt die App diese Schritte, bis sie eine passende Verteilung gefunden hat. Auch bei ★5 dauert es für eine Aufgabe höchstens einige Dutzend Millisekunden.
Wie viele zufällig ausgeteilte Felder sind lösbar?
Wie viele Verteilungen werden in Schritt 4 verworfen? Wir haben auf dieselbe Weise wie die App ausgeteilt und bei den „Verteilungen ohne Röhrchen mit 3 oder mehr gleichen Farben hintereinander“ (faire Verteilungen) alle auf Lösbarkeit geprüft.
| Schwierigkeit | Faire Verteilungen | Lösbare Verteilungen |
|---|---|---|
| ★1 (4 Farben, 2 leer) | 416 | 416 |
| ★2 (6 Farben, 2 leer) | 431 | 431 |
| ★3 (8 Farben, 2 leer) | 453 | 453 |
| ★4 (10 Farben, 2 leer) | 460 | 460 |
| ★5 (9 Farben, 1 leer) | 4539 | 29 |
Bei ★1 bis ★4 mit zwei leeren Röhrchen war jede der gezählten fairen Verteilungen lösbar. Bei ★5 mit nur einem leeren Röhrchen waren dagegen von 4539 nur 29 (0,64 %) lösbar. Die übrigen lassen sich auf keine Weise sortieren.
Mit einem leeren Röhrchen wird es plötzlich unlösbar
Wir haben auch gezählt, wie sich der Anteil lösbarer Verteilungen mit der Farbanzahl ändert, wenn es nur ein leeres Röhrchen gibt.
| Anzahl Farben (1 leer) | Anteil lösbar |
|---|---|
| 3 Farben | 72,7 % |
| 4 Farben | 44,9 % |
| 5 Farben | 26,3 % |
| 6 Farben | 14,0 % |
| 7 Farben | 6,0 % |
| 8 Farben | 2,3 % |
| 9 Farben | 0,64 % |
Mit jeder zusätzlichen Farbe halbiert sich der Anteil etwa, und bei vielen Farben sinkt er noch schneller. Wahrscheinlich liegt das daran, dass du mit nur einem leeren Röhrchen den ersten Zug zwangsläufig dorthin machen musst und danach nur wenige Wege übrig bleiben (So löst du ★5 (ein leeres Röhrchen)).
Der Kniff bei ★5
Bei ★5 sind lösbare Verteilungen selten, deshalb teilt die App bis zu 400-mal neu aus. Findet sie auch dann keine, wechselt sie zu einer anderen Erzeugungsart.
- Ein sortiertes Feld durcheinanderbringen: Man beginnt mit einem sortierten Feld und bringt es mit umgekehrten Zügen zufällig durcheinander. Macht man die umgekehrten Züge rückgängig, ist es sicher wieder sortiert, also ist die Lösbarkeit garantiert.
Als wir 500 ★5-Aufgaben wie in der App erzeugt haben, waren 18 davon solche „durcheinandergebrachten Felder“. Bei einem durcheinandergebrachten Feld sind die Röhrchen manchmal nicht mit je 4 Teilen gefüllt.
Aus demselben Startwert entsteht dieselbe Aufgabe
Der Zufallsgenerator für die Aufgaben liefert immer dieselbe Folge, wenn du eine Zahl als „Startwert“ festlegst (SplitMix64). Aus demselben Startwert entsteht dieselbe Aufgabe. Auch das Spielfeld unter Wo du Sort Puzzle spielen kannst auf dieser Seite erzeugt Aufgaben nach denselben Schritten wie die App.
Wie der Löser funktioniert, der die Lösbarkeit prüft, steht unter Der Computer löst das Puzzle.
