The problem:
Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$)
Output:
YES if there exists a path through adjacent matrix entries $\dagger$, starting at pos, covering each matrix entry with a 1 exactly once, and not covering the matrix entries with a 0.
NO otherwise.
$\dagger$ a matrix entry is adjacent to the one immediately to its left, to the one immediately to its right, to the one immediately upwards and the one immediately below.
Informally, the matrix can be seen as a labyrinth where the 0's are walls, you start somewhere, and you have to walk through the whole maze without repeating any position.
Example input:
1100
1100
0000
0001
Pos: (1,1)
Corresponding output:
No (because you can't reach the position (4,4))
Is this problem NP-complete? If it is, what other NP-complete problem has been reduced to it? If it isn't, what approach can I use to design an efficient algorithm?
I think this is a particular case of the hamiltonian path problem (except that you have a fixed starting point). The graph can be constructed by taking the matrix entries with 1's as vertices. 2 vertices are adjacent iff their corresponding matrix entries are adjacent. So I think that reducing this problem to the hamiltonian path problem should be easy. Of course, to prove it is NP-complete, we would have to do the reduction backwards.
