What is the complexity of succinct (binary) Nurikabe?

computer-science puzzle np-complete computational-complexity

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.

Related

Show that $\phi: \mathbb{R}_3[x]\rightarrow\mathbb{R}^3, \phi(p):=[p(-1), p(0), p(1)] $ is a linear transformation
Mathematical Quine
How to prove $\frac{\pi^2}{6}\le \int_0^{\infty} \sin(x^{\log x}) \ \mathrm dx $?
How many points of intersection between an ellipse and an $L_p$-circle?
How do I install an R package from the source tarball on windows?
SQL string comparison, greater than and less than operators
Authorization header is lost on redirect
Non-blocking console input C++
What is the best way get the symmetric difference between two sets in java?
Why people are so afraid of using clone() (on collection and JDK classes)?
Change floating point rounding mode
jquery's live() is deprecated. What do I use now?