Hill Climb

 import copy

# Function to calculate the Manhattan distance heuristic (h2)

def manhattan_distance(state, goal_state):

    distance = 0

    for i in range(3):

        for j in range(3):

            current_value = state[i][j]

            if current_value != 'B':  # Skip the blank tile

                goal_pos = find_position(goal_state, current_value)

                distance += abs(i - goal_pos[0]) + abs(j - goal_pos[1])

    return distance

# Function to calculate misplaced tiles heuristic (h1)

def misplaced_tiles(state, goal_state):

    misplaced = 0

    for i in range(3):

        for j in range(3):

            if state[i][j] != goal_state[i][j] and state[i][j] != 'B':

                misplaced += 1

    return misplaced

# Function to find the position of a tile in the goal state

def find_position(state, value):

    for i in range(3):

        for j in range(3):

            if state[i][j] == value:

                return (i, j)

    return None

# Function to get all possible moves (new states) for the blank tile

def get_neighbors(state):

    neighbors = []

    blank_pos = find_position(state, 'B')

    i, j = blank_pos

    moves = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]  # Up, Down, Left, Right

    

    for new_i, new_j in moves:

        if 0 <= new_i < 3 and 0 <= new_j < 3:

            new_state = copy.deepcopy(state)

            # Swap the blank tile with the neighbor tile

            new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]

            neighbors.append(new_state)

    

    return neighbors

# Function to perform Hill Climbing Search

def hill_climbing(initial_state, goal_state, heuristic):

    current_state = initial_state

    if heuristic == 'h1':

        calc_heuristic = misplaced_tiles

    elif heuristic == 'h2':

        calc_heuristic = manhattan_distance

    else:

        print("Invalid heuristic!")

        return

    # Loop until we reach the goal or there are no more moves

    while True:

        neighbors = get_neighbors(current_state)

        # Calculate heuristic for each neighbor

        neighbor_heuristics = [(neighbor, calc_heuristic(neighbor, goal_state)) for neighbor in neighbors]

        

        # Sort neighbors by heuristic value (ascending order)

        neighbor_heuristics.sort(key=lambda x: x[1])

        # Get the neighbor with the lowest heuristic

        next_state, next_heuristic = neighbor_heuristics[0]

        # If no improvement is made, we are stuck

        if calc_heuristic(current_state, goal_state) <= next_heuristic:

            print("No solution found!")

            return

        # Print the current state and its heuristic

        print("Current State:")

        for row in current_state:

            print(row)

        print(f"Heuristic ({heuristic}): {calc_heuristic(current_state, goal_state)}")

        

        # Move to the next state

        current_state = next_state

        

        # If we reach the goal state, print the solution

        if current_state == goal_state:

            print("Goal State Reached!")

            for row in current_state:

                print(row)

            print(f"Heuristic ({heuristic}): {calc_heuristic(current_state, goal_state)}")

            return

# Main function

if __name__ == "__main__":

    print("Enter the initial puzzle (3x3 grid, use 'B' for the blank space):")

    initial_state = []

    for i in range(3):

        row = input(f"Enter row {i+1}: ").split()

        initial_state.append(row)

    print("\nEnter the goal state (3x3 grid, use 'B' for the blank space):")

    goal_state = []

    for i in range(3):

        row = input(f"Enter row {i+1}: ").split()

        goal_state.append(row)

    

    heuristic = input("\nEnter the heuristic (h1 for Misplaced Tiles, h2 for Manhattan Distance): ")

    hill_climbing(initial_state, goal_state, heuristic)