P eats NP from both sides.
Zero-dependency polynomial Sudoku solver.
n²×n² grids. Any n.
Drag n to see how the P/NP boundary shifts.
| Zone | Technique | Complexity | What it does |
|---|---|---|---|
| P-Left | BCP-0 | O(n⁴) | Naked + hidden singles cascade |
| P-Left | Naked/hidden subsets | O(n²·C(n²,k)) | Pairs, triples, quads elimination |
| P-Left | Pointing | O(n⁴) | Box-line reduction |
| P-Left | Fish (X-Wing..Jellyfish) | O(n²·C(n²,k)) | Row-column cover sets |
| P-Left | Coloring | O(n⁴) | Graph 2-coloring on conjugate pairs |
| P-Left | XY-Wing | O(n⁶) | Triple-cell inference chain |
| P-Left | greedy_assert | O(n⁴) | Deterministic heuristic fill (full-solve only) |
| P-Left | greedy_multi | O(n⁴·tries) | Permuted cell orderings (MRV + random) |
| NP | BCP-1 | O(n⁶) | Single-depth probing |
| CDCL | cdcl(a) | O(na) | Budgeted DPLL — polynomial backtracking with na node cap |
| NP | uniform_walk | O(budget) | Random constraint walk |
| NP | complex_walk | O(budget) | Walk + polynomial interleave |
| NP | dart | O(n⁴·att) | Randomized probe + BCP-1 cascade |
| P-Right | seed_fill | O(n⁴) | Deterministic permutation (0 givens) |
| P-Right | transform_fill | O(n⁴·tries) | Symmetry group search |
The Clay Mathematics Institute offers $1,000,000 for a proof that P ≠ NP. The implicit bet: NP is untouchable.
This website is the counterpoint.
Sudoku is NP-complete. Every textbook says so, and stops there. We asked a different question: how much of the spectrum is actually hard? The answer is the sandwich — polynomial techniques eat from both ends, leaving an NP strip that covers (n⁴ − n³ − 2n) / n⁴ of the deletion range. As n grows, P coverage converges to 1/n. Not zero. Not trivial. A measured boundary.
Then we added cdcl(a) — budgeted DPLL with a hard cap of na nodes. The exponent is yours to choose. At a = 5, the entire NP strip dissolves for 9×9 (Inkala falls in 243 nodes). At a = 6, 16×16 is polynomial-only. At n = 5, the deep middle still resists — that's where combinatorial hardness genuinely lives. The same framework extends to general SAT in the PolySAT paper, where 12 polynomial techniques hit the wall at SHA-256's diffusion rounds.
The solver is public because if the boundary exists, hiding it helps no one. The scope of what polynomial time can achieve is wider than the P ≠ NP framing suggests. The orange strip above is real — but so are the blue, cyan, teal, and gold zones around it. The question isn't whether NP-hard problems exist. It's how thin the hard part actually is.
Drag the slider. Watch the strip. That's the question.