iframe-proxy | Sunbelt Computer Software

History

100 lines (72 loc) · 2.35 KB

Raw

100

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

from typing import List, Tuple

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

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:

"""

Check if the board (matrix) has been completely filled with non-zero values.

>>> is_complete([[1]])

True

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

False

"""

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:

"""

Helper function to solve knight tour problem.

"""

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

"""

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 Kight Tour cannot be performed on a board of size 2

"""

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

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

if __name__ == "__main__":

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

knight_tour.py

Latest commit

History

knight_tour.py

File metadata and controls