Qequ Blog

2026-06-21

Can you feel the NP?

The feeling of being stuck on a hard puzzle has a precise mathematical shape. I built a game to find it.

The feeling

I really enjoy puzzles. All kinds of puzzles. Sudoku, The Talos Principle, Kanoodle, everything that involves moving pieces and mechanics toward a solution. Board games, logic grids, spatial reasoning, constraint satisfaction. If there's a set of rules and a state to reach, I'm in.

After playing so many of them, I started noticing a feeling that cuts across all of them. Something that shows up whether the game is a paper Sudoku at a coffee shop or a fully rendered 3D puzzle in a game engine. A very specific kind of stuck.

Not blocked-by-a-wall stuck, where there's an obstacle and it's obvious. Not confused-by-instructions stuck. This other kind: everything is understood perfectly. All the pieces are visible. The rules are clear. And yet there are too many possibilities and none of them are obviously right, so one gets tried, leads to a contradiction three moves later, backtrack, try another, that fails too, and somewhere in the branching tree the reason this path was started gets lost and everything starts over.

This feeling has a name. Technically, it's the experience of traversing an exponentially large search tree with no good pruning heuristic. Colloquially, it's what makes a puzzle hard.

I built a game to see if I could replicate it.

Take Sudoku. Everyone knows Sudoku. Fill a 9x9 grid with digits 1 through 9 so that no digit repeats in any row, column, or 3x3 box. Simple rules, clear mechanics, and also, formally, NP-complete.

NP is a complexity class, a way of categorizing problems by how hard they are to solve. P is the class of problems solvable in polynomial time: as the input grows, the computation time grows at a manageable rate. NP is the class where solutions can be verified quickly but finding them may take exponentially longer. Whether P equals NP, whether "easy to check" always implies "easy to find," is the most famous unsolved problem in mathematics. Most researchers believe P != NP, meaning there are problems where no efficient general algorithm exists.

Sudoku sits firmly in NP. So does Minesweeper. So does every puzzle game that involves placing pieces under intersecting constraints. That familiar wall hit on a hard Sudoku, where every cell could plausibly hold three different digits and committing to any of them might unravel four moves later, is the shape of the problem class showing through.

I didn't want to work directly on Sudoku. Too well-trodden, too well-analyzed. I wanted to start from scratch, invent new mechanics, and see whether the NP structure would emerge naturally from the design instead of being inherited from an existing game.

The game

Beacon is a grid puzzle. A set of colored lighthouses, red, yellow, and blue, gets placed on a grid with target cells that need to be lit in specific colors. Beams travel outward from each lighthouse in four directions until they hit a wall or another lighthouse. Colors mix where beams overlap: red + blue = purple, red + yellow = orange, yellow + blue = green, all three = white.

A solved Beacon puzzle on the medium tier

The puzzle: place the lighthouses to satisfy all targets exactly, with a limited supply of each color.

It's NP-complete. Not by analogy or informal argument. There's a formal reduction from 3-SAT. I have a truly elegant proof, but this blog is too small to contain it. Email me and I'll send it.

The short version: each beacon position is a boolean variable. Each target is a clause, "this cell needs red AND blue AND NOT yellow," which encodes a conjunction of literals. Color mixing turns a single tile constraint into something that simultaneously forces multiple beacons' positions AND prohibits others. The blocking mechanic (beacons block each other's beams) creates negative constraints: adding a beacon can remove illumination from a cell, not just add it. This non-monotone behavior is precisely what makes early pruning impossible and what pushes the problem out of polynomial time.

So: formally hard. What happens when trying to make it fun?

The generation paradox

The obvious approach to making NP-complete puzzles is to generate random instances and test them. Pick random beacon positions, compute what they illuminate, assign those as targets, hand it to a solver, verify uniqueness. If it passes, ship it.

This doesn't work well.

The hit rate is low. Most random configurations either have trivially obvious solutions, easy to solve by inspection, or have multiple solutions and are therefore ambiguous. The few that survive both filters produce puzzles with no controllable difficulty.

