knight_tour.py

# Knight Tour Intro: https://www.youtube.com/watch?v=ab_dY3dZFHM

from __future__ importannotations


defget_valid_pos(position: tuple[int, int], n: int) ->list[tuple[int, int]]:
"""
 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)]
 """

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= []

forinner_positioninpositions:
y_test, x_test=inner_position
if0<=y_test<nand0<=x_test<n:
permissible_positions.append(inner_position)

returnpermissible_positions


defis_complete(board: list[list[int]]) ->bool:
"""
 Check if the board (matrix) has been completely filled with non-zero values.

 >>> is_complete([[1]])
 True

 >>> is_complete([[1, 2], [3, 0]])
 False
 """

returnnotany(elem==0forrowinboardforeleminrow)


defopen_knight_tour_helper(
board: list[list[int]], pos: tuple[int, int], curr: int
) ->bool:
"""
 Helper function to solve knight tour problem.
 """

ifis_complete(board):
returnTrue

forpositioninget_valid_pos(pos, len(board)):
y, x=position

ifboard[y][x] ==0:
board[y][x] =curr+1
ifopen_knight_tour_helper(board, position, curr+1):
returnTrue
board[y][x] =0

returnFalse


defopen_knight_tour(n: int) ->list[list[int]]:
"""
 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
 """

board= [[0foriinrange(n)] forjinrange(n)]

foriinrange(n):
forjinrange(n):
board[i][j] =1
ifopen_knight_tour_helper(board, (i, j), 1):
returnboard
board[i][j] =0

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


if__name__=="__main__":
importdoctest

doctest.testmod()