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])

Last posts

  1. Eight Queens Puzzle
  2. Day 12 - Advent of Code 2023
  3. Day 10 - Advent of Code 2023
  4. Sorting It Out
  5. Back to the Checkout