def n_possible(x, y, st):
n = 0
if 1 <= x + 2 <= len(pole[0]) and 1 <= y + 1 <= len(pole) and [x + 2, y + 1] not in sol and [x + 2, y + 1] not in neg[st]:
n += 1
if 1 <= x + 2 <= len(pole[0]) and 1 <= y - 1 <= len(pole) and [x + 2, y - 1] not in sol and [x + 2, y - 1] not in neg[st]:
n += 1
if 1 <= x - 2 <= len(pole[0]) and 1 <= y + 1 <= len(pole) and [x - 2, y + 1] not in sol and [x - 2, y + 1] not in neg[st]:
n += 1
if 1 <= x - 2 <= len(pole[0]) and 1 <= y - 1 <= len(pole) and [x - 2, y - 1] not in sol and [x - 2, y - 1] not in neg[st]:
n += 1
if 1 <= x + 1 <= len(pole[0]) and 1 <= y + 2 <= len(pole) and [x + 1, y + 2] not in sol and [x + 1, y + 2] not in neg[st]:
n += 1
if 1 <= x + 1 <= len(pole[0]) and 1 <= y - 2 <= len(pole) and [x + 1, y - 2] not in sol and [x + 1, y - 2] not in neg[st]:
n += 1
if 1 <= x - 1 <= len(pole[0]) and 1 <= y + 2 <= len(pole) and [x - 1, y + 2] not in sol and [x - 1, y + 2] not in neg[st]:
n += 1
if 1 <= x - 1 <= len(pole[0]) and 1 <= y - 2 <= len(pole) and [x - 1, y - 2] not in sol and [x - 1, y - 2] not in neg[st]:
n += 1
return n
def posible_steps(x,y,st):
posible.clear()
max_pos=[0,0]
n=0
if 1 <= x + 2 <= len(pole[0]) and 1 <= y + 1 <= len(pole) and [x + 2, y + 1] not in sol and [x + 2, y + 1] not in neg[st]:
posible.append([x+2,y+1])
n+=1
if 1 <= x + 2 <= len(pole[0]) and 1 <= y - 1 <= len(pole) and [x + 2, y - 1] not in sol and [x + 2, y - 1] not in neg[st]:
posible.append([x+2,y-1])
n += 1
if 1 <= x - 2 <= len(pole[0]) and 1 <= y + 1 <= len(pole) and [x - 2, y + 1] not in sol and [x - 2, y + 1] not in neg[st]:
posible.append([x-2,y+1])
n += 1
if 1 <= x - 2 <= len(pole[0]) and 1 <= y - 1 <= len(pole) and [x - 2, y - 1] not in sol and [x - 2, y - 1] not in neg[st]:
posible.append([x-2,y-1])
n += 1
if 1 <= x + 1 <= len(pole[0]) and 1 <= y + 2 <= len(pole) and [x + 1, y + 2] not in sol and [x + 1, y + 2] not in neg[st]:
posible.append([x + 1, y + 2])
n += 1
if 1 <= x + 1 <= len(pole[0]) and 1 <= y - 2 <= len(pole) and [x + 1, y - 2] not in sol and [x + 1, y - 2] not in neg[st]:
posible.append([x + 1, y - 2])
n += 1
if 1 <= x - 1 <= len(pole[0]) and 1 <= y + 2 <= len(pole) and [x - 1, y + 2] not in sol and [x - 1, y + 2] not in neg[st]:
posible.append([x - 1, y + 2])
n += 1
if 1 <= x - 1 <= len(pole[0]) and 1 <= y - 2 <= len(pole) and [x - 1, y - 2] not in sol and [x - 1, y - 2] not in neg[st]:
posible.append([x - 1, y - 2])
n += 1
print(posible)
return n
global pole, k, sol, neg, posible
posible=[]
sol = []
steps = 0
pole_x, pole_y = input("Enter your board dimensions: ").split()
pole_x, pole_y = int(pole_x), int(pole_y)
neg = {a: [] for a in range(1, pole_x * pole_y+1)}
k = len(str(pole_x * pole_y))
pole = [["_" * k for i in range(pole_x)] for j in range(pole_y)]
x, y = input("Enter the knight's starting position: ").split()
x, y = int(x), int(y)
sol.append([x, y])
st = 1
while st < pole_x * pole_y:
posible_steps(x, y, st)
max_posible = 0
max_pos = [0, 0]
for coord in posible:
n_pos = n_possible(coord[0], coord[1], st)
if n_pos - 1 > max_posible:
max_posible = n_pos
max_pos = coord
if not max_posible or not posible:
st -= 1
neg[st].append(sol.pop())
else:
st += 1
sol.append(max_pos)
x, y = max_pos[0], max_pos[1]
print(sol)