Implementation of the knights tour algorithm in Python

knights_tour.py

from typing import List, Optional, Tuple

Square = Tuple[int, int]

SIZE = 8
assert SIZE <= 20, "Too large a size will overflow the stack"


def next_possible_squares(x: int, y: int, squares: List[Square]) -> List[Square]:
    """Determine the next possible valid squares based on the current square and the previously visited squares.

    This works by generating all possible squares, then filtering out those which
    have already been visited.

    :param x: The x coordinate of the current location
    :param y: The y coordinate of the current location
    :param square: The list of previously visited squares

    :returns: The list of next valid squares
    """

    # Generate all possible squares
    output = []
    output.append((x - 1, y - 2))
    output.append((x + 1, y - 2))
    output.append((x - 2, y - 1))
    output.append((x + 2, y - 1))
    output.append((x - 1, y + 2))
    output.append((x + 1, y + 2))
    output.append((x - 2, y + 1))
    output.append((x + 2, y + 1))

    valid_output = []
    for px, py in output:

        # Filter out those which lie outside the board
        if px < 0 or px >= SIZE or py < 0 or py >= SIZE:
            continue

        # Filter out those which have already been visited
        if (px, py) not in squares:
            valid_output.append((px, py))

    return valid_output


def tour(squares: List[Square]) -> Optional[List[Square]]:
    """Continue the tour of the board based from the existing visited locations.

    We look at all possible moves, then try each one recursively. If the tour
    is complete, we return the squares, otherwise, we return None and that path
    can be marked as a failure.

    Note: This algorithm makes use of Warnsdorff's algorithm as a heuristic to
    speed up the search. This can solve a 20x20 board in under a second. Without
    the algorithm, even a 5x5 board takes longer, despite being 16 times
    smaller.

    :param squares: The list of squares that have already been visited.

    :returns: The list of squares in order if the tour is complete, None otherwise
    """

    # If the tour is complete, return the result
    if len(squares) >= SIZE * SIZE:
        return squares

    # Generate the valid possible next squares
    potential_next_squares = next_possible_squares(*squares[-1], squares)

    # Sort them according to possible next squares (i.e. Warnsdorff's algorithm)
    potential_next_squares.sort(
        key=lambda square: len(next_possible_squares(*square, squares))
    )

    # If there are no possible next squares, this path was a failure
    if len(potential_next_squares) == 0:
        return None

    # Try each potential next square recursively
    for potential_next_square in potential_next_squares:
        new_squares = tour(squares + [potential_next_square])
        if new_squares:
            return new_squares

    # If we didn't find a path based on each possible next square, then this
    # path was a failure
    return None


def main() -> None:

    # Start at (0,0) and find the tour
    result = tour([(0, 0)])

    # Render the result
    board = []

    for i in range(SIZE):
        board.append([0] * SIZE)

    for index, (x, y) in enumerate(result):
        board[y][x] = index

    print()
    for row in board:
        print(row)


if __name__ == "__main__":
    main()