Introduction

Open the puzzle page of a newspaper, or a Nikoli book, and you will find a family of grid puzzles that need no arithmetic beyond adding small numbers and no guessing in principle. Kakuro is a crossword made of sums: fill the white cells with digits 1 to 9 so that each run adds up to the clue and no digit repeats inside a run. Nurikabe ("wall" in Japanese, after a ghost-like wall spirit) asks you to shade a grid into a single connected sea and islands: every number is an island of exactly that many cells, every island has one number, and the sea may not contain a 2x2 pool.

Both have the property that makes a puzzle satisfying: if someone shows you a finished grid, you can check it in seconds. Finding the grid is what takes thought. That asymmetry between checking and finding is exactly what the class NP captures, and these puzzles turn out to sit at its hard end.

This article plays both puzzles, builds a solver that mixes the human technique of deduction with the machine technique of backtracking, and explains why no one expects a fast general method. It is a close cousin of Sudoku, Minesweeper, Nonograms and Tents, which are hard for the same reason.

Play and Solve

Pick a puzzle type and a preset. In Kakuro, select a white cell and type a digit; in Nurikabe, click cells to mark sea and island. Rule violations are outlined in red as you go.

<!-- Switch between the two puzzle types -->
<div class="seg">
  <button id="tK" type="button" class="segbtn on">Kakuro</button>
  <button id="tN" type="button" class="segbtn">Nurikabe</button>
</div>
<p class="hint" id="hint"></p>
<div class="row">
  <label class="lbl">Puzzle: <select id="preset"></select></label>
</div>
<div id="board" class="board"></div>
<!-- Digit keypad for Kakuro -->
<div id="pad" class="pad">
  <button type="button" data-d="1">1</button><button type="button" data-d="2">2</button><button type="button" data-d="3">3</button>
  <button type="button" data-d="4">4</button><button type="button" data-d="5">5</button><button type="button" data-d="6">6</button>
  <button type="button" data-d="7">7</button><button type="button" data-d="8">8</button><button type="button" data-d="9">9</button>
  <button type="button" data-d="0" class="ghost" aria-label="Erase digit">&#9003;</button>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="log" id="log" aria-live="polite"></div>
<div class="sat" id="sat"></div>

:root { --fg:#1f2933; --muted:#52606d; --bg:#ffffff; --box:#e8eef3; --boxb:#cdd9e3; --acc:#1d3557;
        --blk:#3b4a5c; --blkfg:#e8eef3; --wht:#ffffff; --sea:#2b5d8a; --land:#fff8e1; --bad:#d62839; --ok:#0a7d33; --hot:#f4a261; --cs:46px; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e4e9ee; --muted:#a3b1bf; --bg:#14181d; --box:#24303c; --boxb:#3a4a5a; --acc:#8fb3dd;
          --blk:#0d1014; --blkfg:#c9d4df; --wht:#1e2730; --sea:#3d7fb5; --land:#2d2a1c; --bad:#ff6b78; --ok:#4cc27a; --hot:#e08a3c; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .86rem; color: var(--muted); margin: .5rem 0; line-height: 1.45; }
.seg { display: flex; gap: 4px; }
.segbtn { flex: 1; background: transparent; color: var(--acc); }
.segbtn.on { background: var(--acc); color: var(--bg); }
.row { margin: .3rem 0; font-size: .85rem; }
select { font: inherit; padding: .25rem; border-radius: 6px; border: 1px solid var(--boxb); background: var(--box); color: var(--fg); }
.board { display: grid; gap: 2px; margin: .5rem 0; width: max-content; max-width: 100%; }
.cell { width: var(--cs); height: var(--cs); display: flex; align-items: center; justify-content: center;
        font: 700 18px ui-monospace, monospace; border-radius: 5px; user-select: none; position: relative; }
.block { background: var(--blk); }
.block.clued { background: linear-gradient(to top right, var(--blk) 49%, var(--blkfg) 49%, var(--blkfg) 51%, var(--blk) 51%); }
.block .sa { position: absolute; top: 2px; right: 4px; font-size: 11px; color: var(--blkfg); }
.block .sd { position: absolute; bottom: 2px; left: 4px; font-size: 11px; color: var(--blkfg); }
.white { background: var(--wht); border: 1px solid var(--boxb); cursor: pointer; }
.white.sel { outline: 3px solid var(--acc); }
.cell.bad { outline: 3px solid var(--bad); }
.cell.hot { box-shadow: 0 0 0 3px var(--hot); }
.cands { display: grid; grid-template-columns: repeat(3, 1fr); width: 100%; height: 100%; font: 600 9px/1 system-ui, sans-serif; color: var(--muted); padding: 2px; text-align: center; }
.cands i { font-style: normal; display: flex; align-items: center; justify-content: center; }
.unk { background: var(--box); border: 1px solid var(--boxb); }
.sea { background: var(--sea); }
.land { background: var(--land); border: 1px solid var(--boxb); }
.num { color: var(--fg); font-size: 20px; }
.dot { width: 8px; height: 8px; border-radius: 50%; background: var(--muted); display: block; }
.pad { display: flex; gap: 4px; flex-wrap: wrap; margin: .3rem 0; }
.pad button { width: 32px; padding: .35rem 0; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .45rem .8rem; border: 1px solid var(--acc); background: var(--acc); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--acc); }
.log { font: 12px/1.4 ui-monospace, monospace; color: var(--fg); background: var(--box); border-radius: 6px; padding: .4rem .6rem; margin-top: .5rem; min-height: 3.6em; }
.sat { font-size: .8rem; color: var(--muted); margin-top: .5rem; line-height: 1.4; }

