[Solved]: Is Hidoku NP complete?

Problem Detail: 

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.

Asked By : ipsec

Answered By : Vor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11330