Is Hidoku NP complete?

Question

A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid must contain a different integer from 1 to $n^2$ and each cell with value $z ≠ n^{2}$ must have a neighbor cell with value $z + 1$ (can also be diagonally).

Is it NP hard to decide whether a given Hidoku is solvable? What reduction could be used?

Edit: according to the comments, I give a little clarification. Given is a grid of cells, some of them already contain values (integers from 1 to n²). We must fill all remaining cells with integers from 1 to $n^2$, such that no two cells have the same value and that every cell with value $z ≠ n²$ has a neighbor with value $z + 1$. That is, after filling out the cells, we must find the path $1, 2, 3,\cdots, n^2$. In the grid, which logically visits each cell.

An example of a Hidoku woud be http://www.janko.at/Raetsel/Hidoku/018.c.gif. An already solved Hidoku is http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif, where you can see the path I was refering to.

Answer 1

I think it is $\sf{NP}$-complete: as noticed by Raphael, Hamiltonian cycle on grid graphs with holes problem is NP-complete (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982)).

So given a grid graph $G$ with holes, you can easily build an equivalent Hidoku game where the initial fixed cells fill all the even diagonals; the empty odd diagonals form an undirected graph that is equivalent to the original grid graph $G$ and the Hidoku has a solution if and only if the original grid graph has an Hamiltonian path.

Figure 1: a grid graph with holes and the equivalent $12 \times 12$ Hidoku puzzle (blue cells represent the initial fixed numbered cells ($1$ is the first, $144$ is the last), white cells are the cells that the player must fill, purple line indicates the sequence of the initial fixed numbered cells).

Auxiliary (filled) lines can be added to the bottom or right side to make it a square.

Another example of reduction from a grid graph to an Hidoku puzzle: the 6x4 grid graph is embedded in a larger 13x13 grid; the even diagonals are filled with fixed numbers, and the remaining free cells are equivalent to the original grid graph.

The full picture with transformation can be downloaded here.

Some additional notes to complete the answer:

• the problem is also known as Hidato; the board can have an arbitrary shape (but as a generalization of the square case, it remains NP-hard);

• as correctly evidenced by Steven Stadnicki in his answer it is not obvious that the problem is in NP if the initial partially filled grid is not given as an $n \times n$ array of integers but is given in some succinct representation; however it is clearly in NP if the initial board is given using the reasonable list of integers representation;

• I think that the original rules of the game say that the solution should be unique; so the problem is in US (US-hard), and unlikely to be in NP.

In summary, if we drop the unique solution constraint and specify the initial board with a list of $n^2$ integers the game is $\sf{NP}$-complete.

Answer 2

One subtle catch: while I think that Vor's answer does a pretty good job of explaining why it would be NP-hard, it's not immediately clear that the problem is in NP, depending on what you define as the input size! Note that the problem specification for an $n\times n$ grid doesn't actually have to be of size $\Omega(n)$; it consists of the integer $n$ (of size $\lg n$) and some number of triplets of integers $(x_i, y_i, w_i): x_i, y_i\leq n, w_i\leq n^2$ saying that the cell with coordinates $(x_i, y_i)$ has value $w_i$; each of these triplets is of size $\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$, so unless you have at least $\Omega(n)$ triplets of initial values specified then your total input size might actually be $o(n)$.

It's very possible that you need at least $\Omega(n)$ given cells to have a unique solution, and so any specification with less than that many givens can be rejected out of hand, but (a) that presumes you're asking about the 'unique solution' variant of the problem rather than the 'exists a solution' variant, and (b) it's not immediately obvious that even that restriction is true; I'm not sure how I would go about trying to prove it.

(For a discussion of similar issues, see my question of a while back on the complexity of succinct Nurikabe over on the cstheory.SE site.)