const popcnt = (m) => { let n = 0; while (m) { n += m & 1; m >>= 1; } return n; };
const maskDigits = (m) => { const o = []; for (let d = 1; d <= 9; d++) if (m & (1 << d)) o.push(d); return o; };

// Kakuro model and solver: candidate bitmasks, run-sum combinations, propagation, then search.
const comboCache = {};
function combos(k, S) {
  const key = k + ',' + S;
  if (comboCache[key]) return comboCache[key];
  const out = [];
  for (let m = 0; m < 1024; m += 2) {
    if (popcnt(m) !== k) continue;
    let s = 0;
    for (let d = 1; d <= 9; d++) if (m & (1 << d)) s += d;
    if (s === S) out.push(m);
  }
  return (comboCache[key] = out);
}
function buildKakuro(layout, sol) {
  const R = layout.length, C = layout[0].length;
  const idx = {}; const cells = [];
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (layout[r][c] === '.') { idx[r + ',' + c] = cells.length; cells.push({ r, c }); }
  const runs = [];
  const addRun = (list, dir) => {
    if (list.length < 2) return;
    let sum = 0;
    if (sol) for (const i of list) sum += +sol[cells[i].r][cells[i].c];
    runs.push({ cells: list, sum, dir, r: cells[list[0]].r, c: cells[list[0]].c });
  };
  for (let r = 0; r < R; r++) { let cur = []; for (let c = 0; c <= C; c++) { if (c < C && layout[r][c] === '.') cur.push(idx[r + ',' + c]); else { addRun(cur, 'a'); cur = []; } } }
  for (let c = 0; c < C; c++) { let cur = []; for (let r = 0; r <= R; r++) { if (r < R && layout[r][c] === '.') cur.push(idx[r + ',' + c]); else { addRun(cur, 'd'); cur = []; } } }
  return { R, C, cells, idx, runs };
}
function* kakuroSearch(model, all, st) {
  const full = 0x3fe;
  function* rec(cand) {
    for (;;) {
      let changed = false;
      for (const run of model.runs) {
        const cs = run.cells;
        let un = 0; for (const c of cs) un |= cand[c];
        let allowed = 0;
        for (const m of combos(cs.length, run.sum)) if ((m & ~un) === 0) allowed |= m;
        for (const c of cs) {
          const nc = cand[c] & allowed;
          if (nc !== cand[c]) { cand[c] = nc; st.deduce++; changed = true; yield { t: 'prune', cell: c, run, cand }; if (nc === 0) return false; }
        }
        for (const c of cs) if (popcnt(cand[c]) === 1) for (const d of cs) if (d !== c && (cand[d] & cand[c])) {
          cand[d] &= ~cand[c]; st.deduce++; changed = true; yield { t: 'single', cell: d, from: c, run, cand }; if (cand[d] === 0) return false;
        }
      }
      if (!changed) break;
    }
    let best = -1, bc = 99;
    for (let i = 0; i < cand.length; i++) { const p = popcnt(cand[i]); if (p > 1 && p < bc) { bc = p; best = i; } }
    if (best < 0) {
      for (const run of model.runs) { let s = 0, seen = 0; for (const c of run.cells) { s += maskDigits(cand[c])[0]; seen |= cand[c]; } if (s !== run.sum || popcnt(seen) !== run.cells.length) return false; }
      yield { t: 'solved', cand }; return true;
    }
    for (const d of maskDigits(cand[best])) {
      st.guess++;
      const cp = cand.slice(); cp[best] = 1 << d;
      yield { t: 'guess', cell: best, d, cand: cp };
      if (yield* rec(cp)) { if (!all) return true; }
      st.back++; yield { t: 'undo', cell: best, d, cand };
    }
    return false;
  }
  yield* rec(new Array(model.cells.length).fill(full));
  yield { t: 'done' };
}
function kakuroSatSize(model) {
  const W = model.cells.length;
  let vars = W * 9, clauses = W + W * 36;
  for (const run of model.runs) {
    const k = run.cells.length;
    clauses += (k * (k - 1) / 2) * 9;
    let perm = 1; for (let i = 0; i < k; i++) perm *= (9 - i);
    let f = 1; for (let i = 2; i <= k; i++) f *= i;
    clauses += perm - combos(k, run.sum).length * f;
  }
  return { vars, clauses };
}

