Find the longest rectilinear path in a matrix with descending entries
As I said in the comment, it's probably faster to get the local minima and check the paths that start from those points. You can then get the path with the maximum length and reverse the points if you want the descending path.

I haven't tested this a lot, but it takes less than a second on my pc with a 4x4 matrix.

Here's the code (again, I've only tested this with a few inputs and there's a bit of code duplication, take it as a general guideline):

def get_next_ascending_value(row, column, matrix, size):
    current_value = matrix[row][column]
    max_steepness = -1
    coords = []
    if (column &gt; 0) and (matrix[row][column-1] &gt; current_value):
        if max_steepness &lt; matrix[row][column-1]:
            max_steepness = matrix[row][column-1]
            coords = [row, column-1]
    if (row &gt; 0) and (matrix[row-1][column] &gt; current_value):
        if max_steepness &lt; matrix[row-1][column]:
            max_steepness = matrix[row-1][column]
            coords = [row-1, column]
    if (column &lt; size - 1) and (matrix[row][column+1] &gt; current_value):
        if max_steepness &lt; matrix[row][column+1]:
            max_steepness = matrix[row][column+1]
            coords = [row, column+1]
    if (row &lt; size - 1) and (matrix[row+1][column] &gt; current_value):
        if max_steepness &lt; matrix[row+1][column]:
            max_steepness = matrix[row+1][column]
            coords = [row+1, column]

    return coords


def is_local_minimum(row, column, matrix, size):
    current_value = matrix[row][column]
    if (column &gt; 0) and (matrix[row][column-1] &lt; current_value):
        return False
    if (row &gt; 0) and (matrix[row-1][column] &lt; current_value):
        return False
    if (column &lt; size - 1) and (matrix[row][column+1] &lt; current_value):
        return False
    if (row &lt; size - 1) and (matrix[row+1][column] &lt; current_value):
        return False

    return True

def get_local_minimum(matrix, size):
    for row in range(len(matrix)):
        for column in range(size):
            if is_local_minimum(row, column, matrix, size):
                yield [row, column]

# [4, 5, 6]
# [1, 1, 6]
# [4, 5, 6]

# starting_matrix = [[4, 5, 6],[1, 1, 6],[4, 5, 6]]
# size = 3

# [4, 5]
# [1, 1]

# starting_matrix = [[4, 5],[1, 1]]
# size = 2


# [4, 5, 7, 9]
# [1, 1, 2, 5]
# [4, 5, 7, 9]
# [1, 1, 2, 5]

starting_matrix = [[4, 5, 7, 9],[1, 1, 2, 5],[4, 5, 7, 9],[1, 1, 2, 5]]
size = 4

for coords in get_local_minimum(starting_matrix, size):
    print(coords, starting_matrix[coords[0]][coords[1]])
    next_coords = get_next_ascending_value(coords[0], coords[1], starting_matrix, size)
    while (len(next_coords) &gt; 0):
        print(next_coords, starting_matrix[next_coords[0]][next_coords[1]])
        next_coords = get_next_ascending_value(next_coords[0], next_coords[1], starting_matrix, size)
    print('---')