Solve 8-Puzzle Problem with Python and A* Search
Write a Program to Implement 8-Puzzle problem using Python
import heapq
from termcolor import colored
# Class to represent the state of the 8-puzzle
class PuzzleState:
def __init__(self, board, parent, move, depth, cost):
self.Board = board # The puzzle board configuration
self.Parent = parent # Parent state
self.Move = move # Move to reach this state
self.Depth = depth # Depth in the search tree
self.Cost = cost # Cost (depth + heuristic)
def __lt__(self, other):
return self.Cost < other.Cost
# Function to display the board in a visually appealing format
def print_board(board):
print(“+—+—+—+”)
for row in range(0, 9, 3):
row_visual = “|”
for tile in board[row:row + 3]:
if tile == 0: # Blank tile
row_visual += f” {colored(‘ ‘, ‘cyan’)} |”
else:
row_visual += f” {colored(str(tile), ‘yellow’)} |”
print(row_visual)
print(“+—+—+—+”)
# Goal state for the puzzle
goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# Possible moves for the blank tile (up, down, left, right)
moves = {
‘U’: -3, # Move up
‘D’: 3, # Move down
‘L’: -1, # Move left
‘R’: 1 # Move right
}
# Function to calculate the heuristic (Manhattan distance)
def heuristic(board):
distance = 0
for i in range(9):
if board[i] != 0:
x1, y1 = divmod(i, 3)
x2, y2 = divmod(board[i] – 1, 3)
distance += abs(x1 – x2) + abs(y1 – y2)
return distance
# Function to get the new state after a move
def move_tile(board, move, blank_pos):
new_board = board[:]
new_blank_pos = blank_pos + moves[move]
new_board[blank_pos], new_board[new_blank_pos] = new_board[new_blank_pos], new_board[blank_pos]
return new_board
# A* search algorithm
def a_star(start_state):
open_list = []
closed_list = set()
heapq.Heappush(open_list, PuzzleState(start_state, None, None, 0, heuristic(start_state)))
while open_list:
current_state = heapq.Heappop(open_list)
if current_state.Board == goal_state:
return current_state
closed_list.Add(tuple(current_state.Board))
blank_pos = current_state.Board.Index(0)
for move in moves:
if move == ‘U’ and blank_pos < 3: # Invalid move up
continue
if move == ‘D’ and blank_pos > 5: # Invalid move down
continue
if move == ‘L’ and blank_pos % 3 == 0: # Invalid move left
continue
if move == ‘R’ and blank_pos % 3 == 2: # Invalid move right
continue
new_board = move_tile(current_state.Board, move, blank_pos)
if tuple(new_board) in closed_list:
continue
new_state = PuzzleState(new_board, current_state, move, current_state.Depth + 1, current_state.Depth + 1 + heuristic(new_board))
heapq.Heappush(open_list, new_state)
return None
# Function to print the solution path
def print_solution(solution):
path = []
current = solution
while current:
path.Append(current)
current = current.Parent
path.Reverse()
for step in path:
print(f”Move: {step.Move}”)
print_board(step.Board)
# Initial state of the puzzle
initial_state = [1, 2, 3, 4, 0, 5, 6, 7, 8]
# Solve the puzzle using A* algorithm
solution = a_star(initial_state)
# Print the solution
if solution:
print(colored(“Solution found:”, “green”))
print_solution(solution)
else:
print(colored(“No solution exists.”, “red”))