// Nurikabe model and solver: 0 unknown, 1 sea, 2 land; deduction rules, then search.
function nkComps(P, g) {
  const { R, C } = P; const id = new Int16Array(R * C).fill(-1); const comps = [];
  for (let s = 0; s < R * C; s++) {
    if (g[s] !== 2 || id[s] >= 0) continue;
    const cell = [s]; id[s] = comps.length; let n = 0, num = 0;
    for (let q = 0; q < cell.length; q++) {
      const v = cell[q]; if (P.clue[v]) { n = P.clue[v]; num++; }
      for (const w of P.adj[v]) if (g[w] === 2 && id[w] < 0) { id[w] = comps.length; cell.push(w); }
    }
    comps.push({ cells: cell, n, num });
  }
  return { id, comps };
}
function nkMake(rows) {
  const R = rows.length, C = rows[0].length; const clue = new Int8Array(R * C); const adj = [];
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    const ch = rows[r][c]; if (ch !== '.') clue[r * C + c] = +ch;
    const a = []; if (r > 0) a.push((r - 1) * C + c); if (c > 0) a.push(r * C + c - 1); if (c < C - 1) a.push(r * C + c + 1); if (r < R - 1) a.push((r + 1) * C + c);
    adj.push(a);
  }
  return { R, C, clue, adj };
}
// Returns a contradiction, the next forced deduction, or null when no rule applies.
function nkNext(P, g) {
  const { R, C } = P; const N = R * C;
  const { id, comps } = nkComps(P, g);
  for (const k of comps) { if (k.num > 1) return { bad: true }; if (k.n && k.cells.length > k.n) return { bad: true }; }
  for (const k of comps) if (k.n && k.cells.length === k.n) for (const v of k.cells) for (const w of P.adj[v]) if (g[w] === 0) return { i: w, v: 1, why: 'complete' };
  for (let i = 0; i < N; i++) {
    if (g[i] !== 0) continue;
    const seen = new Set(); let tot = 1, nums = 0, lim = 0;
    for (const w of P.adj[i]) if (g[w] === 2 && !seen.has(id[w])) { seen.add(id[w]); const k = comps[id[w]]; tot += k.cells.length; nums += k.num ? 1 : 0; if (k.n) lim = k.n; }
    if (seen.size >= 2 && (nums >= 2 || (lim && tot > lim))) return { i, v: 1, why: 'between' };
  }
  for (let r = 0; r + 1 < R; r++) for (let c = 0; c + 1 < C; c++) {
    const q = [r * C + c, r * C + c + 1, (r + 1) * C + c, (r + 1) * C + c + 1];
    let sea = 0, unk = -1;
    for (const x of q) { if (g[x] === 1) sea++; else if (g[x] === 0) unk = x; }
    if (sea === 4) return { bad: true };
    if (sea === 3 && unk >= 0) return { i: unk, v: 2, why: 'pool' };
  }
  const reach = new Uint8Array(N);
  for (let ci = 0; ci < comps.length; ci++) {
    const k = comps[ci]; if (!k.n) continue;
    const dist = new Int16Array(N).fill(-1); const qu = [];
    for (const v of k.cells) { dist[v] = 0; qu.push(v); reach[v] = 1; }
    const budget = k.n - k.cells.length;
    for (let h = 0; h < qu.length; h++) {
      const v = qu[h]; if (dist[v] >= budget) continue;
      for (const w of P.adj[v]) {
        if (dist[w] >= 0 || g[w] === 1) continue;
        if (g[w] === 2 && id[w] !== ci && comps[id[w]].n) continue;
        dist[w] = dist[v] + 1; reach[w] = 1; qu.push(w);
      }
    }
  }
  for (let i = 0; i < N; i++) if (g[i] !== 1 && !reach[i]) { if (g[i] === 2) return { bad: true }; return { i, v: 1, why: 'unreach' }; }
  let s0 = -1; for (let i = 0; i < N; i++) if (g[i] === 1) { s0 = i; break; }
  if (s0 >= 0) {
    const vis = new Uint8Array(N); const qu = [s0]; vis[s0] = 1;
    for (let h = 0; h < qu.length; h++) for (const w of P.adj[qu[h]]) if (!vis[w] && g[w] !== 2) { vis[w] = 1; qu.push(w); }
    for (let i = 0; i < N; i++) if (g[i] === 1 && !vis[i]) return { bad: true };
  }
  for (const k of comps) {
    if (!k.n || k.cells.length >= k.n) continue;
    const ex = new Set(); for (const v of k.cells) for (const w of P.adj[v]) if (g[w] === 0) ex.add(w);
    if (ex.size === 0) return { bad: true };
    if (ex.size === 1) return { i: [...ex][0], v: 2, why: 'onlyway' };
  }
  return null;
}
function* nkSearch(P, all, st) {
  function* rec(g) {
    for (;;) {
      const d = nkNext(P, g);
      if (d && d.bad) { return false; }
      if (!d) break;
      g[d.i] = d.v; st.deduce++;
      yield { t: 'deduce', why: d.why, cell: d.i, v: d.v, g };
    }
    let pick = -1;
    for (let i = 0; i < g.length && pick < 0; i++) if (g[i] === 0) for (const w of P.adj[i]) if (g[w] === 2) { pick = i; break; }
    if (pick < 0) pick = g.indexOf(0);
    if (pick < 0) { yield { t: 'solved', g }; return true; }
    for (const v of [2, 1]) {
      st.guess++;
      const cp = g.slice(); cp[pick] = v;
      yield { t: 'guess', cell: pick, v, g: cp };
      if (yield* rec(cp)) { if (!all) return true; }
      st.back++; yield { t: 'undo', cell: pick, v, g };
    }
    return false;
  }
  const g0 = new Int8Array(P.R * P.C);
  for (let i = 0; i < g0.length; i++) if (P.clue[i]) g0[i] = 2;
  yield* rec(g0);
  yield { t: 'done' };
}
function nkSatSize(P) {
  const { R, C } = P; const N = R * C;
  const isl = []; for (let i = 0; i < N; i++) if (P.clue[i]) isl.push(P.clue[i]);
  const K = isl.length, tot = isl.reduce((a, b) => a + b, 0), L = N - tot;
  let E = 0; for (const a of P.adj) E += a.length; E /= 2;
  let vars = N + N * K, clauses = N * (1 + (K + 1) * K / 2) + (R - 1) * (C - 1) + E * K * (K - 1);
  for (const n of isl) { vars += N * n + N * n; clauses += N * n * 2 + N * n * 2 + N; }
  vars += N * L; clauses += N * L * 2 + N + 1;
  return { vars, clauses };
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
// Presets: layout plus the hidden solution from which the clues are computed.
const PUZ = {
  k: [
    { name: "Kakuro 3x3 (easy)", layout: ["#..","...","..#"], sol: ["#71","897","16#"] },
    { name: "Kakuro 3x3 (medium)", layout: ["..#","...","#.."], sol: ["26#","982","#95"] },
    { name: "Kakuro 4x4 (needs search)", layout: ["#...","....","...#"], sol: ["#317","1839","697#"] }
  ],
  n: [
    { name: "Nurikabe 5x5 (A)", rows: [".4...","...4.",".....",".1.1.","....1"] },
    { name: "Nurikabe 5x5 (B)", rows: [".3...","...1.","2....",".....","...4."] },
    { name: "Nurikabe 6x6", rows: ["......",".2..4.","......","......","..1.1.","2....."] }
  ]
};
let mode = 'k', pi = 0, P = null, M = null;
let vals = [], g = null, sel = -1;
let solver = null, timer = null;

function stopTimer() { if (timer) { clearInterval(timer); timer = null; } $('run').textContent = "Run"; }
function fillPresets() {
  const s = $('preset'); s.innerHTML = '';
  PUZ[mode].forEach((p, i) => { const o = document.createElement('option'); o.value = i; o.textContent = p.name; s.appendChild(o); });
  s.value = pi;
}
function load() {
  stopTimer(); solver = null; sel = -1;
  const p = PUZ[mode][pi];
  if (mode === 'k') { M = buildKakuro(p.layout, p.sol); vals = new Array(M.cells.length).fill(0); }
  else { P = nkMake(p.rows); g = new Int8Array(P.R * P.C); for (let i = 0; i < g.length; i++) if (P.clue[i]) g[i] = 2; }
  $('hint').innerHTML = mode === 'k' ? "Fill every white cell with a digit 1-9. The number on the top-right of a black cell is the <b>sum</b> of the run to its right; the one on the bottom-left is the sum of the run below it. A digit may not repeat inside a run. Select a cell and use the keypad (or your keyboard). Violations are outlined in red." : "Click a cell to cycle: unknown, <b>sea</b> (blue), <b>island</b> (dot). Each number is an island of exactly that many cells; every island holds one number; the sea is one connected region with no 2x2 pool. Pools and oversized or merged islands are outlined in red.";
  $('pad').style.display = mode === 'k' ? 'flex' : 'none';
  $('tK').classList.toggle('on', mode === 'k'); $('tN').classList.toggle('on', mode === 'n');
  $('log').textContent = "Press Step to watch the solver deduce, guess and backtrack.";
  render();
}

// Rule checks for the player's own marks.
function kakuroBad(v) {
  const bad = new Set(); let n = 0;
  for (const run of M.runs) {
    const seen = {}; let sum = 0, filled = 0, flag = false;
    for (const c of run.cells) { const d = v[c]; if (!d) continue; filled++; sum += d; if (seen[d] !== undefined) { bad.add(c); bad.add(seen[d]); flag = true; } else seen[d] = c; }
    if (sum > run.sum || (filled === run.cells.length && sum !== run.sum)) { for (const c of run.cells) if (v[c]) bad.add(c); flag = true; }
    if (flag) n++;
  }
  return { bad, n };
}
function nkBad(gg) {
  const bad = new Set(); let n = 0;
  for (let r = 0; r + 1 < P.R; r++) for (let c = 0; c + 1 < P.C; c++) {
    const q = [r * P.C + c, r * P.C + c + 1, (r + 1) * P.C + c, (r + 1) * P.C + c + 1];
    if (q.every((x) => gg[x] === 1)) { q.forEach((x) => bad.add(x)); n++; }
  }
  const { comps } = nkComps(P, gg);
  for (const k of comps) if (k.num > 1 || (k.n && k.cells.length > k.n)) { k.cells.forEach((x) => bad.add(x)); n++; }
  return { bad, n };
}
function nkSolved(gg) {
  const h = gg.map((x) => (x === 0 ? 2 : x));
  if (nkBad(h).n) return false;
  const { comps } = nkComps(P, h);
  for (const k of comps) if (!k.n || k.cells.length !== k.n) return false;
  let s0 = h.indexOf(1); if (s0 < 0) return false;
  const vis = new Set([s0]), qu = [s0];
  for (let i = 0; i < qu.length; i++) for (const w of P.adj[qu[i]]) if (h[w] === 1 && !vis.has(w)) { vis.add(w); qu.push(w); }
  let cnt = 0; h.forEach((x) => { if (x === 1) cnt++; });
  return vis.size === cnt;
}

function render() {
  const b = $('board'); b.innerHTML = '';
  if (mode === 'k') renderK(b); else renderN(b);
  sat();
}
function renderK(b) {
  const R = M.R + 1, C = M.C + 1;
  b.style.gridTemplateColumns = `repeat(${C}, var(--cs))`;
  const cur = solver && solver.cand ? solver.cand : null;
  const shown = cur ? cur.map((m) => { const d = maskDigits(m); return d.length === 1 ? d[0] : 0; }) : vals;
  const { bad, n } = cur ? { bad: new Set(), n: 0 } : kakuroBad(vals);
  for (let dr = 0; dr < R; dr++) for (let dc = 0; dc < C; dc++) {
    const d = document.createElement('div');
    const isWhite = dr > 0 && dc > 0 && P0(dr - 1, dc - 1) === '.';
    if (!isWhite) {
      d.className = 'cell block';
      const a = M.runs.find((q) => q.dir === 'a' && q.r === dr - 1 && q.c === dc);
      const dn = M.runs.find((q) => q.dir === 'd' && q.r === dr && q.c === dc - 1);
      if (a || dn) {
        d.classList.add('clued');
        d.innerHTML = `<span class="sa">${a ? a.sum : ''}</span><span class="sd">${dn ? dn.sum : ''}</span>`;
      }
    } else {
      const i = M.idx[(dr - 1) + ',' + (dc - 1)];
      d.className = 'cell white' + (bad.has(i) ? ' bad' : '') + (sel === i && !cur ? ' sel' : '') + (solver && solver.last === i ? ' hot' : '');
      if (shown[i]) d.textContent = shown[i];
      else if (cur && cur[i]) {
        const m = cur[i]; let h = '<div class="cands">';
        for (let q = 1; q <= 9; q++) h += `<i>${m & (1 << q) ? q : ''}</i>`;
        d.innerHTML = h + '</div>';
      }
      d.addEventListener('click', () => { if (solver) return; sel = i; render(); });
    }
    b.appendChild(d);
  }
  if (!cur) {
    const full = vals.every((x) => x);
    if (full && !n) setStatus("Solved - every run has the right sum and no repeats!", 'ok');
    else if (n) setStatus(i18nFmt("Rule violations: %n%", { n }), 'bad');
    else setStatus("Select a cell and type a digit.", '');
  }
}
function P0(r, c) { return PUZ.k[pi].layout[r][c]; }
function renderN(b) {
  b.style.gridTemplateColumns = `repeat(${P.C}, var(--cs))`;
  const gg = solver && solver.g ? solver.g : g;
  const { bad, n } = solver ? { bad: new Set(), n: 0 } : nkBad(gg);
  for (let i = 0; i < gg.length; i++) {
    const d = document.createElement('div');
    d.className = 'cell ' + (gg[i] === 1 ? 'sea' : gg[i] === 2 ? 'land' : 'unk') + (bad.has(i) ? ' bad' : '') + (solver && solver.last === i ? ' hot' : '');
    if (P.clue[i]) { d.textContent = P.clue[i]; d.classList.add('num'); }
    else if (gg[i] === 2) d.innerHTML = '<b class="dot"></b>';
    else d.addEventListener('click', () => { if (solver || P.clue[i]) return; g[i] = (g[i] + 1) % 3; render(); });
    if (!P.clue[i] && gg[i] !== 3) d.style.cursor = solver ? 'default' : 'pointer';
    b.appendChild(d);
  }
  if (!solver) {
    if (nkSolved(g)) setStatus("Solved - islands, sea and pools all check out!", 'ok');
    else if (n) setStatus(i18nFmt("Rule violations: %n%", { n }), 'bad');
    else setStatus("Mark the sea and the islands.", '');
  }
}
function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + cls; }
function nf(x) { return x.toLocaleString(); }
function sat() {
  const z = mode === 'k' ? kakuroSatSize(M) : nkSatSize(P);
  $('sat').textContent = i18nFmt(mode === 'k' ? "SAT encoding of this Kakuro (direct, one variable per cell and digit): %v% variables, %c% clauses." : "Rough size of a textbook SAT encoding of this %cells%-cell Nurikabe (owner, distance and sea-reachability variables): about %v% variables, %c% clauses.", { v: nf(z.vars), c: nf(z.clauses), cells: mode === 'k' ? M.cells.length : P.R * P.C });
}

