Candy Crush

Candy Crush Saga has been tapped, swapped and rage-quit by hundreds of millions of players. The rules feel trivial: swap two neighboring candies, and if three or more of the same color line up, they pop and the board refills. Hit the level's goal — a score, a number of clears, an ingredient delivered to the bottom — before you run out of moves.

Each individual swap is the simplest thing in the world. You can see in a glance whether it makes a match. But a level isn't won by one swap; it's won by a sequence of them. Which swap now sets up the cascade you'll need three moves from now?

That question — can I reach the goal within the moves I'm given? — is not the casual little puzzle it pretends to be. It is one of the hardest kinds of problem we know how to state.

Here is a tiny match-3 board. Your goal is shown above it. Click two adjacent candies to swap them; if the swap makes a line of three, they clear and the board settles. Try to hit the goal in as few moves as possible.

<p class="hint">{{hint}}</p>
<div class="goal" id="goal">{{cleared_status}}</div>
<div id="board" class="board"></div>
<div class="status" id="status">{{pick_two}}</div>
<div class="depth">
  <label>{{look_ahead_label}}</label>
  <input id="depth" type="range" min="1" max="4" value="1">
</div>
<div class="btns">
  <button id="count" type="button">{{btn_count}}</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 .6rem; line-height: 1.45; }
.goal { font-weight: 700; color: #1d3557; margin: .2rem 0 .5rem; }
.board { display: grid; grid-template-columns: repeat(5, 46px); gap: 4px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; display: flex; align-items: center; justify-content: center;
        font-size: 24px; border-radius: 10px; user-select: none; cursor: pointer;
        background: #f1f3f6; border: 2px solid transparent; transition: all .1s; }
.cell:hover { border-color: #adb5bd; }
.cell.sel { border-color: #1d3557; background: #dbe4ee; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.depth { font-size: .9rem; color: #333; margin: .4rem 0; display: flex; align-items: center; gap: .6rem; }
.depth input { flex: 1; }
.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

Notice the asymmetry. Checking a finished game is effortless: replay the swaps and confirm the goal was met. Finding a winning sequence is the hard part — press Count options and watch how many swap sequences exist as you look further ahead. Each extra move you plan multiplies the branches: the tree of possibilities explodes long before a phone could ever search it all.

How hard is Candy Crush, really? Not the tapping — the planning.

• Checking a proposed solution is trivial: run the swaps and see if the goal is met.
• Brute force explores every legal swap, then every swap after that, then every swap after that — a tree that branches dozens of ways per move and explodes exponentially with the number of moves you plan ahead.
• It's NP-hard. In 2014 the computer scientist Toby Walsh proved that deciding whether a generalized Candy Crush board can be cleared within a given number of moves is NP-hard. He did it by reducing a known hard problem into a match-3 level: arrange the candies so that finding a winning sequence of swaps is exactly the same as satisfying a logic formula.
• So even "can this board be won in k moves?" is as hard as any problem in NP — a single mindless swap is easy, but planning the whole path is intractable in general.

That is the punchline: the moment a level can't be cleared by obvious local matches, you are staring at a genuine instance of the same wall behind P vs NP. The "just one more try" frustration isn't only addictive design — it's combinatorial explosion made playable.

"Find a sequence of moves that reaches a goal" is one of the most common shapes a real problem can take, and Candy Crush is its sweet, friendly face:

• Planning and scheduling: a robot deciding which actions, in which order, to reach a target state is solving the same kind of move-sequence search.
• Logistics and routing: choosing a path through a network of choices, where each decision opens new branches, mirrors the swap tree exactly.
• Game AI: any agent that looks several moves ahead must tame the same exponential blow-up, usually with heuristics rather than full search.
• Teaching complexity: because everyone has felt a level "just out of reach," Candy Crush is a vivid on-ramp to what NP-hardness and combinatorial explosion mean.

Learn why Candy Crush is hard and you've met combinatorial search — the engine under SAT, routing, and countless planning problems.

Candy Crush hides a sweet secret: the same swaps that let you pop three candies can be arranged to encode any logic formula, and through them any problem in NP. One swap stays instant to judge; deciding whether a whole board can be won in the moves you have is as hard as anything in computer science.

So the next time a level taunts you with "almost," take heart — you may not be playing badly. You've simply bumped into P vs NP hiding behind a shower of candy, and there may be no clever shortcut to the winning path at all.