How to solve the 8-puzzle problem using the A* algorithm

How does A* solve the 8 puzzle problem?

To solve the 8 puzzle problem, the A* algorithm calculates the f-score by defining the f-score and h-score as:

h-score: The number of misplaced tiles by comparing the start state and goal state. It is the Manhattan distance The Manhattan distance, also known as the taxicab distance or city block distance, is a measure of the distance between two points in a grid-based system. between the actual position of the tile to the desired position. To understand how to calculate the h-score, look at the illustrations below:
- Calculate the h-score for the following start and goal states:

import heapq
class PuzzleNode:
    def __init__(self, node_state, parent_node=None, move=None, cost=0):
        self.node_state = node_state
        self.parent_node = parent_node
        self.move = move
        self.cost = cost
        self.heuristic = self.calculate_heuristic()
    def __lt__(self, other):
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)
    def calculate_heuristic(self):
        # Manhattan distance heuristic
        heuristic = 0
        for i in range(3):
            for j in range(3):
                if self.node_state[i][j] != 0:
                    goal_i, goal_j = divmod(self.node_state[i][j] - 1, 3)
                    heuristic += abs(i - goal_i) + abs(j - goal_j)
        return heuristic
def is_valid_move(i, j):
    return 0 <= i < 3 and 0 <= j < 3
def get_neighbors(node):
    neighbors = []
    i, j = next((i, j) for i in range(3) for j in range(3) if node.node_state[i][j] == 0)
    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        new_i, new_j = i + di, j + dj
        if is_valid_move(new_i, new_j):
            new_state = [row[:] for row in node.node_state]
            new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]
            neighbors.append(PuzzleNode(new_state, node, (i, j)))
    return neighbors
def reconstruct_path(node):
    path = []
    while node.parent_node is not None:
        path.append(node)
        node = node.parent_node
    return path[::-1]
def solve_8_puzzle(initial_state):
    start_node = PuzzleNode(initial_state)
    open_set = [start_node]
    closed_set = set()
    while open_set:
        current_node = heapq.heappop(open_set)
        if current_node.node_state == goal_state:
            return reconstruct_path(current_node)
        
        closed_set.add(tuple(map(tuple, current_node.node_state)))
        for neighbor in get_neighbors(current_node):
            if tuple(map(tuple, neighbor.node_state)) not in closed_set:
                heapq.heappush(open_set, neighbor)
    
    return None
if __name__ == "__main__":
    goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]  # Define the goal state
    initial_state = parse_input("__ed_input.txt")  # Parse initial state from input.txt
    path = solve_8_puzzle(initial_state)
    if path:
        print("Solution found! Moves to reach goal state:")
        for move in path:
            print(move.node_state)
    else:
        print("No solution found.")

Enter the input below to be saved in file __ed_input.txt

Code input area

Let’s understand the code:

Line 3–9: We define a class PuzzleNode that contains member variables to store information about the state of the node, the parent of the node, the move we took to move from the parent node to this node, the cost (g-score) of the node, and the heuristic cost (h-score) of the node
Line 11–12: The __lt__ method is implemented in the PuzzleNode class to compare to nodes to each other. It returns the node with less f-score calculated by adding up cost and heuristic.
Line 14–22: It calculates the Manhattan distance of each tile in the current state to the corresponding tile in the goal state.
Line 24–25: It determines if it is allowed for the empty tile to move in a specific direction to avoid index out-of-range error.
Line 27–26: It returns a list of possible neighbors when we expand the current state.
Line 38–43: It is used to trace back to the parent node and reconstruct the path we followed to reach the goal_state.
Line 45–60: This is the main function that solves the 8 puzzle problem. In this function, we define the heaps for open and closed lists. As we expand the nodes and move further, we append nodes to these heaps. The function recursively iterates through the open list until it reaches the goal state.
Line 62–71: It is the main driver function that defines the goal_state and calls the solve_8_puzzle function.

Conclusion

A* Algorithm helps us solve problems efficiently by depleting redundant states. Solving the 8 puzzle problem with this algorithm saves a large amount of execution time.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to solve the 8-puzzle problem using the A* algorithm

A* algorithm

How does A* solve the 8 puzzle problem?

Dry run the algorithm

Code

Conclusion