What is the complexity of (possibly succinct) Nurikabe?
You seem to be really asking: is Nurikabe in NP?

Nurikabe is NP-hard, since one can build polynomial-size gadgets that can be used to reduce an NP-complete problem to a Nurikabe decision problem.  This is what Holzer, Klein, and Kutrib do, and also McPhail and Fix in their poster (both referenced from the Wikipedia article).

Both groups of authors assume that the problem is trivially in NP, and wave away the question of membership.  Your unease about succinct instances seems spot on -- I do not believe the problem is in NP.  Consider the following way to formalise the decision problem:


  BINARY NURIKABE
  Input: integers m and n in binary, representing a Nurikabe board, and a list of triples, each indicating a position on the board and a positive integer written in that position.
  Question: can the remaining board positions be coloured with two colours, respecting the Nurikabe constraints?


If $m$ and $n$ are instead specified in unary, then the decision problem of determining if there exists some (not necessarily unique) solution to a given Nurikabe instance is in NP, as a solution can be specified in at most $mn$ bits which is then polynomial in the input size.

In contrast, with a binary encoding, there is a problem (as you point out): if one has just one large constraint (say, the number $(m-2)(n-2)$ placed in the middle of the $m \times n$ board), then a solution will require $mn-1$ bits to represent, which is exponential in the size of the input $\Theta(\log\, m + \log\, n)$.  This means that the problem is not in NP, unless small certificates always exist.

Your question then becomes: do there exist polynomial-sized certificates for all binary Nurikabe instances, which can be checked in polynomial time?

It is not obvious to me that such certificates necessarily exist.  Nor is it obvious how one would go about proving that succinct, quickly-verifiable certificates cannot exist.



However, the restriction to unique solutions means that the problem is actually US-hard, so co-NP-hard, and therefore unlikely to be in NP.  The point is that if one regards "has a unique solution" as a Nurikabe constraint (as opposed to a desirable feature of instances that are presented to humans), then it is not sufficient to demonstrate that there is a solution, but one must also demonstrate that no other solutions are possible.  This requirement alone is then enough to ensure the problem is probably not in NP.  This is true even for the unary version of the problem.

In summary: if one relaxes the unique solutions requirement, and specifies the board size in unary, then the decision problem is in NP; with non-unique solutions and binary board size, it is unclear whether the decision problem is in NP; and with unique solutions the decision problem is US-hard and therefore unlikely to be in NP, for either encoding of the board size.