Sliding Puzzle Problem

class SlidingPuzzle:
    def __init__(self, board, goal=None):
        self.board = board
        self.size = len(board)
        self.goal = goal if goal is not None else self._generate_goal()

    def _generate_goal(self):
        goal = []
        for i in range(self.size):
            row = []
            for j in range(self.size):
                if i == self.size - 1 and j == self.size - 1:
                    row.append(0)  # The empty space
                else:
                    row.append(i * self.size + j + 1)
            goal.append(row)
        return goal

    def is_solved(self):
        return self.board == self.goal

    def find_empty(self):
        for i, row in enumerate(self.board):
            for j, val in enumerate(row):
                if val == 0:
                    return (i, j)
        raise ValueError("No empty (0) tile found on the board")

    def get_possible_moves(self, empty_pos):
        i, j = empty_pos
        moves = []
        # Order: right, down, left, up to match typical neighbor listing
        candidates = [(i, j+1), (i+1, j), (i, j-1), (i-1, j)]
        for r, c in candidates:
            if 0 <= r < self.size and 0 <= c < self.size:
                moves.append((r, c))
        return moves

    def _swap(self, board, pos_a, pos_b):
        (i1, j1), (i2, j2) = pos_a, pos_b
        board[i1][j1], board[i2][j2] = board[i2][j2], board[i1][j1]

    def neighbour_states(self):
        neighbors = []
        empty_pos = self.find_empty()
        possible_moves = self.get_possible_moves(empty_pos)

        for move in possible_moves:
            new_board = [row[:] for row in self.board]
            self._swap(new_board, empty_pos, move)
            neighbors.append(SlidingPuzzle(new_board, self.goal))

        return neighbors

    def misplaced_tiles(self):
        count = 0
        for i in range(self.size):
            for j in range(self.size):
                if self.board[i][j] != 0 and self.board[i][j] != self.goal[i][j]:
                    count += 1
        return count

    def print_board(self):
        for row in self.board:
            print(' '.join(str(cell) for cell in row))

def solve_hill_climbing(initial_puzzle, max_iterations=1000):
    """
    Solves a SlidingPuzzle using steepest-ascent hill climbing.

    Args:
        initial_puzzle (SlidingPuzzle): The starting state of the puzzle.
        max_iterations (int): A safeguard against infinite loops.

    Returns:
        list[SlidingPuzzle]: The path of states from start to finish (or local minimum).
    """
    current_puzzle = initial_puzzle
    current_heuristic = current_puzzle.misplaced_tiles()
    
    path = [current_puzzle]

    for i in range(max_iterations):
        # 1. Check if we have reached the goal
        if current_puzzle.is_solved():
            print(f"🎉 Solved in {len(path) - 1} moves!")
            return path

        # 2. Get all neighbors
        neighbors = current_puzzle.neighbour_states()

        if not neighbors:
            print("No neighbors found. Stuck.")
            break 

        best_neighbor = None
        best_heuristic = current_heuristic

        for neighbor in neighbors:
            neighbor_heuristic = neighbor.misplaced_tiles()
            
            # If this neighbor is strictly better, it's our new best candidate
            if neighbor_heuristic < best_heuristic:
                best_heuristic = neighbor_heuristic
                best_neighbor = neighbor

        # 4. Check if we are stuck at a local minimum
        if best_neighbor is None:
            # We didn't find any neighbor with a *better* (lower) heuristic.
            print(f"🛑 Stuck at a local minimum after {len(path) - 1} moves.")
            print("Current state (h={current_heuristic}):")
            current_puzzle.print_board()
            return path

        # 5. Move to the best neighbor
        current_puzzle = best_neighbor
        current_heuristic = best_heuristic
        path.append(current_puzzle)

    # 6. If we're here, we hit the iteration limit
    print(f"⚠️ Failed to solve within {max_iterations} iterations.")
    return path

if __name__ == "__main__":
    
    # 1. A board that is solvable with hill climbing
    print("--- Example 1: Solvable Puzzle ---")
    # Goal is:
    # 1 2 3
    # 4 5 6
    # 7 8 0
    start_board_solvable = [
        [1, 2, 3],
        [4, 0, 5],  # 3 misplaced tiles (0, 5, 6)
        [7, 8, 6]
    ]
    
    puzzle1 = SlidingPuzzle(start_board_solvable)
    
    print("Starting Board (h={puzzle1.misplaced_tiles()}):")
    puzzle1.print_board()
    
    solution_path1 = solve_hill_climbing(puzzle1)
    
    print("\nFinal Board:")
    if solution_path1:
        solution_path1[-1].print_board()

    print("\n" + "="*30 + "\n")

    # 2. A board that gets stuck in a local minimum
    print("--- Example 2: Local Minimum Puzzle ---")
    start_board_stuck = [
        [1, 2, 3],
        [5, 4, 6],  # 2 misplaced tiles (4, 5)
        [7, 8, 0]
    ]

    puzzle2 = SlidingPuzzle(start_board_stuck)
    
    print("Starting Board (h={puzzle2.misplaced_tiles()}):")
    puzzle2.print_board()
    
    solution_path2 = solve_hill_climbing(puzzle2)
    
    print("\nFinal Board (Stuck):")
    if solution_path2:
        solution_path2[-1].print_board()