19
$\begingroup$

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 2x2 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.)

Improve this question
$\endgroup$
2
  • $\begingroup$ It seems nearly impossible to even force a unique solution if the areas are large. If a long boundary zig-zags, then it can exist in an alternate form (pull it in a pixel here, push it out a pixel there). So the long boundaries would have to be aligned with the grid, having at most a single jog. Trying to push the alignment of the jog from place to place seems like the only hope, but the first step would be to see if it is possible to make any valid puzzle at all using large areas. If it is possible, there are surely hard such puzzles. $\endgroup$ – Matt Apr 18 '11 at 16:12
  • $\begingroup$ @matt: There's at least one such puzzle; on an $n\times n$ grid (indexing from $(0,0)$), put $(n-2)^2$ at $(2,2)$ and $4n-3$ at $(1,1)$. This forces the central $(n-2)\times(n-2)$ square and the ring around the outside with the one extra cell at $(1,1)$ as the two regions. $\endgroup$ – Steven Stadnicki Sep 29 '11 at 18:34
2
$\begingroup$

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:

17x16 Nurikabe puzzle

and its (I believe) unique solution:

17x16 Nurikabe puzzle 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Beautiful! It feels like there should be some means of breaking the symmetry but still getting 99 cells in that tree, but I'm certainly not seeing anything. How does the number of 'small' numbers needed for this solution scale up as $n$ does, is it $\Theta(n)$ or $\Theta(\log n)$? $\endgroup$ – Steven Stadnicki Dec 19 '11 at 23:50
  • $\begingroup$ I just went through the solution cell by cell and I see now that it isn't quite unique. The white cell at the base of the main tree can be removed and there are many places it can be reinserted. To fix the puzzle, change the 99 to 98. $\endgroup$ – Kyle Jones Dec 20 '11 at 2:54
  • $\begingroup$ The number of small numbers scale $\Theta$(n). $\endgroup$ – Kyle Jones Dec 20 '11 at 7:47
  • $\begingroup$ That would still leave it in NP then, wouldn't it, since the problem size is thus $\Theta(n)$ rather than $\Theta(\log^k(n))$ for some $k$? $\endgroup$ – Steven Stadnicki Dec 20 '11 at 8:04
  • $\begingroup$ Indeed, you are right. I see no way to bound the growth of the number of 1 cells along the bottom of the puzzle by log(n). $\endgroup$ – Kyle Jones Dec 20 '11 at 16:48
0
$\begingroup$

My suspicion is that this is NP-complete -- specifically one can create instances of Nurikabe almost along your guidelines (O(1) numbers of size \Theta(n^2) + O(n) numbers of size O(1)) which will encode any SAT problem. This would be like the proof that Minesweeper is NP-complete, you use the black squares to lay out a circuit of size O(n), and the Nurikabe problem has a solution iff the corresponding SAT problem has a solution.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Oh, it's clear that it's at least NP-hard - the question is, how do you prove that (general) Nurikabe is even in NP when the solution could (potentially) be exponentially larger than the problem presentation? $\endgroup$ – Steven Stadnicki Aug 30 '11 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.