function rc(i) { return mode === 'k' ? `(${M.cells[i].r + 1}, ${M.cells[i].c + 1})` : `(${Math.floor(i / P.C) + 1}, ${(i % P.C) + 1})`; }
const EV = { complete: "An island is already complete, so its neighbour %cell% must be sea.", between: "Cell %cell% would join two islands (or make one too big), so it is sea.", pool: "Three sea cells around a corner: cell %cell% must be land to avoid a 2x2 pool.", unreach: "No island can reach cell %cell% in time, so it is sea.", onlyway: "An unfinished island has one way to grow: cell %cell% must be land." };
function describe(e) {
  const x = rc(e.cell === undefined ? 0 : e.cell);
  switch (e.t) {
    case 'prune': return i18nFmt("Cell %cell% in the run of sum %s% (%k% cells): candidates narrowed to %d%.", { cell: x, s: e.run.sum, k: e.run.cells.length, d: maskDigits(e.cand[e.cell]).join(', ') || "none" });
    case 'single': return i18nFmt("Cell %from% is fixed to %d%, so cell %cell% in the same run cannot use it.", { cell: x, from: rc(e.from), d: maskDigits(e.cand[e.from])[0] });
    case 'deduce': return i18nFmt(EV[e.why], { cell: x });
    case 'guess': return i18nFmt(mode === 'k' ? "Guess: cell %cell% = %what%." : "Guess: cell %cell% is %what%.", { cell: x, what: mode === 'k' ? e.d : (e.v === 2 ? "land" : "sea") });
    case 'undo': return i18nFmt("Dead end - undo the guess at cell %cell%.", { cell: x });
    case 'solved': return "Solved.";
    default: return "No solution exists.";
  }
}
function newSolver() {
  const st = { deduce: 0, guess: 0, back: 0 };
  const gen = mode === 'k' ? kakuroSearch(M, false, st) : nkSearch(P, false, st);
  solver = { gen, st, last: -1, cand: null, g: null, over: false, found: false };
  if (mode === 'k') solver.cand = new Array(M.cells.length).fill(0x3fe); else { solver.g = new Int8Array(P.R * P.C); for (let i = 0; i < P.clue.length; i++) if (P.clue[i]) solver.g[i] = 2; }
}
function advance() {
  if (!solver) newSolver();
  if (solver.over) return false;
  const r = solver.gen.next();
  if (r.done) { solver.over = true; return false; }
  const e = r.value;
  if (e.cand) solver.cand = e.cand;
  if (e.g) solver.g = e.g;
  solver.last = e.cell === undefined ? -1 : e.cell;
  if (e.t === 'solved') { solver.found = true; solver.over = true; }
  if (e.t === 'done') solver.over = true;
  const s = solver.st;
  $('log').textContent = describe(e) + '  ' + i18nFmt("[deductions %d% | guesses %g% | backtracks %b%]", { d: s.deduce, g: s.guess, b: s.back });
  if (e.t === 'solved') setStatus("Solver found the solution.", 'ok');
  else if (e.t === 'done') setStatus("No solution exists.", 'bad');
  else setStatus("Solver at work...", '');
  return !solver.over;
}
function step() { stopTimer(); advance(); render2(); }
function render2() { const keep = $('status').textContent, cls = $('status').className; render(); if (solver) { $('status').textContent = keep; $('status').className = cls; } }
function run() {
  if (timer) { stopTimer(); return; }
  $('run').textContent = "Pause";
  timer = setInterval(() => { if (!advance()) stopTimer(); render2(); }, 110);
}
function solveAll() {
  stopTimer(); let n = 0;
  while (n++ < 400000 && advance()) { }
  render2();
}
function resetAll() { load(); }

