Deep under the keep, a hero is coming for your treasure. They are no fool — they always walk the shortest path from the entrance to the gem. You are the dungeon itself, and you have a few walls to spend. Place them so the hero's shortest way becomes as long as you can make it.
Five labyrinths, each tighter than the last — then a real optimizer builds the cruelest maze it can and shows you the path you missed.
Five labyrinths, five interdiction puzzles — here's the total path you forced next to the proven-longest.
The hero walks the shortest path; you spend a fixed budget of walls to make that shortest path as long as possible. That is shortest-path network interdiction — a two-player optimization: you move first (place walls), the hero responds optimally (re-routes). You're maximizing the minimum.
Why one good wall is rarely enough: the hero just sidesteps a lone wall. A long detour needs walls that close every short way at once — they only pay off together.
It is tempting to try every set of wall positions. With a budget of b walls and m open tiles that is m-choose-b combinations — and for each one you must recompute the hero's shortest path. A modest dungeon explodes past billions of layouts almost immediately.
Unlike the assignment puzzle in The Quest Board, this problem really is hard: interdiction is NP-hard. The defender-then-attacker structure is exactly what makes adversarial planning so much tougher than ordinary planning.
The trick is a famous identity: the hero's shortest path equals the best set of node prices π that go up by at most one step across each open passage (LP duality). Walling a cell simply deletes its constraint, freeing the prices to climb — so a longer path. The keeper's choice becomes one mixed-integer program:
maximize π(treasure) − π(entrance)
price gap π(v) − π(u) ≤ 1 + M·wall(u) (each passage)
budget Σ wall ≤ b, wall ∈ {0,1}
solved to a proof by branch-and-bound → no walls do better ∎
The solver (HiGHS) doesn't guess; it returns the longest forced path with a proof of optimality.
Your five labyrinths were solved live in this tab — a real interdiction MILP per maze, in a Web Worker, proven in milliseconds. Flip the roles and the same model is everywhere defenders meet adversaries: hardening road, power and data networks against the worst failure, stress-testing supply chains for the disruption that hurts most, and planning where a few closures cause the least (or most) delay.
The keeper and the network planner ask the same question: where do a handful of changes matter most?
Use case: network resilience ▸ Follow me for more games ▸