Python Homework Help - Python Logical Puzzles, Games, and Algorithms: Knight Tour

Python Homework Help

Python Homework Question

Python Logical Puzzles, Games, and Algorithms: Knight Tour

Python Homework Solution

Here's an example Python program for the Knight Tour problem using a backtracking algorithm:
class KnightTour:
    def __init__(self, board_size):
        self.board = [[0] * board_size for _ in range(board_size)]
        self.moves = ((2, 1), (1, 2), (-1, 2), (-2, 1),
                      (-2, -1), (-1, -2), (1, -2), (2, -1))

    def solve(self):
        if self._solve(0, 0, 1):
            self.print_board()
        else:
            print("No solution found.")

    def _solve(self, row, col, move):
        if move == len(self.board) ** 2 + 1:
            return True

        for m in self.moves:
            next_row = row + m[0]
            next_col = col + m[1]

            if 0 <= next_row < len(self.board) and 0 <= next_col < len(self.board[0]) \
                    and self.board[next_row][next_col] == 0:
                self.board[next_row][next_col] = move

                if self._solve(next_row, next_col, move + 1):
                    return True

                self.board[next_row][next_col] = 0

        return False

    def print_board(self):
        for row in self.board:
            for col in row:
                print(str(col).rjust(2), end=' ')
            print()

if __name__ == '__main__':
    kt = KnightTour(5)
    kt.solve()
This program creates a KnightTour class that contains a 2D array representing the chessboard and a set of moves that a knight can make. The solve method initializes the starting position of the knight and calls the _solve method to recursively check all possible moves until a solution is found or no moves are left. The _solve method uses backtracking to explore all possible moves and tries to find a solution. If a solution is found, the print_board method is called to print the chessboard with the knight's path.