Slitherlink & NP-Complete Pencil Puzzles

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?

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">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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

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.