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$?

If all numbers are distinct then you can find the longest path using straightforward dynamic programming. The general problem is probably NP-complete, since deciding whether a grid graph has a Hamilton path is NP-complete, as shown by Itai, Papadimitriou and Szwarcfiter. Grid graphs are finite induced subgraphs of the infinite rectangular grid, in which non-diagonal cells are not adjacent; however it seems reasonable to conjecture that Hamilton path is NP-complete also for finite subgraphs of the infinite rectangular grid with diagonals. Given that, it is likely that your problem is also NP-complete.

StackExchange Computer Science Q#12239, answer score: 3