function setDigit(d) {
  if (mode !== 'k' || solver || sel < 0) return;
  vals[sel] = d; render();
}
document.querySelectorAll('#pad button').forEach((b) => b.addEventListener('click', () => setDigit(+b.dataset.d)));
document.addEventListener('keydown', (ev) => {
  if (mode !== 'k' || solver) return;
  if (ev.key >= '1' && ev.key <= '9') setDigit(+ev.key);
  else if (ev.key === 'Backspace' || ev.key === 'Delete' || ev.key === '0') setDigit(0);
  else if (sel >= 0 && ev.key.startsWith('Arrow')) {
    const c = M.cells[sel]; const dr = ev.key === 'ArrowDown' ? 1 : ev.key === 'ArrowUp' ? -1 : 0, dc = ev.key === 'ArrowRight' ? 1 : ev.key === 'ArrowLeft' ? -1 : 0;
    const j = M.idx[(c.r + dr) + ',' + (c.c + dc)]; if (j !== undefined) { sel = j; render(); ev.preventDefault(); }
  }
});
$('tK').addEventListener('click', () => { mode = 'k'; pi = 0; fillPresets(); load(); });
$('tN').addEventListener('click', () => { mode = 'n'; pi = 0; fillPresets(); load(); });
$('preset').addEventListener('change', (e) => { pi = +e.target.value; load(); });
$('step').addEventListener('click', step);
$('run').addEventListener('click', run);
$('solve').addEventListener('click', solveAll);
$('reset').addEventListener('click', resetAll);
fillPresets();
load();
Result
Console

