Bitmask DFS
Nodes–
Time–
Place one cat per row, column and colour region.
An N×N board has N colour regions. Every row, column and region holds exactly one cat, and no two cats touch, not even diagonally. Play a puzzle, then watch two solvers fight over the same board.
Tap a cell to mark or clear X; double-tap to place a cat. A gold frame means correct and locked, a red frame means wrong.
Rules
- Exactly one cat in every row.
- Exactly one cat in every column.
- Exactly one cat in every colour region.
- Cats never touch, diagonals included.
Same board, same branching order, two solvers. Both are bitmask backtracking; the second one also asks, at every node, whether the unplaced colour regions can still be matched to distinct free rows and to distinct free columns (Hall's condition). If not, it prunes.
DFS + Hall matching
Nodes–
Time–
What the benchmark found
On ordinary puzzles, backtracking with Hall-matching pruning was the fastest method tested: on random unique-solution boards (N=11–16) it needed 0.3 ms against 1.2–1.6 ms for SAT, and on random-region N=25 boards it solved all 20 puzzles (slowest 0.01 s) while three plain DFS variants timed out on 4–5 of 20 at 60 s.
On the hardest puzzles found by hill-climbing (N=10–18, all unique-solution), CDCL SAT was the steadiest: worst single puzzle 76–91 ms, against 454 ms for Hall-matching DFS and 0.8–1.1 s for plain DFS. This is not a worst-case guarantee; no unsatisfiable adversarial puzzles were tried.
SAT is not in this demo because the solvers behind those numbers (CaDiCaL, Glucose, CP-SAT) are native libraries driven from Python; this page is plain static JavaScript with no build step and no dependencies.