The Real Complexity of Slitherlink

Introduction

Slitherlink is one of those quiet pencil puzzles that fill the back pages of newspapers and puzzle magazines. You start with a grid of dots scattered with small numbers, and your only job is to draw one single closed loop along the grid lines. The loop may not branch, cross itself, or split into pieces — it has to be a single continuous circuit.

The numbers are the clues. Each one sits in a little cell and tells you exactly how many of the four edges around that cell the loop must use. A 0 means "the loop stays away from me entirely"; a 3 means "three of my four sides are loop." Cells with no number are free.

It feels meditative — a few logical nudges and the loop seems to draw itself. But hidden in that gentle ritual is a question that computer scientists place among the very hardest they know: given the numbers, is there any single loop that fits them at all?

Draw the Loop

Here is a small Slitherlink grid. Click the dashes between the dots to switch edges on and off, and try to draw a single closed loop so that every number matches the count of loop edges around its cell.

<p class="hint">Click the dashes between dots to toggle loop edges. Each number says how many of its four surrounding edges are part of the loop. Build <b>one single closed loop</b> with no branches or crossings that satisfies every clue. Checking a drawing is instant — finding the loop is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Toggle edges, then check.</div>
<div class="btns">
  <button id="check" type="button">Check loop</button>
  <button id="solve" type="button">Find the loop</button>
  <button id="reset" type="button" class="ghost">Clear</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 .8rem; line-height: 1.45; }
