pad = [
"123",
"456",
"789",
" 0 "
]
def valid(i, j):
if i >= 4 or i < 0 or j < 0 or j >= 3:
return False
return (pad[i][j] != ' ')
delta_x = [-1, 1, 0, 0]
delta_y = [0, 0, -1, 1]
def f(d, n):
if n == 1:
return [d]
if n <= 0:
return []
x = None; y = None
# The following line of code can be replaced by a dict lookup which
# stores the indices of every digit, say { 5: (1, 1), 1: (0, 0) .. }
for i in range(0,4):
for j in range(0,3):
if pad[i][j] == str(d):
x = i; y = j
digits = []
for i in range(0,4):
next_x = x + delta_x[i]
next_y = y + delta_y[i]
if valid(next_x, next_y):
digits.extend(f(pad[next_x][next_y], n - 1))
return [str(d) + str(w) for w in digits]
print(f(5, 1))
print(f(1, 3))
print(f(0, 3))
cGFkID0gWwoJIjEyMyIsCgkiNDU2IiwKCSI3ODkiLAoJIiAwICIKXQoKZGVmIHZhbGlkKGksIGopOgoJaWYgaSA+PSA0IG9yIGkgPCAwIG9yIGogPCAwIG9yIGogPj0gMzoKCQlyZXR1cm4gRmFsc2UKCXJldHVybiAocGFkW2ldW2pdICE9ICcgJykKCQkKZGVsdGFfeCA9IFstMSwgMSwgMCwgMF0KZGVsdGFfeSA9IFswLCAwLCAtMSwgMV0KIApkZWYgZihkLCBuKToKCWlmIG4gPT0gMToKCQlyZXR1cm4gW2RdCglpZiBuIDw9IDA6CgkJcmV0dXJuIFtdCgkJCgl4ID0gTm9uZTsgeSA9IE5vbmUKCQoJIyBUaGUgZm9sbG93aW5nIGxpbmUgb2YgY29kZSBjYW4gYmUgcmVwbGFjZWQgYnkgYSBkaWN0IGxvb2t1cCB3aGljaAoJIyBzdG9yZXMgdGhlIGluZGljZXMgb2YgZXZlcnkgZGlnaXQsIHNheSB7IDU6ICgxLCAxKSwgMTogKDAsIDApIC4uIH0KCWZvciBpIGluIHJhbmdlKDAsNCk6CgkJZm9yIGogaW4gcmFuZ2UoMCwzKToKCQkJaWYgcGFkW2ldW2pdID09IHN0cihkKToKCQkJCXggPSBpOyB5ID0gagoKCWRpZ2l0cyA9IFtdCglmb3IgaSBpbiByYW5nZSgwLDQpOgoJCW5leHRfeCA9IHggKyBkZWx0YV94W2ldCgkJbmV4dF95ID0geSArIGRlbHRhX3lbaV0KCQlpZiB2YWxpZChuZXh0X3gsIG5leHRfeSk6CgkJCWRpZ2l0cy5leHRlbmQoZihwYWRbbmV4dF94XVtuZXh0X3ldLCBuIC0gMSkpCgkKCXJldHVybiBbc3RyKGQpICsgc3RyKHcpIGZvciB3IGluIGRpZ2l0c10KCnByaW50KGYoNSwgMSkpCnByaW50KGYoMSwgMykpCnByaW50KGYoMCwgMykp