# Longest path in grid like graph

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

• I believe the SO problem has a rectangular grid (width $\times$ height), and the grid squares are filled with numbers, so not so sure. If the problem is a general sub-graph of numbers, then I believe your assertion of NP-Hardness might be true. Given a grid graph (whose hamiltonian path we want), replace a grid square with a $3\times3$ square and fill it with $$0 1 0$$ $$1 1 1$$ $$0 1 0$$ and I believe you have a reduction to this problem (haven't tried proving anything, though). Commented May 24, 2013 at 7:15