A puzzle that knows whether you have already lost

Every pencil puzzle I have built so far shares a defect the player never sees. Ask the program whether the position on the screen can still be completed and it cannot answer. It can rule out some dead positions cheaply, and it can settle any position given enough search, but between those two lies a gap it fills by guessing. Nurikabe, Slitherlink and Shikaku are all NP-complete, so this is not a failure of craft. It is the shape of the problem.

This post is about what happens when you remove that defect deliberately. Keep the grid, keep the clues, keep the requirement that a published board has exactly one solution, and swap the global constraint for one that a century of optimisation has already made easy. The puzzle that comes out is playable, and it can do something none of the others can: it can tell you, instantly and correctly, that the position you are looking at is lost.

The rules

Cells of a grid are vertices. The edges between orthogonally adjacent cells are the places you may draw an arrow, at most one arrow per edge.

Some cells are circled with a signed number. A cell circled is a source: it must send out more arrows than it receives. A cell circled is a sink and owes the reverse. Every uncircled cell conserves, sending out exactly as many as it takes in. An uncircled cell may also carry a plain number, its throughput: how many arrows enter it, which by conservation is also how many leave.

Write for the surplus demanded at cell , so at a source, at a sink and elsewhere. A solution is an orientation of a subset of the edges with

with on each directed copy of an edge and at most one direction used per edge. That is a unit-capacity -flow, and the name of the puzzle is the name of the law.

CONSERVATION · UNIQUE SOLUTION

Kirchhoff

Draw arrows along the grid so that flow is conserved. A circled number is a source (+) or a sink (−) with that much to send or absorb. A plain number is throughput: how many arrows enter that cell, which is also how many leave. Every other cell takes in exactly as much as it gives out. Tap an edge to cycle through the two directions and back to nothing.

constructing a layout…

EASY 5×5MEDIUM 6×6HARD 7×7

NEW PUZZLEHINTSHOW SOLUTIONCLEAR

The playable version is at /games/kirchhoff/. Unlike the other three this one is not a Nikoli puzzle, or anyone’s: I made it up, which is the only reason I get to choose its global constraint.

A first observation, and the reason the whole thing hangs together: must be zero, because every arrow contributes at its tail and at its head. Sources and sinks have to balance globally before you look at the board at all.

Why the other three cannot answer the question

In Nurikabe the global constraint is that the shaded cells form one connected region with no block. In Slitherlink it is that the chosen edges form a single closed loop. Both are connectivity conditions on a set you are still choosing, and both are exactly where the NP-completeness comes from. The local arithmetic, taken alone, is easy in all three puzzles.

That has a practical consequence for anyone writing the solver. Your propagators are sound — anything they deduce is true in every completion — but they are necessarily incomplete, because a complete propagator running in polynomial time would decide an NP-complete problem. So the solver ends up as a ladder of rules with a search underneath, and the honest statement of what it knows is “I have not found a contradiction yet”.

You feel this as a player too. When a Nurikabe position is dead, nothing tells you. You keep going until a count fails somewhere far from the mistake, and then you unpick.

What conservation buys

Feasibility of a -flow is decided by a single max-flow computation. The argument is Gale’s, from 1957, and it is the one the player is already making without the vocabulary:

A -flow exists if and only if for every set of vertices, is at most the number of edges leaving .

Read that as a sentence about the board. Draw a boundary around any region. Add up the surplus the sources inside it must push out. If that exceeds the number of edges crossing your boundary, the region cannot export what it owes, and the position is dead. If the two numbers are equal, something stronger happens: every edge crossing the boundary is used, and used outwards. You have determined a whole cut at once, directions included.

That is the puzzle’s central move, and it is why counting edges against demand is the skill the game teaches. The player is computing a min-cut by eye.

There are exponentially many regions, so checking Gale’s condition directly is hopeless. Max-flow duality does it for you in polynomial time: the minimum cut is found without enumerating cuts. The bottleneck the player hunts for by drawing loops on the board is the same object the algorithm returns.

The integrality that makes it honest

One step deserves care, because it is where the argument would collapse if the problem were slightly different. Max-flow works over the rationals. What you draw is a set of arrows — integers. Nothing so far rules out an optimum that wants half an arrow on each of two edges.

Network incidence matrices are totally unimodular: every square submatrix has determinant , or . By the Hoffman–Kruskal theorem a polyhedron with totally unimodular and integral has integral vertices. So the linear program you actually solve has an optimal solution in whole arrows, and the flow the algorithm computes is a flow you can draw.

