Flood-It

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.

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">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{moves_prefix}} 0</div>
<div class="palette" id="palette"></div>
<div class="btns">
  <button id="optimal" type="button">{{btn_show_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

"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.

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.