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.