sandwich2.py

def solve1(n, a):
    s = n + 1
    for p in range(len(a) - 2 * s):
        if a[p] + a[p + s] + a[p + s + s] == 0:
            a[p] = a[p + s] = a[p + s + s] = n
            if n > 1:
                solve1(n - 1, a)
            else:
                print(''.join(map(str, a)))
            a[p] = a[p + s] = a[p + s + s] = 0


def solve(n):
    solve1(n, [0] * n * 3)


solve(9)