The deeper problem: not all NP-complete instances are hard. This surprised me more than it should have. NP-completeness is a worst-case statement about a problem class, not about individual instances. Random 3-SAT instances at low clause density are trivially satisfiable, so many solutions exist that finding one is easy. At high density, unit propagation identifies a contradiction immediately. The hard instances live at a phase transition between these extremes, at a clause-to-variable ratio of approximately 4.267. Below that: too easy. Above it: too constrained to be interesting. Right at 4.267, the solver's search tree explodes.

Puzzle design, it turns out, is about engineering instances that hit this transition on purpose.

The approach that worked: solution-first design. Place the beacons first (define the solution), compute the illumination, assign target colors from the illuminated cells, then remove the beacons. A backtracking solver verifies uniqueness. If a different beacon placement also satisfies all targets, a discriminating target or wall gets added until exactly one solution remains.

This sidesteps the generation paradox entirely. Instead of generating random puzzles and hoping they land at the phase transition, the solution gets designed and the constraint structure reverse-engineered from it.

What playtesting taught me

I thought I understood what made puzzles hard before I started playtesting. I was wrong about almost everything.

Blocking is the mechanic.

The first interesting discovery was what players called the "aha" moments. Not when they placed the obvious beacon, the one that clearly illuminates the only cluster of red targets. The aha happened when they realized they needed to place a beacon to block another beacon's beam, not to illuminate anything. A lighthouse placed to cast a shadow, not a light.

This is forced blocking: a negative placement whose purpose is interference rather than illumination. It maps precisely to what makes a SAT clause hard: a literal needed not for its positive effect but to prevent a different assignment from being true.

Difficulty != uniqueness.

My first instinct was to make puzzles unique by adding walls. More walls, fewer valid positions, fewer solutions. This produced puzzles with unique solutions that felt terrible to play. The walls removed the search space for the solver, but they removed the search space for the player too.

The realization: difficulty is about how many plausible-looking wrong solutions exist, not how many correct ones.

A puzzle with 100 possible placements and exactly 1 correct solution is harder than a puzzle with 3 possible placements and 1 correct solution, even though both have unique solutions. The first has 99 wrong paths that each look reasonable until they fail. The second is a multiple-choice question with one obviously wrong answer.

Beacon count dominates.

Instance size overwhelms all other factors. With 3 beacons on a 5x5 grid, there are C(25, 3) ~= 2,300 possible placements. With 6 beacons on an 8x8, there are C(64, 6) ~= 74 million. The backtracking solver times out entirely on 7-beacon configurations, not because of any clever structure, just because the search space is too large to enumerate within any reasonable budget.

Players confirm this subjectively. The jump from 4-beacon to 5-beacon puzzles feels qualitatively different. More like search and less like deduction.

Axis alignment is a cheat code.

Targets clustered on the same rows and columns telegraph the solution. If all red targets sit in column 3, the answer is obvious: put the red beacon somewhere in column 3. This is the NP-complete puzzle equivalent of a Horn clause, a clause with only one positive literal, solvable by unit propagation without any search.

Once this pattern became visible, it showed up everywhere. Every puzzle that felt "easy in a wrong way" had targets sharing too many rows and columns. The fix: spread targets across independent axes. Distribute constraints so that satisfying one target doesn't immediately suggest where another beacon goes. In SAT terms, shared variables push the effective clause density below the phase transition into the "trivially solvable" regime.

Misdirection is the point.

The puzzles players rated highest, genuinely hard and satisfying to solve, had one structural property: a plausible-looking wrong placement that almost works. It satisfies seven of eight targets. The eighth requires undoing everything and starting again.

That's the NP-complete problem structure doing what it's supposed to do, not the designer being cruel. A promising branch of the search tree gets explored, turns out to be wrong, and backtracking from deep inside it produces a sharp oh moment: the gap between what looked right and what actually was. The aha is proportional to how far down the wrong branch the search went before the contradiction surfaced.

The SAT hierarchy is the difficulty curve