Then press Step to watch the solver. It first applies deductions (forced moves, no guessing) until none applies; only then does it guess, continue deducing from the guess, and backtrack when it reaches a contradiction. On the easy Kakuro presets a guess or two suffices; on the harder presets the guess and backtrack counters climb (the 4x4 Kakuro needs dozens of guesses because its sums leave many digit combinations open). Below the board you will see how large the same puzzle becomes as a SAT instance, which is how industrial solvers attack it.

The Real Complexity

What is proved. Deciding whether a generalized Kakuro grid has a solution is NP-complete. The result is due to Takahiro Seta, whose 2002 bachelor's thesis at the University of Tokyo (supervised by Hiroshi Imai) reduced from 3-SAT and related problems; a companion line of work with Takayuki Yato showed that even the question "is there a second solution?" is as hard (ASP-completeness). For Nurikabe, NP-completeness was shown independently by Brandon McPhail (a 2003 bachelor's thesis at Reed College) and by Markus Holzer, Andreas Klein and Martin Kutrib (FUN with Algorithms, 2004), who proved it even when every clue is 1 or 2; an expanded version with Oliver Ruepp appeared in Fundamenta Informaticae in 2011. Heyawake was shown NP-complete by Holzer and Ruepp (2007), and Hitori and Masyu are also known to be NP-complete. All of these are the "generalized" puzzles on an n×nn \times n board, because a fixed-size puzzle has finitely many instances and is trivially constant time.