This is the property being spent. It is not a convenience; it is the entire reason the puzzle is different from its three predecessors, and it is fragile.

The temptation I turned down

The obvious way to make the puzzle prettier is to ban closed circuits of arrows. Every -flow decomposes into source-to-sink paths plus circulations, and a board littered with pointless little loops looks untidy next to one that is a clean set of routes between terminals.

I left circulations legal, and the reason is the whole point of the exercise. “Contains no directed cycle” is not a cut condition and cannot be written as a bound on arcs. Add it and the constraint set stops being a flow polytope, integrality is no longer guaranteed by the theorem above, and max-flow stops answering the question the player is asking. The oracle would confidently call positions alive that are dead under the real rules.

So the choice is between a slightly tidier puzzle whose solver must guess, and a slightly untidier one whose solver knows. Having just written three of the former, I took the latter. The generator still routes disjoint paths and never produces a circulation, so boards look the way I wanted anyway; a player who draws one is simply not breaking a rule.

A hint that cannot be wrong

With exact feasibility available, a genuinely new interface element becomes possible. For an undecided edge, try each of its three states — unused, forward, backward — and test feasibility of each. If exactly one survives, that state is forced: it holds in every completion of the current position. If none survives for any edge, the position is already lost, and the board can say so at the moment it becomes true rather than twenty moves later.

That is what the HINT button does. It is not a nudge toward the stored solution and it never reveals more than the position already implies. Press it on a fresh board and it finds forced edges one after another. Draw a wrong arrow and it tells you immediately.

No NP-hard puzzle in the lab can offer this. A hint button elsewhere is either reading the answer key or running the same incomplete ladder the player has access to anyway.

One caveat, since the implementation is where these claims usually go soft. The network I build for pruning lets an undecided edge contribute an arc in both directions, which means a throughput clue can be satisfied by flow running both ways along a single edge — something no legal board may do. The relaxation is therefore one-sided: it can call a dead position alive, but never a live position dead. Every hint it gives is forced under a superset of the real constraints, so hints are always correct; occasionally it fails to notice a loss as early as it could.

Where the difficulty went

If feasibility is easy, is the puzzle easy? No, and the reason is worth stating because it changed how the generator had to be built.

A published puzzle must have exactly one solution. Deciding whether a second solution exists is a different problem from deciding whether one exists, and the first does not inherit the second’s tractability. Feasibility is polynomial; uniqueness is where the cost reappears, as a three-way branching search over edge states.

The other three generators spend their time asking “can this be solved?”. This one answers that instantly and spends everything on “can this be solved twice?”. Construction runs the other way round: route a set of paths, clue every ordinary cell so the board is trivially unique, then rub clues out one at a time for as long as the solution stays alone. Difficulty is the ratio that survives. Fewer throughput clues pushes the player from cell-local counting up to genuine region cuts.

So the puzzle is not easy. The easy part moved into the machine, and what is left for the player is the part the machine was never doing for them.

What this says about the other three

Comparing four puzzles instead of three sharpens a claim I made when I had only the Nikoli ones. Each was a set of local arithmetic constraints on the clues plus one global constraint, and the difficulty lived in the global one. That reading survives, but it was missing a variable: not all global constraints are equally expensive, and the cost is not about how complicated they look.

Connectivity and loop-formation are conditions on a set still being chosen, and they resist local certificates. Conservation is a condition on a linear function of the choice, and linear conditions over network matrices come with integrality and duality attached. Kirchhoff’s law reads, on the page, like a fussier rule than “the shaded cells must be connected”. It is enormously cheaper.

That is the finding, and I would not have got it by staring harder at Nurikabe. Building a fourth puzzle specifically to break the pattern was the cheapest way to learn what the pattern was actually made of.

Sources

• David Gale, “A theorem on flows in networks”, Pacific Journal of Mathematics 7(2), 1957.
• Alan Hoffman and Joseph Kruskal, “Integral Boundary Points of Convex Polyhedra”, in Linear Inequalities and Related Systems, 1956.
• Lester Ford and Delbert Fulkerson, “Maximal Flow through a Network”, Canadian Journal of Mathematics 8, 1956, for max-flow min-cut.
• Yefim Dinitz, “Algorithm for solution of a problem of maximum flow in networks with power estimation”, Soviet Mathematics Doklady 11, 1970, which is the algorithm the board actually runs.
• Takayuki Yato and Takahiro Seta, “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles”, IEICE Transactions on Fundamentals E86-A(5), 2003, for why uniqueness is its own problem.