Knight's Tour
A solution to the Knight's Tour.
Solution
""" knights_tour.py """
# usage: python3 knights_tour 8 1
import sys
def image(n, data):
""" visualise n x n board with data """
output = '\033[2J\033[H'
for i in range(n):
output += ' '.join(data[i * n: (i + 1) * n] + ['\n'])
return output
def where_to(p, n):
""" moves possible from p on n x n board """
distinct_moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
(2, -1), (2, 1), (1, -2), (1, 2)]
row, col = divmod(p, n)
squares = []
for dy, dx in distinct_moves:
r, c = row + dy, col + dx
if any([r < 0, c < 0, n - 1 < r, n - 1 < c]):
continue
squares.append(r * n + c)
return squares
size, start = map(int, sys.argv[1:3])
assert start < size * size
board = ['..' for _ in range(size * size)]
positions = []
pos = start
while len(positions) != size * size:
if board[pos] == '..':
possible = where_to(pos, size)
positions.append((pos, possible))
board[pos] = f'{len(positions):02}'
print(image(size, board))
while not positions[-1][1]:
pos, _ = positions.pop()
board[pos] = '..'
if not positions:
break
if positions:
pos = positions[-1][1].pop()
else:
break
print([i for i, _ in positions])