Why membership in NP is easy. A candidate grid is verified in polynomial time. For Kakuro with mm white cells, one pass over the runs checks sums and repeats in O(m)O(m). For Nurikabe on NN cells, a flood fill checks island sizes, sea connectivity and the 2x2 rule in O(N)O(N).

Why hardness holds. The proofs build wires, gates and variable gadgets out of puzzle clues, exactly as for Minesweeper. A Kakuro cell with a fixed run-sum offers a small set of digits, which acts like a Boolean choice; runs enforce clause-like constraints. So a puzzle can be made to have a solution if and only if a given 3-SAT formula is satisfiable. This is the same machinery as Cook-Levin and the pattern behind P vs NP.

What it costs to solve. Brute force on Kakuro tries up to 9m9^{m} fillings; Nurikabe has up to 2N2^{N} shadings. Practical solvers are far better than that thanks to constraint propagation. For a Kakuro run of kk cells with sum SS, only a few digit sets qualify (two cells summing to 3 must be {1,2}\{1,2\}, to 17 must be {8,9}\{8,9\}), so each cell's candidate set shrinks before any guess is made. For Nurikabe the standard rules are: a complete island is walled off by sea, a cell touching two islands is sea, a cell no island can reach is sea, and three sea cells around a corner force the fourth to be land. Pseudocode of the loop in the demo:

