ChromaOracle findet die kürzestmögliche Lösung für jedes Farbsortier-Rätsel mit einem Algorithmus namens Breitensuche oder BFS. Anstatt zu raten oder Heuristiken zu folgen, erkundet der Solver systematisch jede mögliche Zugsequenz, kürzeste Sequenzen zuerst, bis er eine findet, die das Rätsel löst. Dies garantiert, dass die zurückgegebene Lösung die wenigstmöglichen Züge verwendet.
Das Rätsel als Suchproblem
Jedes Farbsortier-Rätsel — egal ob Water Sort, Ball Sort oder eine andere Variante — kann als Suchproblem beschrieben werden. Das Rätselbrett zu jedem Zeitpunkt ist ein "Zustand": ein spezifisches Arrangement von Farben über alle Reagenzgläser. Jeder gültige Guss oder Zug transformiert einen Zustand in einen anderen.
Was ist Breitensuche?
Breitensuche ist eine Methode, diese Karte von Zuständen in einer sehr spezifischen Reihenfolge zu erkunden: sie prüft alle Zustände, die einen Zug vom Start entfernt sind, dann alle Zustände, die zwei Züge entfernt sind, dann drei und so weiter.
Dieser geschichtete Ansatz garantiert die Optimalität. Da BFS alle Fünf-Zug-Lösungen vor jeder Sechs-Zug-Lösung erkundet, hat es notwendigerweise den kürzesten Pfad gefunden, wenn es das erste Mal den Zielzustand erreicht.
Der Prozess funktioniert so:
- Beginne mit dem anfänglichen Brettzustand.
- Generiere jeden gültigen Zug aus diesem Zustand.
- Prüfe, ob einer dieser neuen Zustände der gelöste Zustand ist.
- Wenn nicht, füge alle neuen Zustände zur Warteschlange hinzu und wiederhole.
- Setze fort, bis das Ziel gefunden ist oder alle erreichbaren Zustände erkundet wurden.
Zustandsraum-Repräsentation
ChromaOracle stellt jedes Reagenzglas als Stapel von Farben dar und das gesamte Brett als Sammlung dieser Stapel. Um zu vermeiden, denselben Zustand zweimal zu erkunden, generiert der Solver einen kanonischen Schlüssel für jeden Zustand.
Warum BFS die kürzeste Lösung garantiert
Die Garantie kommt von der Erkundungsreihenfolge. BFS verarbeitet Zustände streng nach ihrer Entfernung vom Start. Daher hat der Solver, wenn er das erste Mal den Zielzustand erreicht, ihn über einen Pfad der Länge N erreicht, und kein Pfad mit einer Länge kleiner als N existiert.
BFS gegen DFS
ChromaOracle unterstützt auch Tiefensuche (DFS) als Alternative. Die Trade-offs sind:
- BFS findet die kürzeste Lösung, verwendet aber mehr Speicher.
- DFS findet eine Lösung in vielen Fällen schneller und verwendet weniger Speicher, aber die Lösung ist möglicherweise nicht die kürzeste.
Wie der Mystery-Modus funktioniert
ChromaOracles Mystery-Modus, entwickelt für Rätsel mit versteckten oder unbekannten Farben, behandelt dies durch Permutationsanalyse:
- Der Solver identifiziert alle als unbekannt markierten Positionen.
- Er generiert jede mögliche Zuweisung von Farben zu diesen Positionen.
- Er löst jedes resultierende Rätsel unabhängig mit BFS.
- Er analysiert alle Lösungssätze, um Züge zu finden, die unabhängig davon sicher sind.
Performance und praktische Grenzen
Der Zustandsraum eines Farbsortier-Rätsels wächst exponentiell mit der Anzahl der Reagenzgläser und Farben. ChromaOracle läuft vollständig im Browser mit TypeScript. Für die meisten Rätsel — bis etwa zehn Farben — ist BFS in unter einer Sekunde fertig.
Häufig gestellte Fragen
Warum dauert ChromaOracle bei bestimmten Rätseln länger?
Die Lösungszeit hängt von der Größe des Zustandsraums ab.
Kann der Solver fehlschlagen, eine Lösung zu finden?
Wenn eine Lösung existiert, wird BFS sie immer finden. Wenn BFS ohne Lösung abschließt, ist das Rätsel mathematisch unlösbar.
Ist die BFS-Lösung immer die bestmögliche?
Ja. BFS garantiert die kürzeste Lösung in Bezug auf die Anzahl der Züge.
Wie weiß der Mystery-Modus, welche Züge sicher sind?
Der Mystery-Modus löst das Rätsel für jede mögliche Zuweisung versteckter Farben und vergleicht dann alle Lösungen. Ein Zug wird nur dann als sicher markiert, wenn er in der optimalen Lösung für jede einzelne Möglichkeit erscheint.