Introduction

Flood-It is the kind of game you download to kill five minutes and end up replaying for an hour. The board is a grid of colored squares. You always control the top-left corner, and on each turn you pick a color — the whole connected blob touching your corner instantly floods to that color, swallowing any neighbors that match. Keep going until the entire board is a single color. The only catch: do it in as few moves as possible.

Choosing the next color feels harmless. Pick the color that grabs the biggest region? Pick the color you have the most of? Both sound reasonable, and both can be beaten. The truly optimal sequence is often surprising, and the gap between a greedy guess and the perfect play is exactly where the difficulty lives.

That gap is not just a matter of practice. Once the board uses three or more colors, finding the shortest sequence is one of the hardest kinds of problem we know how to describe — the same wall that algorithms hit again and again across computer science.

Try It

Here is a small Flood-It board. You always control the top-left cell. Click a color below to flood your corner region into it; the connected blob touching your corner takes that color and absorbs matching neighbors. Win by making every cell the same color in as few moves as you can.

<p class="hint">You control the <b>top-left</b> cell. Click a color to flood your corner region into it — the connected blob touching the corner takes that color and swallows matching neighbors. Make the <b>whole board one color</b> in as few moves as you can, then compare against the optimal solver.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Moves: 0</div>
<div class="palette" id="palette"></div>
<div class="btns">
  <button id="optimal" type="button">Show optimal</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(5, 46px); gap: 3px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; border-radius: 6px; border: 1px solid rgba(0,0,0,.12); }