Here's the insight that tied everything together.

The SAT family has a well-known complexity hierarchy:

  • Horn-SAT: every clause has at most one positive literal. Solvable in linear time by unit propagation. Trivial.
  • 2-SAT: every clause has at most two literals. Solvable in polynomial time via implication graphs. Tractable.
  • 3-SAT: clauses with up to three literals. NP-complete. Hard in the worst case.

I started noticing that the difficulty tiers in Beacon, across tutorial, easy, medium, hard, expert, and impossible, mapped directly onto this hierarchy in a structural way, beyond rough metaphor.

Tutorial / Horn-SAT: One or two beacons. Single-color targets. Forced placements: the beacon can only go here because it's the only position that illuminates that cluster of targets. Unit propagation. Solver time under 1ms.

Easy-Medium / 2-SAT: Two or three beacons. Mixed colors. Implication chains: "if red goes in that row, it hits the blue target too, so blue must be placed to block it, which means blue goes in column 4." Two-variable interactions that resolve without full search. Solver time around 1-2 seconds.

Hard / 3-SAT: Four or five beacons. Three colors. Three-way interactions where placing beacon A changes what beacon B illuminates, which changes what beacon C must do. No two-variable simplification exists. Misdirection. Solver time around 10 seconds.

Expert / General SAT: Five or six beacons on 7x7+ boards. Multiple beacons per color. Sparse targets. The backtracking solver explores hundreds of thousands of states. Timeout on 5+ beacons.

An expert-tier puzzle mid-solve, with two of three beacons placed

Impossible / Beyond: Six or seven beacons on 8x9 boards. White targets, requiring all three colors to cross simultaneously, encode NAE-3-SAT (Not-All-Equal 3-SAT), known to be harder in practice than standard 3-SAT. The solver times out completely. Solutions verified by hand from known placements.

The playtesting progression discovered empirically, the axis-alignment finding, the misdirection insight, the beacon-count threshold, is just the SAT phase transition appearing in empirical form.

It holds everywhere

Once this pattern appeared in Beacon, I looked for it in other games. It's there in all of them.

