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