ChromaOracle finds the shortest possible solution to any color sort puzzle by using an algorithm called breadth-first search, or BFS. Instead of guessing or following heuristics, the solver systematically explores every possible sequence of moves, shortest sequences first, until it finds one that solves the puzzle. This guarantees that the solution it returns uses the fewest moves possible. Here is how it works, explained for both curious players and technically minded readers.
The Puzzle as a Search Problem
Every color sort puzzle — whether Water Sort, Ball Sort, or any variant — can be described as a search problem. The puzzle board at any moment is a "state": a specific arrangement of colors across all tubes. Each valid pour or move transforms one state into another. Solving the puzzle means finding a sequence of moves that transforms the starting state into the goal state, where every tube holds a single color or is empty.
Picture it as a map. Each intersection is a state. Each road between intersections is a move. The starting state is where you are now. The goal state is your destination. The solver's job is to find the shortest route.
What Is Breadth-First Search?
Breadth-first search is a method for exploring this map of states in a very specific order: it checks all states that are one move away from the start, then all states that are two moves away, then three, and so on. It fans out evenly in all directions, layer by layer.
This layered approach is what guarantees optimality. Because BFS explores all five-move solutions before any six-move solution, the first time it reaches the goal state, it has necessarily found the shortest path. There is no shorter path it could have missed because it already checked every shorter possibility.
The process works like this:
- Start with the initial board state.
- Generate every valid move from that state. Each move produces a new board state.
- Check whether any of those new states is the solved state. If yes, return the move sequence.
- If not, add all the new states to a queue and repeat from step two with the next state in the queue.
- Continue until the goal is found or all reachable states have been explored.
If the queue empties without finding a solution, the puzzle is unsolvable — and the solver reports that immediately.
State Space Representation
For BFS to work efficiently, the solver needs a way to represent each board state compactly and to detect when it has already visited a state. ChromaOracle represents each tube as a stack of colors, and the full board as a collection of these stacks.
To avoid exploring the same state twice — which would waste time and memory — the solver generates a canonical key for each state. This key is a normalized string representation of the board that treats identical arrangements as the same state regardless of tube ordering. If two boards have the same tubes with the same contents, just in a different left-to-right order, they produce the same key and are recognized as duplicates.
This deduplication is critical. Without it, the solver would revisit the same positions millions of times, making it impractically slow. With it, the solver only processes each unique state once.
Why BFS Guarantees the Shortest Solution
The guarantee comes from the order of exploration. BFS processes states strictly by their distance from the start, measured in number of moves. Every state at distance N is processed before any state at distance N+1. Therefore, the first time the solver reaches the goal state, it has arrived via a path of length N, and no path of length less than N exists — because all shorter paths were already fully explored.
This is a mathematical property of the algorithm, not a heuristic or approximation. The solution BFS returns is provably optimal.
BFS Versus DFS
ChromaOracle also supports depth-first search (DFS) as an alternative algorithm. DFS works differently: instead of exploring layer by layer, it follows a single path as deep as possible before backtracking.
The tradeoffs are:
- BFS finds the shortest solution but uses more memory, because it must store all states at the current depth level simultaneously.
- DFS finds a solution faster in many cases and uses less memory, but the solution may not be the shortest. It returns the first valid path it stumbles upon, which might be much longer than necessary.
For most players, BFS is the right choice — you want the fewest moves. DFS is useful when you just want any solution quickly, or when the puzzle is so large that BFS runs out of memory.
How Mystery Mode Works
One of ChromaOracle's most distinctive features is Mystery Mode, designed for puzzles that contain hidden or unknown colors. In many puzzle games, some tube slots display a question mark instead of a color, and the actual color is only revealed when that layer becomes the top of its tube.
ChromaOracle handles this through permutation analysis:
- The solver identifies all positions marked as unknown.
- It generates every possible assignment of colors to those positions that is consistent with the puzzle's rules — each color must appear the correct number of times.
- It solves every resulting puzzle independently using BFS.
- It analyzes all solution sets to find moves that are safe regardless of what the hidden colors turn out to be.
This is called finding the "common prefix" — the longest sequence of moves that appears at the start of every solution across all possible color assignments. These moves are guaranteed to be correct no matter what the unknowns reveal.
This approach transforms a problem of uncertainty into a problem of exhaustive analysis. Instead of guessing, the solver considers every possibility and tells you exactly which moves are risk-free.
Performance and Practical Limits
The state space of a color sort puzzle grows exponentially with the number of tubes and colors. A simple puzzle with five colors might have a few thousand reachable states. A complex puzzle with twelve colors can have millions.
ChromaOracle runs entirely in your browser using TypeScript. For most puzzles — up to about ten colors — BFS completes in under a second. Larger puzzles may take a few seconds. Extremely large configurations might exceed browser memory limits, at which point DFS becomes the better option.
The solver is a pure computation with no network calls. Your puzzle data never leaves your device, and solving speed depends only on your device's processing power.
The Engine Architecture
For readers interested in the technical implementation, ChromaOracle's solver engine is organized into focused modules:
- Container — represents a single tube as a stack of colors, handling push, pop, and top-color queries.
- Collection — represents the full board, generates all valid moves from the current state, and produces canonical keys for deduplication.
- Search — implements both BFS and DFS, managing the queue or stack and the visited-state set.
- Strategy — coordinates multi-solution analysis, finding all solutions and computing common prefixes for Mystery Mode.
- Validation — checks that a puzzle configuration is well-formed before solving begins.
The engine has no framework dependencies. It is pure TypeScript, fully testable in isolation, and portable to any JavaScript runtime.
Frequently Asked Questions
Why does ChromaOracle sometimes take longer on certain puzzles?
Solving time depends on the size of the state space, which is determined by the number of colors, tubes, and empty slots. More colors and fewer empty tubes mean more possible states to explore. A twelve-color puzzle with one empty tube has a vastly larger state space than a four-color puzzle with three empty tubes.
Can the solver fail to find a solution?
If a solution exists, BFS will always find it. If BFS completes without finding a solution, the puzzle is mathematically unsolvable — no sequence of valid moves can reach the goal state. ChromaOracle reports this clearly so you know the puzzle is impossible, not just difficult.
Is the BFS solution always the best possible?
Yes. BFS guarantees the shortest solution in terms of number of moves. There is no valid solution with fewer moves than the one BFS returns. This is a mathematical property of the algorithm.
How does Mystery Mode know which moves are safe?
Mystery Mode solves the puzzle for every possible assignment of hidden colors, then compares all the solutions. A move is marked as safe only if it appears in the optimal solution for every single possibility. This means the move is correct no matter what the hidden colors turn out to be.