solve(state):
  repeat
    apply every forced deduction      # propagation
    if a contradiction appears: return fail
  until nothing changes
  if no unknowns left: return state    # solved
  pick an unknown cell x
  for each value v of x:               # branching
    result = solve(state with x = v)
    if result is not fail: return result
  return fail

With good propagation, search trees stay small on human-sized grids, but the worst case remains exponential unless P=NP\mathrm{P} = \mathrm{NP}.

SAT encodings. The alternative is to translate the puzzle to Boolean logic and hand it to a CDCL SAT solver. A direct Kakuro encoding uses a variable xc,dx_{c,d} for "cell cc holds digit dd", giving 9m9m variables. Each cell needs one clause saying it holds some digit and (92)=36\binom{9}{2}=36 clauses saying it holds at most one. Repeats in a run of length kk cost (k2)⋅9\binom{k}{2}\cdot 9 clauses, and each ordered digit tuple that is all-distinct but has the wrong sum is forbidden by one clause of kk literals. For Nurikabe the clues must also say that islands are connected and the sea is connected, which needs auxiliary distance or reachability variables, so the encoding grows roughly like N⋅(island sizes+sea size)N \cdot (\text{island sizes} + \text{sea size}). The demo prints the exact Kakuro counts and a rough Nurikabe estimate for the puzzle on screen. Even so, the encoding stays polynomial, which is why SAT solving is the pragmatic route when a puzzle is too hard for hand deduction.

Where It Matters

  • Teaching reductions. Pencil puzzles are the friendliest place to learn NP-hardness proofs: you can draw the gadgets. Papers on Nikoli puzzles are a steady source of new examples.
  • Constraint solvers. Propagation plus backtracking is the engine of general constraint satisfaction tools used for timetabling, rostering and product configuration, and SAT or CP encodings of puzzles are standard benchmarks for them.
  • Puzzle design. A designer needs puzzles with a unique solution and a gentle path of deductions. A solver that counts solutions and records which rules fired is exactly what generates and grades puzzles; the hardness result explains why generators rely on search rather than a formula.
  • Physical and cryptographic proofs. Because these puzzles are NP-complete, researchers also design zero-knowledge ways to prove "I know a solution" without revealing it.

If you enjoyed these, exact cover shows the structure under many other placement puzzles.

Conclusion

Kakuro, Nurikabe, Hitori, Heyawake and Masyu share a profile: tiny rules, instant verification, and no known fast algorithm for large grids, because each can encode an arbitrary 3-SAT formula. Human solvers and computers use the same two tools, deduction to prune and search for what deduction cannot settle, and SAT encodings let industrial solvers do both at scale.

So the next time a Nurikabe stalls and you have to try a cell to see what breaks, you are running the backtracking step of an algorithm that, in the worst case, nobody expects to beat. That is P vs NP on the puzzle page.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/logic-puzzles-nurikabe-kakuro/Content licensed under CC BY-NC 4.0.