.cell.corner { box-shadow: inset 0 0 0 3px #1d3557; }
.c0 { background: #e63946; } .c1 { background: #2a9d8f; } .c2 { background: #f4a261; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.palette { display: flex; gap: .5rem; margin: .3rem 0 .6rem; }
.swatch { width: 40px; height: 40px; border-radius: 8px; cursor: pointer;
          border: 2px solid rgba(0,0,0,.15); transition: transform .08s; }
.swatch:hover { transform: scale(1.08); }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Flood-It: control the top-left corner; each move recolors the whole connected
// region touching the corner. Win when the board is one color, in as few moves
// as possible. Replaying/verifying a sequence is cheap; finding the SHORTEST one
// is NP-hard for >= 3 colors (Arthur, Clifford, Jalsenius, Montanaro & Sach, 2010).
// The "Show optimal" button does an exact breadth-first search over board states.
const N = 5, COLORS = 3;
const PALETTE = ['#e63946', '#2a9d8f', '#f4a261'];
// Fixed start board (verified: optimal = 5 moves, greedy = 6).
const START = [[2,0,2,0,1],[1,0,1,0,1],[2,2,1,2,0],[1,2,2,1,0],[1,0,1,1,1]];

let board, moves;
const clone = b => b.map(r => r.slice());

// Flood the corner region to color `col`; returns a new board.
function flood(b, col){
  const nb = clone(b), start = b[0][0];
  if (start === col) return nb;
  const stack = [[0,0]], seen = new Set(['0,0']), region = [];
  while (stack.length){
    const [r,c] = stack.pop(); region.push([r,c]);
    for (const [dr,dc] of [[1,0],[-1,0],[0,1],[0,-1]]){
      const nr=r+dr, nc=c+dc;
      if (nr>=0&&nr<N&&nc>=0&&nc<N && !seen.has(nr+','+nc) && b[nr][nc]===start){
        seen.add(nr+','+nc); stack.push([nr,nc]);
      }
    }
  }
  for (const [r,c] of region) nb[r][c] = col;
  return nb;
}
function isWon(b){ const f=b[0][0]; for(let r=0;r<N;r++)for(let c=0;c<N;c++) if(b[r][c]!==f) return false; return true; }
const keyOf = b => b.map(r=>r.join('')).join('|');

// Exact optimal move count via BFS over states (the slow but honest way).
function optimalMoves(start){
  if (isWon(start)) return 0;
  const seen = new Set([keyOf(start)]);
  let frontier = [start], depth = 0;
  while (frontier.length){
    depth++; const next = [];
    for (const st of frontier){
      const cur = st[0][0];
      for (let col=0; col<COLORS; col++){
        if (col===cur) continue;
        const nb = flood(st, col);
        if (isWon(nb)) return depth;
        const k = keyOf(nb);
        if (!seen.has(k)){ seen.add(k); next.push(nb); }
      }
    }
    frontier = next;
  }
  return -1;
}

function setStatus(t, cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function render(){
  const el = document.getElementById('board'); el.innerHTML='';
  for (let r=0;r<N;r++) for (let c=0;c<N;c++){
    const d=document.createElement('div');
    d.className='cell c'+board[r][c]+((r===0&&c===0)?' corner':'');
    el.appendChild(d);
  }
}
function move(col){
  if (col===board[0][0] || isWon(board)) return;
  board = flood(board, col); moves++;
  render();
  if (isWon(board)){
    const opt = optimalMoves(START);
    if (moves===opt) setStatus(fmt('Solved in %moves% moves — that is optimal! 🎉', { moves: moves }),'ok');
    else setStatus(fmt('Solved in %moves% moves. Optimal is %opt%.', { moves: moves, opt: opt }), moves<=opt?'ok':'bad');
    console.log('Solved in', moves, 'moves; optimal =', opt);
  } else setStatus(fmt('Moves: %moves%', { moves: moves }));
}
function showOptimal(){
  const opt = optimalMoves(START);
  setStatus(fmt('The fewest moves possible for this board is %opt%.', { opt: opt }),'ok');
  console.log('Optimal (BFS over board states):', opt, 'moves');
}
function reset(){ board=clone(START); moves=0; render(); setStatus('Moves:0'); }

const pal = document.getElementById('palette');
PALETTE.forEach((hex,i)=>{ const s=document.createElement('div'); s.className='swatch'; s.style.background=hex;
  s.title=fmt('Color %i%%v%', { i: i, v: 1 }); s.addEventListener('click',()=>move(i)); pal.appendChild(s); });
document.getElementById('optimal').addEventListener('click', showOptimal);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

Play a board, then press Show optimal to see the fewest moves possible — the solver searches every sequence with a breadth-first walk and returns the guaranteed minimum. Notice how hard it is to match it by eye. On this tiny grid the search is instant, but the number of sequences explodes with board size: that explosion is exactly why no fast perfect strategy is known.

The Real Complexity

How hard is Flood-It, really? Not playing a single move — finding the shortest full solution.

  • Checking a proposed sequence is easy: replay the moves and confirm the board ends one color. The count of moves is right there.
  • Greedy strategies (flood the largest region, or the most-frequent color) are fast but provably not optimal — they can be forced into many extra moves.
  • It's NP-hard. In 2010, David Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro and Benjamin Sach proved that deciding whether a board can be flooded in k moves is NP-hard whenever there are three or more colors, even on a square grid. There is no known algorithm that finds the optimum quickly in general.
  • Two colors are the exception. With only two colors the game becomes easy and can be solved in polynomial time — the hardness genuinely switches on at three.

That is the punchline, and it echoes a familiar pattern: a problem that is trivial to verify but seems to require searching an exponential pile of options to solve. Flood-It joins the NP-hard family alongside graph coloring and ultimately the open question of P vs NP — the simple corner-flood is intractability wearing bright colors.

Where It Matters

"Spread a property to reach everything in the fewest steps" is a shape that turns up far beyond a phone game, and Flood-It is its friendly face:

  • Flood fill and graphics: the paint-bucket tool in every image editor is a flood fill; choosing how to recolor regions efficiently is the same machinery.
  • Image segmentation: grouping connected pixels of similar color into regions is flood filling at scale.
  • Spreading processes: how an idea, an infection or a rumor diffuses across a network mirrors how a color floods a board.
  • Teaching NP-hardness: because the rules fit in one sentence and everyone can play, Flood-It is a vivid on-ramp to why some optimization problems resist fast solutions.

Understand why Flood-It is hard and you have met combinatorial optimization — the same difficulty behind graph coloring, routing and scheduling, where checking a plan is easy but finding the best one can be impossibly slow.

Conclusion

Flood-It hides a quiet surprise: the same cheerful taps that recolor a board encode a problem we don't know how to solve quickly. Replaying a sequence to check it is instant; finding the shortest one is NP-hard the moment three colors appear. Two colors are easy; three flips the switch.

So the next time the solver beats your score by a move or two, don't feel bad — you ran straight into P vs NP hiding behind a wall of color, and for now there may be no shortcut to perfect play at all.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/flood-it/Content licensed under CC BY-NC 4.0.