Introduction

A Flood-It-style puzzle asks for the shortest sequence of color changes that floods the entire board from the starting region, usually the top-left cell. For small boards, the cleanest exact approach is breadth-first search over board states. For large boards, the problem becomes computationally hard enough that heuristics are often more practical than exact search.

Model the Puzzle as a State Space

Each click changes the current flooded region to a new color, which may absorb adjacent cells of that color. So a state can be represented by:

• the current board coloring, or an equivalent reduced state
• the current flooded region implied by the top-left color
• the number of moves taken so far

For an exact minimum-click answer, breadth-first search is attractive because every move has equal cost. The first time BFS reaches a fully flooded board, that path length is optimal.

A Small Exact Solver in Python

For a small board, we can store the board as a tuple of tuples and apply a flood operation for each possible next color.

1from collections import deque
2
3board = (
4    (1, 2, 3),
5    (1, 1, 2),
6    (3, 2, 2),
7)
8
9def neighbors(r, c, rows, cols):
10    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
11        nr, nc = r + dr, c + dc
12        if 0 <= nr < rows and 0 <= nc < cols:
13            yield nr, nc
14
15def flood_fill_state(state, new_color):
16    rows, cols = len(state), len(state[0])
17    old_color = state[0][0]
18    if old_color == new_color:
19        return state
20
21    grid = [list(row) for row in state]
22    q = deque([(0, 0)])
23    region = {(0, 0)}
24
25    while q:
26        r, c = q.popleft()
27        for nr, nc in neighbors(r, c, rows, cols):
28            if (nr, nc) not in region and grid[nr][nc] == old_color:
29                region.add((nr, nc))
30                q.append((nr, nc))
31
32    for r, c in region:
33        grid[r][c] = new_color
34
35    expanded = True
36    while expanded:
37        expanded = False
38        for r, c in list(region):
39            for nr, nc in neighbors(r, c, rows, cols):
40                if (nr, nc) not in region and grid[nr][nc] == new_color:
41                    region.add((nr, nc))
42                    expanded = True
43
44    return tuple(tuple(row) for row in grid)
45
46def solved(state):
47    first = state[0][0]
48    return all(cell == first for row in state for cell in row)
49
50def min_clicks(start, colors):
51    q = deque([(start, 0)])
52    seen = {start}
53
54    while q:
55        state, dist = q.popleft()
56        if solved(state):
57            return dist
58
59        current = state[0][0]
60        for color in colors:
61            if color == current:
62                continue
63            nxt = flood_fill_state(state, color)
64            if nxt not in seen:
65                seen.add(nxt)
66                q.append((nxt, dist + 1))
67
68    return None
69
70print(min_clicks(board, colors={1, 2, 3}))

This is not optimized for huge boards, but it correctly expresses the shortest-path idea.

Why BFS Gives the Minimum

BFS explores all states at distance 0, then all states at distance 1, then distance 2, and so on. Because each click counts as one move, the first solved state found by BFS must use the minimum number of clicks.

That makes BFS the simplest exact answer for small inputs.

A depth-first search can still find a solution, but not necessarily the shortest one unless you add extra bookkeeping and pruning.

Why the Problem Gets Hard Fast

The board state space grows rapidly with board size and color count. Even though each move only changes one color, the number of reachable states can become large enough that naive exact search stops being practical.

That is why two very different statements can both be true:

• BFS is the right exact approach for small boards
• the general problem is hard enough that heuristics are common in larger variants

For larger puzzles, people often use:

• greedy lookahead heuristics
• A-star with state heuristics
• branch-and-bound pruning
• compact region-based state representations

Practical Heuristics

A simple heuristic is to choose the color that expands the flooded region the most on the next move. That does not guarantee the minimum, but it often performs reasonably on larger boards where exact BFS is too expensive.

The engineering tradeoff is straightforward:

• exact BFS for correctness on small inputs
• heuristics for scalability on larger inputs

Choose based on whether you need provable optimality or just a good solution quickly.

Common Pitfalls

• Using DFS and assuming the first solution found is minimal.
• Forgetting to track visited states, which makes search explode with repeated work.
• Representing the state too naively and paying a heavy performance cost.
• Expecting exact search to scale well on large boards with many colors.
• Confusing a good heuristic result with a guaranteed minimum number of clicks.

Summary

• Flood-It can be modeled as a shortest-path problem in a state graph.
• BFS gives the exact minimum number of clicks for small boards.
• Each move changes the flooded region to a new color and expands it.
• The search space grows quickly, so large boards often need heuristics.
• Use exact search when optimality matters and heuristics when scale matters more.