Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a region of connected 'on' cells of that size, and some minor constraints on the region of 'off' cells (it must be connected and can't contain any contiguous 2×2 regions). The Wikipedia page has more explicit rules and sample puzzles, if anyone's curious.
There are some NP-completeness proofs for Nurikabe out there, but they all rely on a 'unary' presentation of the puzzle, with an amount of data that scales roughly with grid size; but one of the unusual features of Nurikabe as opposed to most other similar puzzles is that instances can be potentially 'succinct'. The sum of the provided numbers must be proportional to the area of the grid (since the density of on cells is at least $1/4$), but if the grid size is $n$ then it's possible for a puzzle to use $\mathrm{O}(1)$ numbers each of size $\Theta(n^2)$ (rather than for instance $\Theta(n)$ numbers each of size $\Theta(n)$), for a total puzzle instance size of $\mathrm{O}(\log(n))$ bits – or, viewed the other way, given $n$ bits we can encode at least some Nurikabe puzzles of grid size exponential in $n$.
What I don't know, though, is whether these succinct puzzles can encode computationally-hard problems; the constructions for the NP-completeness reductions I've seen all use $\Theta(n^2)$ numbers of bounded size (in fact, mostly all $1$s and $2$s), and it's possible that puzzles with $\mathrm{O}(1)$ numbers are simpler in some fundamental way (for instance, that their on regions are the union of $\mathrm{O}(1)$ rectangles, which would imply that polynomially-sized witnesses still exist). Does anyone know of any NEXP-completeness results for succinct Nurikabe (or for that matter any other relatively natural puzzles), or of a proof that even this binary-coded version is still NP-complete?
(update: I've asked this question over at cstheory.SE as well, as it seems appropriate there.)
Best Answer
I don't have a proof of NEXP-completeness but I can offer some evidence that succinct Nurikabe isn't in NP and that it can encode computationally difficult problems. Consider this 17 x 16 Nurikabe puzzle:
and its (I believe) unique solution:
This puzzle is based on the fourth iteration of the Hilbert curve construction described in the Wikipedia article on space filling curves, modified slightly to produce a puzzle with a unique solution. I don't see any way to encode a certificate for this solution with fewer than the 272 bits of the naive encoding. And I don't see any way to solve the puzzle short of exponential trial and error.