<p>I received an email last February from a Spanish undergraduate, Nil Mamano, with a proof that this problem is indeed NP-complete, by reduction from Hamiltonian path in grid graphs. I don't know that it has been published anywhere yet. The reduction replaces each vertex of the grid graph by a 2x2 block of 1's, and each edge, face, or missing vertex by a 2x2 block of 0's. The input sequence alternates between subsequences of four 1's and four 0's for as many times as is needed to cover all the vertices, then fills out the rest of the sequence with 0's. To match the input sequence, a path through the grid must align the subsequences of four 1's with the 2x2 blocks of 1's from the reduction, forming a Hamiltonian path; if such a path exists, it's always possible to do this in a way that allows the rest of the matrix to be covered by the remaining zeros at the end of the sequence.</p>

CC BY-SA 3.0
2014-06-27T20:43:59.927Z
2014-06-27T20:43:59.927Z
David Eppstein
<p>I stumbled on an open problem posed by <a href="http://www.ics.uci.edu/~theory/269/020125.pdf">David Eppstein</a> and I am interested in its complexity status. He conjectured that it is NP-complete.</p>

<p>Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’s and 1’s</p>

<p>Question:  Is there a path through adjacent matrix entries, covering each matrix entry exactly once, with values matching the given sequence?</p>

<blockquote>
  <p>Did anyone prove that the problem is indeed hard?</p>
</blockquote>

<cc.complexity-theory><graph-theory>
Hidden path in square grids
Mohammad Al-Turkistany
# Hidden path in square grids

(Asked by: username_0 on 2014-06-27)

I stumbled on an open problem posed by [username_1](http://www.ics.uci.edu/~theory/269/020125.pdf) and I am interested in its complexity status. He conjectured that it is NP-complete.

Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’s and 1’s

Question: Is there a path through adjacent matrix entries, covering each matrix entry exactly once, with values matching the given sequence?

> Did anyone prove that the problem is indeed hard?

**Tags:** cc.complexity-theory, graph-theory


---

## 1 answers

### Answer by username_1 on 2014-06-27. Score: 12 | Accepted answer

I received an email last February from a Spanish undergraduate, Nil Mamano, with a proof that this problem is indeed NP-complete, by reduction from Hamiltonian path in grid graphs. I don't know that it has been published anywhere yet. The reduction replaces each vertex of the grid graph by a 2x2 block of 1's, and each edge, face, or missing vertex by a 2x2 block of 0's. The input sequence alternates between subsequences of four 1's and four 0's for as many times as is needed to cover all the vertices, then fills out the rest of the sequence with 0's. To match the input sequence, a path through the grid must align the subsequences of four 1's with the 2x2 blocks of 1's from the reduction, forming a Hamiltonian path; if such a path exists, it's always possible to do this in a way that allows the rest of the matrix to be covered by the remaining zeros at the end of the sequence.


---

