How the Color Lines Pathfinder Works: BFS Behind Every Move

In Color Lines you can't drop a marble just anywhere — it has to travel there along a clear path of empty squares, never stepping over another marble. That one constraint is what makes the game a puzzle rather than a shuffle, and it's enforced by a tiny, classic algorithm: breadth-first search (BFS). Here's exactly what happens between tapping a marble and seeing the reachable squares light up.

The board is a graph

Think of the 9×9 grid as 81 nodes. Two empty squares are connected if they're directly adjacent — up, down, left or right (no diagonals; a marble can't squeeze through a corner). A marble can move from its square to any empty square that is connected to it through a chain of other empty squares. "Can this marble reach that cell?" is therefore just the question "is there a path between these two nodes in the graph of empty squares?" — and BFS answers it efficiently.

Flood-filling from the marble

When you pick a marble up, the game runs a flood fill outward from its square. BFS keeps a queue of squares to visit and a record of which it has already seen. It pops a square, looks at its four neighbours, and any neighbour that is empty and unseen gets marked as reachable and added to the queue. Repeat until the queue is empty, and you've found every square the marble can get to — which is exactly the set the board highlights with little dots. Because each square is visited once, the whole sweep is effectively instant on an 81-cell board.

// reachable empty squares from a marble's cell
function reachable(start) {
  const seen = new Set([start]), queue = [start], out = [];
  while (queue.length) {
    const cur = queue.shift();
    for (const nb of neighbours(cur)) {       // up/down/left/right
      if (seen.has(nb) || occupied(nb)) continue;
      seen.add(nb); queue.push(nb); out.push(nb);
    }
  }
  return out;                            // the squares we light up
}

If the square you tap isn't in that returned set, there's simply no open corridor to it — which is why a move is sometimes refused even though the destination is empty. Tick Show moves and the game paints exactly this reachable set as dots, so you can see at a glance where each marble can travel.

Why BFS and not A*? We don't need the shortest path, just whether any path exists — and we need it for every empty square at once. A single flood fill answers all of those questions in one pass, so the more elaborate A* search would be wasted here. (For the animation, we then trace one concrete route back through the recorded steps.)

The same idea powers Smart Move

The Smart-Move hint reuses this machinery. For each of your marbles it runs the same flood fill to list every square it can reach, then simulates dropping the marble on each one. If a move completes a line of five or more, that's an immediate recommendation; otherwise it scores the move by the longest same-color run it would create and keeps the best. The result is the marble-and-destination pair the hint highlights — a move that either clears now or makes your strongest line longer. It's the same reasoning a strong human uses, just checked exhaustively in a few milliseconds.

That's the whole trick: model the board as a graph, flood-fill for reachability, and reuse it to evaluate moves. Want to see it in action? Pick up a marble and watch the dots — then read the strategy guide to turn those reachable squares into a high score.

See the pathfinder light up the board.

Play Color Lines →

How the Pathfinder Works: BFS Behind Every Move

The board is a graph

Flood-filling from the marble

The same idea powers Smart Move