Finding all paths in an array of numbers satisfying certain properties.

gistfile1.py

def neighbours(a, x, y):
    xs = []
    ys = []
    if x > 0:
        xs.append(-1)
    xs.append(0)
    if x < len(a[0]) - 1:
        xs.append(1)
    if y > 0:
        ys.append(-1)
    ys.append(0)
    if y < len(a) - 1:
        ys.append(1)
    for x1 in xs:
        for y1 in ys:
            if x1 != 0 or y1 != 0:
                yield (x+x1, y+y1)

def generate_all_paths_from(a, X, Y, stack, f = lambda a, s, x, y : True, final = lambda a, s, x, y : True):
    hadneighbour = False
    s = stack[:] + [(X,Y)]
    for (x, y) in neighbours(a, X, Y):
        if (x, y) not in stack:
            if f(a, s, x, y):
                for p in generate_all_paths_from(a, x, y, s, f, final):
                    hadneighbour = True
                    yield [(X, Y)] + p
    if final(a, s, X, Y):
        yield [(X, Y)]

def generate_all_paths(a, f = lambda a, s, x, y : True, final = lambda a, s, x, y : True):
    for x in xrange(len(a[0])):
        for y in xrange(len(a)):
            for p in generate_all_paths_from(a, x, y, [], f, final):
                yield p

def is_growing(a, s, x, y):
    if not s:
        return True
    lastelem = a[s[-1][1]][s[-1][0]]
    newelem = a[y][x]
    return newelem > lastelem

N = 3
from random import sample
arr = [sample([_ for _ in xrange(N*N)], N) for i in xrange(N)]
print arr

for p in generate_all_paths(arr, is_growing, lambda a, s, x, y : a[y][x]%2==0):
    print [arr[y][x] for (x,y) in p]