knight tour intro https www youtube comwatch vabdy3dzfhm find all the valid positions a knight can move to from the current position getvalidpos1 3 4 2 1 0 1 3 2 check if the board matrix has been completely filled with nonzero values iscomplete1 true iscomplete1 2 3 0 false helper function to solve knight tour problem find the solution for the knight tour problem for a board of size n raises valueerror if the tour cannot be performed for the given size openknighttour1 1 openknighttour2 traceback most recent call last valueerror open knight tour cannot be performed on a board of size 2 knight tour intro https www youtube com watch v ab_dy3dzfhm find all the valid positions a knight can move to from the current position get_valid_pos 1 3 4 2 1 0 1 3 2 check if the board matrix has been completely filled with non zero values is_complete 1 true is_complete 1 2 3 0 false helper function to solve knight tour problem find the solution for the knight tour problem for a board of size n raises valueerror if the tour cannot be performed for the given size open_knight_tour 1 1 open_knight_tour 2 traceback most recent call last valueerror open knight tour cannot be performed on a board of size 2
from __future__ import annotations


def get_valid_pos(position: tuple[int, int], n: int) -> list[tuple[int, int]]:
    

    y, x = position
    positions = [
        (y + 1, x + 2),
        (y - 1, x + 2),
        (y + 1, x - 2),
        (y - 1, x - 2),
        (y + 2, x + 1),
        (y + 2, x - 1),
        (y - 2, x + 1),
        (y - 2, x - 1),
    ]
    permissible_positions = []

    for position in positions:
        y_test, x_test = position
        if 0 <= y_test < n and 0 <= x_test < n:
            permissible_positions.append(position)

    return permissible_positions


def is_complete(board: list[list[int]]) -> bool:
    

    return not any(elem == 0 for row in board for elem in row)


def open_knight_tour_helper(
    board: list[list[int]], pos: tuple[int, int], curr: int
) -> bool:
    

    if is_complete(board):
        return True

    for position in get_valid_pos(pos, len(board)):
        y, x = position

        if board[y][x] == 0:
            board[y][x] = curr + 1
            if open_knight_tour_helper(board, position, curr + 1):
                return True
            board[y][x] = 0

    return False


def open_knight_tour(n: int) -> list[list[int]]:
    

    board = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            board[i][j] = 1
            if open_knight_tour_helper(board, (i, j), 1):
                return board
            board[i][j] = 0

    msg = f"Open Knight Tour cannot be performed on a board of size {n}"
    raise ValueError(msg)


if __name__ == "__main__":
    import doctest

    doctest.testmod()