Strictly Increasing Path in Grid with Python

At each step we can go the one of the left,right,up or down cells only if the that cell is strictly greater thab our current cell. (We cannot move diagonally). We want to find all the paths that we can go from the top-left cell to the bottom-right cell.

[[1,4,3], [5,6,7]]

In our example, these paths are 1->4->6->7 and 1->5->6->7.

How can i solve it in reversible use?

Answer

First, note that the number of such paths is exponential (in the size of the graph).

For example, look at the graph:

1    2     3   ... n
2    3     4   ... n+1
3    4     5   ... n+2
...
n  (n+1) (n+2) ... 2n

In here, you have exactly n rights and n down – which gives you exponential number of such choices – what makes “efficient” solution irrelevant (as you stated, you are looking for all paths).

One approach to find all solutions, is using a variation of DFS, where you can go to a neighbor cell if and only if it’s strictly higher.

It should look something like:

def Neighbors(grid, current_location):
  """returns a list of up to 4 tuples neighbors to current location"""
  pass  # Implement it, should be straight forward

# Note: Using a list as default value is problematic, don't do it in actual code.
def PrintPaths(grid, current_path = [(0,0)], current_location = (0, 0)):
  """Will print all paths with strictly increasing values.
  """
  # Stop clause: if got to the end - print current path.
  if current_location[0] == len(grid) and current_location[1] == len(grid[current_location[0]):
    print(current_path)
    return
  # Iterate over all valid neighbors:
  for next in Neighbors(grid, current_location):
    if grid[current_location[0]][current_location[1]] < grid[next[0]][next[1]]:
    current_path = current_path + next
    PrintPaths(grid, current_path, next)
    # When getting back here, all that goes through prefix + next are printed.
    # Get next out of the current path
    current_path.pop()