Introduction

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.

Plan the Swaps

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">Goal: <b>clear at least 3 candies</b>. Click two adjacent candies to swap them — if the swap lines up three of a color, they pop. Checking a game is instant; finding a winning plan is the hard part. Use <b>Count options</b> to see the move tree explode.</p>
<div class="goal" id="goal">Cleared: 0 / 3  ·  Moves: 0</div>
<div id="board" class="board"></div>
<div class="status" id="status">Pick two adjacent candies.</div>
<div class="depth">
  <label>Look ahead: <b id="dval">1</b> move(s)</label>
  <input id="depth" type="range" min="1" max="4" value="1">
</div>
<div class="btns">
  <button id="count" type="button">Count options</button>
  <button id="reset" type="button" class="ghost">Reset board</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Match-3 "planning": one swap is trivial to make and to check, but deciding whether a goal is reachable within k moves means searching a tree of swap sequences that branches once per legal swap and explodes exponentially. Deciding clearability in k moves on a generalized board is NP-hard (Toby Walsh, 2014).
const N = 5;
const COLORS = ['🟥','🟦','🟩','🟨','🟪'];
// Fixed starting board so the demo is reproducible (no 3-in-a-row yet).
const START = [
  0,1,0,2,3,
  1,0,1,3,2,
  2,1,2,0,1,
  3,2,3,1,0,
  0,3,0,2,3,
];
let grid = START.slice();
let sel = null, cleared = 0, moves = 0;

const idx = (r,c) => r*N + c;
const adj = (a,b) => { const ra=(a/N)|0,ca=a%N,rb=(b/N)|0,cb=b%N;
  return Math.abs(ra-rb)+Math.abs(ca-cb)===1; };

// Find all matched cells (runs of 3+ horizontally or vertically) in a grid.
function matches(g){
  const hit = new Set();
  for(let r=0;r<N;r++){ let run=1; for(let c=1;c<N;c++){
    if(g[idx(r,c)]===g[idx(r,c-1)]) run++; else run=1;
    if(run>=3) for(let k=0;k<run;k++) hit.add(idx(r,c-k)); } }
  for(let c=0;c<N;c++){ let run=1; for(let r=1;r<N;r++){
    if(g[idx(r,c)]===g[idx(r-1,c)]) run++; else run=1;
    if(run>=3) for(let k=0;k<run;k++) hit.add(idx(r-k,c)); } }
  return hit;
}
// Apply a swap; if it creates a match, clear those cells (mark -1) and report count.
function trySwap(g, a, b){
  const ng = g.slice(); [ng[a],ng[b]] = [ng[b],ng[a]];
  const m = matches(ng);
  if(m.size===0) return null;            // illegal: a swap must make a match
  m.forEach(i => ng[i] = -1);            // cleared cells
  return { grid: ng, count: m.size };
}
// Every legal swap from a position = the branching factor of the search tree.
function legalSwaps(g){
  const out = [];
  for(let a=0;a<N*N;a++) for(let b=a+1;b<N*N;b++) if(adj(a,b))
    if(trySwap(g,a,b)) out.push([a,b]);
  return out;
}

function render(){
  const b = document.getElementById('board'); b.innerHTML='';
  for(let i=0;i<N*N;i++){
    const d=document.createElement('div'); d.className='cell'+(sel===i?' sel':'');
    d.textContent = grid[i]<0 ? '⬜' : COLORS[grid[i]];
    d.addEventListener('click',()=>click(i));
    b.appendChild(d);
  }
  document.getElementById('goal').textContent =
    fmt('Cleared: %cleared% / 3 · Moves: %moves%', { cleared: cleared, moves: moves });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

function click(i){
  if(grid[i]<0){ return; }
  if(sel===null){ sel=i; render(); setStatus('Now pick an adjacent candy.'); return; }
  if(sel===i){ sel=null; render(); setStatus('Pick two adjacent candies.'); return; }
  if(!adj(sel,i)){ setStatus('Those are not adjacent. Pick a neighbor.','bad'); sel=i; render(); return; }
  const res = trySwap(grid, sel, i);
  if(!res){ setStatus('That swap makes no match — not allowed.','bad'); sel=null; render(); return; }
  grid = res.grid; cleared += res.count; moves++; sel=null; render();
  if(cleared>=3) setStatus(fmt('✓ Goal reached in %moves% move(s)! Checking was instant.', { moves: moves }),'ok');
  else setStatus(fmt('Popped %count% candies. Keep going.', { count: res.count }),'ok');
}

// Count distinct swap sequences of length = depth: the size of the search tree.
function countOptions(g, depth){
  if(depth===0) return 1;
  let total = 0;
  for(const [a,b] of legalSwaps(g)){
    const res = trySwap(g,a,b);
    total += countOptions(res.grid, depth-1);
  }
  return total;
}
function doCount(){
  const depth = +document.getElementById('depth').value;
  const t0 = performance.now();
  const n = countOptions(grid, depth);
  const ms = (performance.now()-t0).toFixed(1);
  setStatus(fmt('Looking %depth% move(s) ahead from the current board: %n% swap sequences (%ms% ms).', { depth: depth, n: n, ms: ms }),'');
  console.log('depth', depth, '=>', n, 'sequences in', ms, 'ms');
}

document.getElementById('depth').addEventListener('input', e=>{
  document.getElementById('dval').textContent = e.target.value; });
document.getElementById('count').addEventListener('click', doCount);
document.getElementById('reset').addEventListener('click', ()=>{
  grid = START.slice(); sel=null; cleared=0; moves=0; render(); setStatus('Pick two adjacent candies.'); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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