BFS_Solver.py

from Game import Game
from BaseSolver import BaseSolver
from typing import Optional
from collections import deque

class BFS_Solver(BaseSolver):
    
    def __init__(self, initial_game: Game, max_nodes=None):
        super().__init__(initial_game, max_nodes)
        self.max_queue_size = 0
    
    def solve(self) -> Optional[Game]:
        print("\nStarting BFS Search...")
        print(f"Board: {self.initial_game.board.rows}x{self.initial_game.board.cols}, Colors: {len(self.initial_game.board.positions)}")
        
        self.visited_count = 0
        self.max_queue_size = 0
        self.solution_found = None
        self.solution_path = []
        self.parent_map = {}
        
        self.initial_game.visited_states.clear()
        result = self._bfs_iterative()
        
        print(f"\nBFS Complete: {self.visited_count:,} states visited, max queue: {self.max_queue_size:,}")
        
        if result:
            print("Solution found!")
            return result
        else:
            print("No solution found")
            return None
    
    def _bfs_iterative(self) -> Optional[Game]:
        queue = deque()
        queue.append(self.initial_game)
        self.initial_game.MarkAsVisited()
        
        state_hash = self._hash_state(self.initial_game)
        self.parent_map[state_hash] = None
        
        while queue:
            if self.visited_count >= self.max_nodes:
                return None
            
            if len(queue) > self.max_queue_size:
                self.max_queue_size = len(queue)
            
            current_state = queue.popleft()
            self.visited_count += 1
            
            if current_state.IsFinalState():
                self.solution_found = current_state
                self._reconstruct_path(current_state)
                return current_state
            
            current_hash = self._hash_state(current_state)
            next_states = current_state.GetPossibleMoves()
            
            for next_state in next_states:
                next_state.MarkAsVisited()
                queue.append(next_state)
                
                next_hash = self._hash_state(next_state)
                self.parent_map[next_hash] = current_state
        
        return None