8 Puzzle. Write a program that solves the problem using the algorithm A*. Problem.…
- User
8 Puzzle. Write a program that solves the problem using the algorithm A*. Problem. http://en.wikipedia.org/wiki/Fifteen_puzzle I think everyone knows the game of nickels and dimes. This is a slightly simplified version - a game of 8. Our goal is to rearrange the blocks so that they are arranged in ascending order, and to make as few steps as possible. You are allowed to move blocks horizontally and vertically into an empty square.
Best-first search. We describe a solution to the problem that illustrates one of the artificial intelligence algorithms known as the A* search algorithm. We define the board as a search node (i.e., the result of a move is a board with elements arranged in a certain order), and we need to memorize the number of steps to be taken to reach this search node and the previous search node. First, we insert the initial search node (input location, 0 steps, null previous search node) into the priority queue. After that, we remove the search node with the lowest priority from the queue and insert all its successors (those that can be reached in one step from this node) into the queue. We repeat this procedure until we get a node from the queue that corresponds to the final state (a board with all the blocks in their places). The success of our activity depends on the choice of the priority function. Let's consider two functions: The Hamming function - the number of blocks in the wrong positions, plus the number of steps taken to reach the current search node. It is intuitively clear that a position on the board with a small number of blocks out of place is close enough to the desired state. The Manhattan function is the sum of the Manhattan distances (the sum of the vertical and horizontal distance) from the current position of each block to the desired state, plus the number of steps taken to reach the current state. Example:
Optimization. As you can see, Best-first search will have one small problem. We will add the previous state to PQ.
Therefore, we should not add to the PQ a state that is previous to the current state. Problem. Not all initial states have a solution.
Solvability condition. We change the blocks in pairs until the blocks are arranged in the correct order. If there are an even number of such permutations, then the problem is solvable, otherwise it is unsolvable. API. The initial classes are lower in the text. You must use MinPQ.
- Assistant
Here's a Python program that solves the 8-puzzle problem using the A* algorithm with both the Hamming and Manhattan heuristics. It uses a
MinPQ(implemented using Python'sheapqmodule) for managing the priority queue and follows all the specifications mentioned:import heapq class Board: def __init__(self, tiles): self.N = len(tiles) self.tiles = [row[:] for row in tiles] # Deep copy of the tiles # Find the zero (blank) position for i in range(self.N): for j in range(self.N): if self.tiles[i][j] == 0: self.zero_pos = (i, j) return # Generate neighbor boards by sliding tiles into the empty space def neighbors(self): neighbors = [] x0, y0 = self.zero_pos # Possible moves: up, down, left, right directions = [(-1, 0), (1,0), (0,-1), (0,1)] for dx, dy in directions: x_new, y_new = x0 + dx, y0 + dy if 0 <= x_new < self.N and 0 <= y_new < self.N: # Swap the zero tile with the adjacent tile new_tiles = [row[:] for row in self.tiles] new_tiles[x0][y0], new_tiles[x_new][y_new] = new_tiles[x_new][y_new], new_tiles[x0][y0] neighbor_board = Board(new_tiles) neighbors.append(neighbor_board) return neighbors # Check if the board is in the goal state def is_goal(self): goal = 1 for i in range(self.N): for j in range(self.N): expected_value = goal % (self.N*self.N) if self.tiles[i][j] != expected_value: return False goal +=1 return True # Hamming distance: Number of tiles out of place def hamming(self): hamming_distance = 0 goal = 1 for i in range(self.N): for j in range(self.N): if self.tiles[i][j] != 0 and self.tiles[i][j] != goal: hamming_distance += 1 goal += 1 return hamming_distance # Manhattan distance: Sum of distances of tiles from their goal positions def manhattan(self): manhattan_distance = 0 for i in range(self.N): for j in range(self.N): value = self.tiles[i][j] if value != 0: target_i = (value -1) // self.N target_j = (value -1) % self.N manhattan_distance += abs(i - target_i) + abs(j - target_j) return manhattan_distance # Equality methods to compare boards def __eq__(self, other): return self.tiles == other.tiles def __hash__(self): return hash(tuple(tuple(row) for row in self.tiles)) # String representation of the board def __str__(self): return '\n'.join([' '.join(map(str, row)) for row in self.tiles]) class Solver: class SearchNode: def __init__(self, board, moves, previous, priority_function): self.board = board self.moves = moves self.previous = previous # Choose heuristic function based on preference if priority_function == 'hamming': heuristic = board.hamming() elif priority_function == 'manhattan': heuristic = board.manhattan() else: heuristic = 0 self.priority = heuristic + moves # f = g + h # For priority queue comparisons def __lt__(self, other): return self.priority < other.priority def __init__(self, initial_board, priority_function='manhattan'): self.initial_board = initial_board self.priority_function = priority_function self.solution_node = None if not self.is_solvable(): print("No solution possible") return self.solve() # Solvability check def is_solvable(self): # Count the number of inversions inversion_count = 0 flattened = [tile for row in self.initial_board.tiles for tile in row if tile != 0] for i in range(len(flattened)): for j in range(i+1, len(flattened)): if flattened[i] > flattened[j]: inversion_count +=1 # For 3x3 puzzle, if inversion count is even, it's solvable return inversion_count % 2 == 0 # The A* algorithm def solve(self): open_set = [] initial_node = Solver.SearchNode(self.initial_board, 0, None, self.priority_function) heapq.heappush(open_set, (initial_node.priority, initial_node)) closed_set = set() while open_set: current_priority, current_node = heapq.heappop(open_set) if current_node.board.is_goal(): self.solution_node = current_node return closed_set.add(current_node.board) for neighbor in current_node.board.neighbors(): if neighbor not in closed_set and (current_node.previous is None or neighbor != current_node.previous.board): neighbor_node = Solver.SearchNode(neighbor, current_node.moves +1, current_node, self.priority_function) heapq.heappush(open_set, (neighbor_node.priority, neighbor_node)) # Returns the number of moves to solve the puzzle def moves(self): if self.solution_node: return self.solution_node.moves else: return -1 # Indicates no solution # Retrieves the sequence of boards from initial to goal state def solution(self): if self.solution_node is None: return None path = [] node = self.solution_node while node is not None: path.append(node.board) node = node.previous return reversed(path) def main(): # Example initial board configuration initial_tiles = [ [2, 8, 3], [1, 6, 4], [7, 0, 5] ] initial_board = Board(initial_tiles) # Solve using the Manhattan heuristic solver = Solver(initial_board, priority_function='manhattan') if solver.moves() == -1: print("No solution possible") else: print(f"Minimum number of moves = {solver.moves()}") for board in solver.solution(): print(board) print("") if __name__ == '__main__': main()Explanation:
-
Board Class: Represents the state of the puzzle. It includes methods to generate neighbors (possible moves), calculate the Hamming and Manhattan heuristics, check if the current state is the goal state, and provide a string representation of the board.
-
Solver Class: Implements the A* algorithm using a priority queue (MinPQ). It defines an inner
SearchNodeclass to keep track of the board state, the number of moves taken to reach that state, and its priority based on the selected heuristic. Thesolvemethod performs the A* search, avoiding adding the previous state back into the priority queue as specified. -
Solvability Check: Before attempting to solve the puzzle, the solver checks if the initial state is solvable based on the number of inversions. For a 3x3 puzzle, if the inversion count is even, the puzzle is solvable.
-
Main Function: Initializes the puzzle with a given starting state, invokes the solver, and prints out the minimum number of moves along with the sequence of moves to solve the puzzle.
-
Heuristic Functions: Both Hamming and Manhattan heuristics are implemented, and the solver can use either based on the
priority_functionparameter.
Usage:
Run the script, and it will solve the specified 8-puzzle, outputting the minimum number of moves and the steps to reach the goal state.
Note: This solution adheres to the specified constraints:
- Uses the A* algorithm.
- Implements both Hamming and Manhattan heuristics.
- Avoids adding the previous state back into the priority queue.
- Uses a
MinPQ(implemented withheapq). - Checks for solvability before attempting to solve.
-