Yes. Deciding whether an arbitrary Shikaku grid has a solution is NP-complete. That means no known algorithm solves every possible Shikaku efficiently as grids grow — but well-designed puzzles are built to be solvable by step-by-step logic, so they remain fun for people.
What “NP-complete” means
- NP problems are those where a proposed answer can be checked quickly. A Shikaku solution is easy to check: is every cell covered once, and does every rectangle hold one matching number?
- NP-complete problems are the hardest problems in NP: if any one of them could be solved quickly in every case, all NP problems could.
- Whether that is possible is the famous open question P vs NP.
Why Shikaku qualifies
Computer scientists prove NP-completeness by reduction: they show that any instance of a known NP-complete problem can be translated into a Shikaku grid whose solvability matches it. Shikaku is listed among the puzzles proven NP-complete, alongside many other Nikoli genres such as Nurikabe and Tatamibari.
Why humans still solve them quickly
NP-completeness is about the worst case over all possible grids, including enormous, deliberately nasty ones. Published puzzles are different: they are small, have a unique solution, and are designed so a chain of simple deductions always exists. On PuzzleShikaku, every Easy and Medium puzzle is verified to be solvable without any search at all.
How solvers and generators cope
Our Shikaku solver combines constraint propagation — the same forced-rectangle, reachability and overlap rules humans use — with backtracking when logic stalls. On puzzle-sized grids this finishes in milliseconds. The generator uses it to prove each puzzle unique before you ever see it.
Further reading
Questions
Is Shikaku NP-hard?
Yes. Shikaku is NP-complete, which means it is both in NP and NP-hard.
Can a computer solve any Shikaku?
Practical solvers handle puzzle-sized grids almost instantly. NP-completeness only means there is no known method that is guaranteed to be fast for every possible grid as size grows without limit.