graph theory
Posts tagged "graph theory"
2 posts
A puzzle that knows whether you have already lost
The three Nikoli puzzles I built are NP-complete, so their solvers must guess. Replacing the global constraint with flow conservation makes feasibility a max-flow computation, and the board gains a hint button that cannot be wrong.
The mathematics of Nikoli puzzles
Cell Blocks, Nurikabe and Slitherlink share no rules, but they share a shape: local arithmetic plus one global topological constraint. That split explains where the difficulty lives, why propagation always stops short, and what a puzzle with a well-behaved global constraint would look like.