15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Intuitively, without thinking much through it, it sounds polytime solvable on first glance. Something like dynamic programming on the values allowed ($1, \dots, n^2$) and the vertices ($v_1, \dots v_n$). Sounds solvable in time $O(n^3)$. $\endgroup$ – Pål GD Apr 15 '13 at 13:36
  • $\begingroup$ This can be modelled equivalently as graph, connecting nodes with edges if they are successors in $\mathbb{N}$. Then, you are looking for a Hamilton path. According to Hamilton paths in grid graphs by Itai et al. (1982) this problem is NP-complete in grid graphs. This does not immediately fit your problem since you allow diagonal connections, but it bodes badly. $\endgroup$ – Raphael Apr 15 '13 at 14:29
  • $\begingroup$ @Raphael isn't the constructed graph a DAG? $\endgroup$ – Pål GD Apr 15 '13 at 15:25
  • $\begingroup$ I don't see how this is a DAG. As far as I understand, the input is a (undirected) grid graph (containing also diagonal edges) and the goal is to find a Hamiltonian path, where the position of some nodes on the path is given. $\endgroup$ – George Apr 15 '13 at 15:46
  • $\begingroup$ @George Okey, I interpreted the question as finding the maximum path of increasing values in a grid! $\endgroup$ – Pål GD Apr 15 '13 at 15:50
7
$\begingroup$

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.

enter image description here

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ Isn't this a DAG? Have I completely misunderstood the question? $\endgroup$ – Pål GD Apr 15 '13 at 15:39
  • $\begingroup$ @PålGD: no, i don't think it is a DAG, it is an undirected grid graph with diagonal edges. The game starts with a partially filled board and the player must start from cell 1 and reach the last one making orthogonal or diagonal steps (but perhaps I don't rememeber the rules very well ... now I check it) $\endgroup$ – Vor Apr 15 '13 at 15:45
  • 1
    $\begingroup$ But it says "find a path of successive integers". $\endgroup$ – Pål GD Apr 15 '13 at 15:46
  • $\begingroup$ Perhaps it simply means that it cannot visit the same cell twice, and that all cells must be visited $\endgroup$ – Vor Apr 15 '13 at 15:47
  • $\begingroup$ "The goal is to find a path of successive integers (from $1$ to $n^2$) in the grid"? $\endgroup$ – Pål GD Apr 15 '13 at 15:48
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Not specifying the board size in unary strikes me as an unreasonable interpretation. $\endgroup$ – David Eisenstat Apr 16 '13 at 0:36
  • $\begingroup$ @DavidEisenstat It's not necessarily the natural interpretation, but it seems like a perfectly valid one to me. $\endgroup$ – Steven Stadnicki Apr 16 '13 at 0:58
  • $\begingroup$ @StevenStadnicki: I agree with you, I made a similar note in the proof of NP-completeness of Binary Puzzle that I recently posted on cstheory.stackexchange.com. Though the non-unary representation is indeed not so reasonable :-). I'll add a note on my answer. And I should address the problem of the solution uniqueness, too; because I think that the original rules say that the solution should be unique. $\endgroup$ – Vor Apr 16 '13 at 6:38

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.