Sudoku: Naked singles (only one digit fits this cell) = Horn-SAT. Unit propagation, no search. Hidden singles and pointing pairs (if digit 5 isn't in this box, it must be in that row) = 2-SAT: implication chains. XY-Wing and Swordfish = 3-SAT: three cells interact in a way that can't be decomposed into two-variable subproblems. The hardest Sudoku puzzles sit at around 25-30 givens, the phase transition where pure logical deduction barely suffices.

Flow Free: Forced path extensions (this endpoint has only one adjacent cell to extend to) = Horn-SAT. Bottleneck reasoning (this corridor can only be traversed by one path, creating a chain of implications) = 2-SAT. Three or more paths weaving through a shared region, each routing affecting the others = 3-SAT. The hardest boards are sparse-endpoint configurations where paths must weave tightly with exactly one valid routing.

Minesweeper: The obvious mine (a 1 with one unrevealed neighbor) = Horn-SAT. The 1-1 pattern (two 1s sharing neighbors create mutual implications) = 2-SAT. The 50-50 guess, where no local information resolves any cell, is the regime above the phase transition, where the only strategy is enumeration. Good Minesweeper generators actively avoid producing positions that require guessing. They're filtering for instances that stay in the 2-SAT regime.

The pattern holds:

  • Every game has three tiers: forced moves (Horn-SAT), implication chains (2-SAT), full constraint interaction (3-SAT).
  • "Aha" moments live in 2-SAT: resolving an implication chain, well past the territory of simply noticing a forced move.
  • 3-SAT at the phase transition = satisfying difficulty: enough search to feel hard, but a unique solution guaranteed, so the frustration eventually resolves into finding it.
  • Never require pure guessing: that's past the phase transition into the overconstrained regime, where the only strategy is blind enumeration.

The impossible tier

The six impossible puzzles in Beacon were designed specifically to be intractable for the backtracking solver while remaining human-solvable with the right insight.

White targets encode NAE-3-SAT. A white target requires that red, yellow, AND blue beams all cross at that cell. This is a Not-All-Equal constraint: all three literals must be simultaneously satisfied, and the absence of any one fails the target. NAE-3-SAT is harder in practice than standard 3-SAT because the constraint is both a lower bound (all must be present) and an upper bound (none accidentally absent) at once. Each white target is a planted hard instance.

Column sandwiches create high clause density. The impossible puzzles use geometric configurations where candidate beam paths pass through multiple target cells, creating dense interdependencies between beacon positions. Moving any single beacon affects five or six targets at once. This maximizes the local clause-to-variable ratio, pushing those constraints well past the phase transition.

Non-monotone blocking breaks pruning. In most constraint satisfaction, branches get pruned early: if the current partial assignment already violates a constraint, no extension can fix it. In Beacon this fails. A beacon not yet placed might block another beacon's beam, changing a cell's color from wrong to right. Adding more variables can remove illumination, not just add it. Standard pruning assumes monotone constraint satisfaction. Beacon violates this assumption completely, so the solver enumerates.

The combination: intractable to enumerate, solvable by insight once the structure is visible. The solution requires reading the constraint graph and understanding why certain positions are geometrically forced, which is a different cognitive mode than search.

The NP is tangible

There's a standard CS handwave when explaining NP-completeness to non-specialists. "It means the problem gets really hard really fast as the input grows." Then a gesture toward a complexity diagram. The point lands intellectually but doesn't stick.

Playing an NP-complete puzzle produces a different kind of understanding. Sitting on the sixth puzzle in the hard tier, three beacons placed, everything looking right, but the purple target in the corner isn't lighting up, and fixing it ruins the green target across the board, and backtracking to an empty grid and trying again from a different angle. That's the algorithm running in human form. The branching search tree, the failed branches, the backtracking, the eventual solution that feels obvious once found and completely non-obvious until then.

That's what NP means, experientially. Hard to solve like this: where the solution space is huge, plausible-looking wrong answers abound, and there's no shortcut that consistently avoids them.

The SAT hierarchy works as a map of difficulty as it's actually experienced, by automated solvers and by anyone sitting with a puzzle game, both running the same underlying search. The theoretical taxonomy is the practical one.

Beacon is live.

Notes & references

The literature this investigation leans on, for anyone who wants to dig deeper:

  • Mitchell, Selman, and Levesque (1992), Hard and Easy Distributions of SAT Problems. AAAI. The original phase-transition paper for random 3-SAT.
  • Crawford and Auton (1996), Experimental Results on the Crossover Point in Random 3SAT. Artificial Intelligence. The empirical refinement of the 4.267 clause-to-variable threshold cited in the post.
  • Yato and Seta (2003), Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. IEICE Transactions. The standard reference for Sudoku NP-completeness, via ASP (Another Solution Problem) completeness. This is the closest formal mapping of difficulty onto SAT structure for Sudoku.
  • Simonis (2005), Sudoku as a Constraint Problem. CP Workshop. Models Sudoku resolution rules (naked/hidden singles, pairs, X-Wing) as propagation steps in a CSP, which is the constructive side of the Horn-SAT / 2-SAT / 3-SAT analogy used here.
  • Pelánek (2011), Difficulty Rating of Sudoku Puzzles by a Computational Model. FLAIRS. Empirically rates Sudoku difficulty by the deduction techniques required to solve them, which lines up with the SAT hierarchy directly.
  • McPhail (2005), Light Up is NP-Complete. The proof for Akari/Light Up, used in the post as the monotone cousin of Beacon.
  • Schaefer (1978), The Complexity of Satisfiability Problems. STOC. The dichotomy theorem, which classifies which SAT variants are tractable and places NAE-3-SAT on the hard side.
  • Knuth (2000), Dancing Links. arXiv:cs/0011047. The algorithm for exact cover problems, with Sudoku as the worked example. Useful as a contrast: it's exactly the kind of solver Beacon resists due to non-monotonicity.