.grid { display: inline-grid; gap: 0; margin: .4rem 0; }
.dot { width: 9px; height: 9px; border-radius: 50%; background: #1d3557; justify-self: center; align-self: center; }
.h-edge, .v-edge { background: transparent; cursor: pointer; transition: background .1s; }
.h-edge { width: 44px; height: 9px; align-self: center; justify-self: center; border-radius: 5px; }
.v-edge { width: 9px; height: 44px; align-self: center; justify-self: center; border-radius: 5px; }
.h-edge:hover, .v-edge:hover { background: #c9ccd1; }
.h-edge.on, .v-edge.on { background: #e63946; }
.cell { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        font: 700 18px ui-monospace, monospace; color: #1d3557; }
.cell.blank { color: transparent; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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] ?? ''));
// Slitherlink: on a grid of dots, draw a single closed loop along the dashes.
// Each numbered cell counts how many of its 4 surrounding edges are on the loop.
// A blank cell has no constraint. Checking a candidate is a quick scan; deciding
// whether ANY satisfying single loop exists is NP-complete (Yato & Seta, 2003).
const R = 3, C = 3;                 // cells: 3x3 -> 4x4 dots
// Clues (null = blank). This board has a unique single-loop solution.
const CLUES = [
  [null, 2,    null],
  [3,    2,    1   ],
  [null, 0,    null]
];
// Edge model: horizontal edges H[r][c] for r in 0..R (rows of dots), c in 0..C-1.
// vertical   edges V[r][c] for r in 0..R-1,  c in 0..C.
const H = [], V = [];
for (let r = 0; r <= R; r++) { H[r] = []; for (let c = 0; c < C; c++) H[r][c] = 0; }
for (let r = 0; r < R; r++) { V[r] = []; for (let c = 0; c <= C; c++) V[r][c] = 0; }

function cellEdges(r, c) { // the 4 edges of cell (r,c)
  return [['H',r,c],['H',r+1,c],['V',r,c],['V',r,c+1]];
}
function get(t,r,c){ return t==='H'?H[r][c]:V[r][c]; }
function set(t,r,c,v){ if(t==='H')H[r][c]=v; else V[r][c]=v; }

// ---- validity check ----
// (1) every clue equals the number of its on-edges
// (2) every dot touches 0 or 2 on-edges (degree)
// (3) the on-edges form exactly ONE loop (one connected component, no stray)
function dotDegree(r, c) { // dot at (r,c), r in 0..R, c in 0..C
  let d = 0;
  if (c < C && H[r][c]) d++;            // right
  if (c > 0 && H[r][c-1]) d++;          // left
  if (r < R && V[r][c]) d++;            // down
  if (r > 0 && V[r-1][c]) d++;          // up
  return d;
}
function valid() {
  // clues
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (CLUES[r][c] == null) continue;
    const k = cellEdges(r,c).reduce((s,[t,a,b]) => s + get(t,a,b), 0);
    if (k !== CLUES[r][c]) return false;
  }
  // degrees 0 or 2
  let onEdges = 0, startDot = null;
  for (let r = 0; r <= R; r++) for (let c = 0; c <= C; c++) {
    const d = dotDegree(r,c);
    if (d !== 0 && d !== 2) return false;
    if (d === 2 && !startDot) startDot = [r,c];
  }
  for (let r = 0; r <= R; r++) for (let c = 0; c < C; c++) onEdges += H[r][c];
  for (let r = 0; r < R; r++) for (let c = 0; c <= C; c++) onEdges += V[r][c];
  if (onEdges === 0) return false;            // empty is not a loop
  // single component: walk from startDot, count edges reached
  const seen = new Set();
  let reached = 0;
  const stack = [startDot];
  const id = (r,c) => r + ',' + c;
  const visitedDots = new Set([id(startDot[0],startDot[1])]);
  while (stack.length) {
    const [r,c] = stack.pop();
    const nbrs = [];
    if (c < C && H[r][c]) nbrs.push([r, c+1]);
    if (c > 0 && H[r][c-1]) nbrs.push([r, c-1]);
    if (r < R && V[r][c]) nbrs.push([r+1, c]);
    if (r > 0 && V[r-1][c]) nbrs.push([r-1, c]);
    for (const [nr,nc] of nbrs) {
      reached++;                              // counts each edge twice (both ends)
      if (!visitedDots.has(id(nr,nc))) { visitedDots.add(id(nr,nc)); stack.push([nr,nc]); }
    }
  }
  // reached/2 = edges in the component; must equal total on-edges => one loop
  return reached / 2 === onEdges;
}

// ---- exhaustive solver (the "hard part"): try every subset of edges ----
function allEdges(){ const e=[];
  for (let r=0;r<=R;r++) for (let c=0;c<C;c++) e.push(['H',r,c]);
  for (let r=0;r<R;r++) for (let c=0;c<=C;c++) e.push(['V',r,c]);
  return e; }
function solve() {
  const E = allEdges(); let steps = 0, found = null;
  for (let mask = 0; mask < (1 << E.length); mask++) { steps++;
    E.forEach(([t,r,c],i) => set(t,r,c,(mask >> i) & 1));
    if (valid()) { found = mask; break; }
  }
  return { steps, found, total: 1 << E.length };
}

// ---- rendering ----
const grid = document.getElementById('grid');
function render() {
  grid.style.gridTemplateColumns = `repeat(${2*C+1}, auto)`;
  grid.innerHTML = '';
  for (let gr = 0; gr <= 2*R; gr++) {
    for (let gc = 0; gc <= 2*C; gc++) {
      const el = document.createElement('div');
      const evenR = gr % 2 === 0, evenC = gc % 2 === 0;
      if (evenR && evenC) { el.className = 'dot'; }
      else if (evenR && !evenC) {           // horizontal edge
        const r = gr/2, c = (gc-1)/2;
        el.className = 'h-edge' + (H[r][c] ? ' on' : '');
        el.addEventListener('click', () => { H[r][c] ^= 1; reset(false); render(); });
      } else if (!evenR && evenC) {         // vertical edge
        const r = (gr-1)/2, c = gc/2;
        el.className = 'v-edge' + (V[r][c] ? ' on' : '');
        el.addEventListener('click', () => { V[r][c] ^= 1; reset(false); render(); });
      } else {                               // cell center (clue)
        const r = (gr-1)/2, c = (gc-1)/2; const v = CLUES[r][c];
        el.className = 'cell' + (v == null ? ' blank' : '');
        el.textContent = v == null ? '·' : v;
      }
      grid.appendChild(el);
    }
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }
function clearEdges() {
  for (let r=0;r<=R;r++) for (let c=0;c<C;c++) H[r][c]=0;
  for (let r=0;r<R;r++) for (let c=0;c<=C;c++) V[r][c]=0;
}
function reset(full) { if (full) { clearEdges(); render(); } setStatus(full ? 'Toggle edges, then check.' : '', ''); }

document.getElementById('check').addEventListener('click', () => {
  if (valid()) setStatus('✓ One closed loop and every clue satisfied!', 'ok');
  else setStatus('✗ Not a valid single loop yet — keep deducing.', 'bad');
});
document.getElementById('solve').addEventListener('click', () => {
  const { steps, found, total } = solve();
  if (found != null) { render();
    setStatus(fmt('Found the loop after checking %steps% of %total% edge subsets.', { steps: steps, total: total }), 'ok');
    console.log('Solved by brute force: checked', steps, 'of', total, 'subsets');
  } else { clearEdges(); render(); setStatus('No single loop satisfies these clues.', 'bad'); }
});
document.getElementById('reset').addEventListener('click', () => reset(true));
render();

<p class="hint">Click the dashes between dots to toggle loop edges. Each number says how many of its four surrounding edges are part of the loop. Build <b>one single closed loop</b> with no branches or crossings that satisfies every clue. Checking a drawing is instant — finding the loop is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Toggle edges, then check.</div>
<div class="btns">
  <button id="check" type="button">Check loop</button>
  <button id="solve" type="button">Find the loop</button>
  <button id="reset" type="button" class="ghost">Clear</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 .8rem; line-height: 1.45; }
.grid { display: inline-grid; gap: 0; margin: .4rem 0; }
.dot { width: 9px; height: 9px; border-radius: 50%; background: #1d3557; justify-self: center; align-self: center; }
.h-edge, .v-edge { background: transparent; cursor: pointer; transition: background .1s; }
.h-edge { width: 44px; height: 9px; align-self: center; justify-self: center; border-radius: 5px; }
.v-edge { width: 9px; height: 44px; align-self: center; justify-self: center; border-radius: 5px; }
.h-edge:hover, .v-edge:hover { background: #c9ccd1; }
.h-edge.on, .v-edge.on { background: #e63946; }
.cell { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        font: 700 18px ui-monospace, monospace; color: #1d3557; }
.cell.blank { color: transparent; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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] ?? ''));
// Slitherlink: on a grid of dots, draw a single closed loop along the dashes.
// Each numbered cell counts how many of its 4 surrounding edges are on the loop.
// A blank cell has no constraint. Checking a candidate is a quick scan; deciding
// whether ANY satisfying single loop exists is NP-complete (Yato & Seta, 2003).
const R = 3, C = 3;                 // cells: 3x3 -> 4x4 dots
// Clues (null = blank). This board has a unique single-loop solution.
const CLUES = [
  [null, 2,    null],
  [3,    2,    1   ],
  [null, 0,    null]
];
// Edge model: horizontal edges H[r][c] for r in 0..R (rows of dots), c in 0..C-1.
// vertical   edges V[r][c] for r in 0..R-1,  c in 0..C.
const H = [], V = [];
for (let r = 0; r <= R; r++) { H[r] = []; for (let c = 0; c < C; c++) H[r][c] = 0; }
for (let r = 0; r < R; r++) { V[r] = []; for (let c = 0; c <= C; c++) V[r][c] = 0; }

function cellEdges(r, c) { // the 4 edges of cell (r,c)
  return [['H',r,c],['H',r+1,c],['V',r,c],['V',r,c+1]];
}
function get(t,r,c){ return t==='H'?H[r][c]:V[r][c]; }
function set(t,r,c,v){ if(t==='H')H[r][c]=v; else V[r][c]=v; }

// ---- validity check ----
// (1) every clue equals the number of its on-edges
// (2) every dot touches 0 or 2 on-edges (degree)
// (3) the on-edges form exactly ONE loop (one connected component, no stray)
function dotDegree(r, c) { // dot at (r,c), r in 0..R, c in 0..C
  let d = 0;
  if (c < C && H[r][c]) d++;            // right
  if (c > 0 && H[r][c-1]) d++;          // left
  if (r < R && V[r][c]) d++;            // down
  if (r > 0 && V[r-1][c]) d++;          // up
  return d;
}
function valid() {
  // clues
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (CLUES[r][c] == null) continue;
    const k = cellEdges(r,c).reduce((s,[t,a,b]) => s + get(t,a,b), 0);
    if (k !== CLUES[r][c]) return false;
  }
  // degrees 0 or 2
  let onEdges = 0, startDot = null;
  for (let r = 0; r <= R; r++) for (let c = 0; c <= C; c++) {
    const d = dotDegree(r,c);
    if (d !== 0 && d !== 2) return false;
    if (d === 2 && !startDot) startDot = [r,c];
  }
  for (let r = 0; r <= R; r++) for (let c = 0; c < C; c++) onEdges += H[r][c];
  for (let r = 0; r < R; r++) for (let c = 0; c <= C; c++) onEdges += V[r][c];
  if (onEdges === 0) return false;            // empty is not a loop
  // single component: walk from startDot, count edges reached
  const seen = new Set();
  let reached = 0;
  const stack = [startDot];
  const id = (r,c) => r + ',' + c;
  const visitedDots = new Set([id(startDot[0],startDot[1])]);
  while (stack.length) {
    const [r,c] = stack.pop();
    const nbrs = [];
    if (c < C && H[r][c]) nbrs.push([r, c+1]);
    if (c > 0 && H[r][c-1]) nbrs.push([r, c-1]);
    if (r < R && V[r][c]) nbrs.push([r+1, c]);
    if (r > 0 && V[r-1][c]) nbrs.push([r-1, c]);
    for (const [nr,nc] of nbrs) {
      reached++;                              // counts each edge twice (both ends)
      if (!visitedDots.has(id(nr,nc))) { visitedDots.add(id(nr,nc)); stack.push([nr,nc]); }
    }
  }
  // reached/2 = edges in the component; must equal total on-edges => one loop
  return reached / 2 === onEdges;
}

// ---- exhaustive solver (the "hard part"): try every subset of edges ----
function allEdges(){ const e=[];
  for (let r=0;r<=R;r++) for (let c=0;c<C;c++) e.push(['H',r,c]);
  for (let r=0;r<R;r++) for (let c=0;c<=C;c++) e.push(['V',r,c]);
  return e; }
function solve() {
  const E = allEdges(); let steps = 0, found = null;
  for (let mask = 0; mask < (1 << E.length); mask++) { steps++;
    E.forEach(([t,r,c],i) => set(t,r,c,(mask >> i) & 1));
    if (valid()) { found = mask; break; }
  }
  return { steps, found, total: 1 << E.length };
}

// ---- rendering ----
const grid = document.getElementById('grid');
function render() {
  grid.style.gridTemplateColumns = `repeat(${2*C+1}, auto)`;
  grid.innerHTML = '';
  for (let gr = 0; gr <= 2*R; gr++) {
    for (let gc = 0; gc <= 2*C; gc++) {
      const el = document.createElement('div');
      const evenR = gr % 2 === 0, evenC = gc % 2 === 0;
      if (evenR && evenC) { el.className = 'dot'; }
      else if (evenR && !evenC) {           // horizontal edge
        const r = gr/2, c = (gc-1)/2;
        el.className = 'h-edge' + (H[r][c] ? ' on' : '');
        el.addEventListener('click', () => { H[r][c] ^= 1; reset(false); render(); });
      } else if (!evenR && evenC) {         // vertical edge
        const r = (gr-1)/2, c = gc/2;
        el.className = 'v-edge' + (V[r][c] ? ' on' : '');
        el.addEventListener('click', () => { V[r][c] ^= 1; reset(false); render(); });
      } else {                               // cell center (clue)
        const r = (gr-1)/2, c = (gc-1)/2; const v = CLUES[r][c];
        el.className = 'cell' + (v == null ? ' blank' : '');
        el.textContent = v == null ? '·' : v;
      }
      grid.appendChild(el);
    }
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }
function clearEdges() {
  for (let r=0;r<=R;r++) for (let c=0;c<C;c++) H[r][c]=0;
  for (let r=0;r<R;r++) for (let c=0;c<=C;c++) V[r][c]=0;
}
function reset(full) { if (full) { clearEdges(); render(); } setStatus(full ? 'Toggle edges, then check.' : '', ''); }

document.getElementById('check').addEventListener('click', () => {
  if (valid()) setStatus('✓ One closed loop and every clue satisfied!', 'ok');
  else setStatus('✗ Not a valid single loop yet — keep deducing.', 'bad');
});
document.getElementById('solve').addEventListener('click', () => {
  const { steps, found, total } = solve();
  if (found != null) { render();
    setStatus(fmt('Found the loop after checking %steps% of %total% edge subsets.', { steps: steps, total: total }), 'ok');
    console.log('Solved by brute force: checked', steps, 'of', total, 'subsets');
  } else { clearEdges(); render(); setStatus('No single loop satisfies these clues.', 'bad'); }
});
document.getElementById('reset').addEventListener('click', () => reset(true));
render();

Result

Console

Notice the asymmetry. Checking a finished drawing is effortless: count the edges around each number, confirm every dot has either zero or two edges, and confirm the on-edges form one connected loop. Finding the loop is the hard part — press Find the loop and the computer simply tries every subset of edges. This tiny board already has 24 edges, so brute force walks through $2^{24}$ ≈ 16 million possibilities; add a few rows and the count explodes.

The Real Complexity

How hard is Slitherlink, really? Not the drawing — the deciding.

Checking a candidate is trivial: verify each clue, that every dot has degree 0 or 2, and that the edges form one loop. All of this is a quick scan, the hallmark of a problem in NP.
Brute force tries every subset of the grid's edges — $2^{n}$ combinations, hopeless once the grid grows past a few rows.
It's NP-complete. In 2003, Takayuki Yato and Takahiro Seta proved that deciding whether a Slitherlink instance has any valid loop is NP-complete. The proof wires logic into the puzzle: clue gadgets force the loop to behave like wires and gates, so any SAT formula can be encoded as a Slitherlink board.
The cousins are hard too. The same kind of result holds for a whole family of Japanese pencil puzzles — Masyu, Nurikabe, Akari (Light Up), Hashiwokakero (Bridges) and others are all NP-complete. Simple rules, brutal worst case.

That is the punchline: the moment a puzzle can't be settled by quick local deductions, you are looking at a genuine instance of the same problem behind P vs NP. The "uniquely solvable, solve by logic alone" promise on the magazine cover is doing a lot of quiet work — in general, there is no known shortcut.

Where It Matters

"Satisfy local count constraints and form one connected structure" is a shape that shows up far beyond the puzzle page:

SAT solving: the gadget-building trick that proves Slitherlink hard is the same engine modern SAT solvers use to crack the constraints in reverse.
Routing and network design: laying out one non-crossing circuit that touches the right things is the heart of VLSI wire routing and loop-based network topologies.
Puzzle generation: making a puzzle with a unique solution is itself a hard search problem — generators lean on the same solvers.
Teaching complexity: because the rules are so simple, Slitherlink is a vivid way to show that "easy to state" has nothing to do with "easy to solve."

Learn why Slitherlink is hard and you've met the union of constraint satisfaction and connectivity — the engine under SAT and cousins like Nonogram and Sudoku.

Conclusion

Slitherlink hides a beautiful secret: the same numbers that guide your pencil into a tidy loop can be wired into logic gates, and through them into any problem in NP. Checking a finished loop stays instant; deciding whether a valid loop even exists is as hard as anything in computer science — and the whole family of Japanese pencil puzzles, from Masyu to Nurikabe, shares the same fate.

So the next time a loop puzzle leaves you stuck, take comfort — you haven't lost your touch. You've simply run into P vs NP hiding inside a grid of dots, and there may be no clever way around the search at all.

Comments

Loading comments...

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

Cookies & privacy

Slitherlink & NP-Complete Pencil Puzzles

When drawing one loop becomes a hard problem