211264116001
Artificial Intelligence (3161608)
Experiment No: 8
TITTLE: Write a program to solve 8 puzzle problems.
EXERCISE
1. Implement python and Prolog code to solve 8 Puzzle Problem.
Ans:
from queue import PriorityQueue
class PuzzleNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.cost = 0
self.depth = 0
if parent:
self.depth = parent.depth + 1
def __lt__(self, other):
return self.cost < other.cost
def __eq__(self, other):
return self.state == other.state
def __hash__(self):
return hash(str(self.state))
def calculate_cost(self, goal_state):
self.cost = self.depth + self.manhattan_distance(goal_state)
def manhattan_distance(self, goal_state):
distance = 0
for i in range(3):
Prof. Ravi Patel
211264116001
Artificial Intelligence (3161608)
for j in range(3):
value = self.state[i][j]
if value != 0:
row = (value - 1) // 3
col = (value - 1) % 3
distance += abs(row - i) + abs(col - j)
return distance
def get_successors(node):
successors = []
i, j = next((i, j) for i in range(3) for j in range(3) if node.state[i][j] == 0)
for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
if 0 <= x < 3 and 0 <= y < 3:
new_state = [row[:] for row in node.state]
new_state[i][j], new_state[x][y] = new_state[x][y], new_state[i][j]
successors.append(PuzzleNode(new_state, node, (x, y)))
return successors
def solve_8_puzzle(initial_state, goal_state):
start_node = PuzzleNode(initial_state)
start_node.calculate_cost(goal_state)
frontier = PriorityQueue()
frontier.put(start_node)
explored = set()
while not frontier.empty():
current_node = frontier.get()
if current_node.state == goal_state:
Prof. Ravi Patel
211264116001
Artificial Intelligence (3161608)
path = []
while current_node:
path.append(current_node.state)
current_node = current_node.parent
path.reverse()
return path
explored.add(current_node)
for successor in get_successors(current_node):
if successor not in explored:
successor.calculate_cost(goal_state)
frontier.put(successor)
return None
# Example usage:
initial_state = [[1, 2, 3], [4, 5, 6], [7, 0, 8]]
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
path = solve_8_puzzle(initial_state, goal_state)
if path:
print("Solution Path:")
for state in path:
print(state)
else:
print("No solution found.")
Output:
Solution Path:
[[1, 2, 3], [4, 5, 6], [7, 0, 8]]
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
Prof. Ravi Patel
