ai_lab_6

import heapq
class PuzzleNode:
def init(self, state, parent=None, move=None, depth=0):
self.state = state
self.parent = parent
self.move = move
self.depth = depth
self.cost = 0
def lt(self, other):
return self.cost < other.cost
class EightPuzzleSolver:
def init(self, initial_state):
self.initial_state = initial_state
self.goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
def find_blank(self, state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
def get_possible_moves(self, state):
moves = []
blank_i, blank_j = self.find_blank(state)
if blank_i > 0:
moves.append((-1, 0)) # Move blank tile up
if blank_i < 2:
moves.append((1, 0)) # Move blank tile down
if blank_j > 0:
moves.append((0, -1)) # Move blank tile left
if blank_j < 2:
moves.append((0, 1)) # Move blank tile right
return moves
def heuristic_cost(self, state):
cost = 0
for i in range(3):
for j in range(3):
if state[i][j] != 0:
goal_i, goal_j = divmod(state[i][j] - 1, 3)
cost += abs(i - goal_i) + abs(j - goal_j)
return cost
def solve(self):
initial_node = PuzzleNode(self.initial_state)
initial_node.cost = self.heuristic_cost(initial_node.state)
frontier = [initial_node]
heapq.heapify(frontier)
explored = set()
while frontier:
current_node = heapq.heappop(frontier)
if current_node.state == self.goal_state:
return self.construct_path(current_node)
explored.add(tuple(map(tuple, current_node.state)))
for move in self.get_possible_moves(current_node.state):
new_state = [row[:] for row in current_node.state]
i, j = self.find_blank(new_state)
new_i, new_j = i + move[0], j + move[1]
new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]
if tuple(map(tuple, new_state)) not in explored:
new_node = PuzzleNode(new_state, current_node, move, current_node.depth + 1)
new_node.cost = new_node.depth + self.heuristic_cost(new_state)
heapq.heappush(frontier, new_node)
return None # No solution found
def construct_path(self, node):
path = []
while node:
path.append((node.state, node.move))
node = node.parent
return path[::-1]
def print_solution(path):
for i, (state, move) in enumerate(path):
print(f"Step {i + 1}:")
for row in state:
print(row)
if move:
print(
f"Move blank tile {'up' if move == (-1, 0) else 'down' if move == (1, 0) else 'left' if move
== (0, -1) else 'right'}")
print()
if name == "main":
initial_state = [[1, 2, 3],
[4, 8, 5],
[7, 0, 6]]
solver = EightPuzzleSolver(initial_state)
solution = solver.solve()
if solution:
print("Solution found!\n")
print_solution(solution)
else:
print("No solution found.")