Untitled

import chess
from collections import deque

def BFS(board: chess.Board, goal_position: chess.Square):
    """
    Implements the Breadth-First Search (BFS) algorithm for the Knight Errant Problem.
    
    Parameters:
    - board: A chess.Board object representing the current board state.
    - goal_position: The target square where the knight needs to move (H8).
    
    Returns:
    A list of squares (as integers) visited in the order they were expanded.
    """
    # Get the knight's starting position (A1 = 0)
    start_position = 0  # Knight starts at A1 which corresponds to 0
    
    # Initialize the queue for BFS
    queue = deque([start_position])
    visited_nodes_in_order = []  # This will store the tiles visited in order
    visited = set([start_position])  # Set to track visited squares
    
    # Loop until queue is empty (BFS loop)
    while queue:
        current_square = queue.popleft()  # Get the current tile
        
        # Add to visited order list
        visited_nodes_in_order.append(current_square)
        
        # Check if we've reached the goal
        if current_square == goal_position:
            break
        
        # Temporarily place the knight at the current square
        board.clear()  # Clear the board to ensure only the knight moves
        board.set_piece_at(current_square, chess.Piece(chess.KNIGHT, chess.WHITE))  # Place knight at current square
        
        # Explore all legal knight moves from the current position
        legal_moves = list(board.legal_moves)
        
        # Expand knight moves and enqueue unvisited tiles
        for move in legal_moves:
            next_square = move.to_square
            if next_square not in visited:
                visited.add(next_square)
                queue.append(next_square)

    return visited_nodes_in_order