Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Experiment No: 8 TITTLE: Write A Program To Solve 8 Puzzle Problems. Exercise

    Uploaded by

    Krupa
    The document discusses writing a program to solve 8 puzzle problems using Python and Prolog code. It provides an implementation of solving the 8 puzzle problem using a priority queue and calculating Manhattan distance between puzzle states.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Experiment No: 8 TITTLE: Write A Program To Solve 8 Puzzle Problems. Exercise

    Uploaded by

    Krupa
    9 views3 pages
    The document discusses writing a program to solve 8 puzzle problems using Python and Prolog code. It provides an implementation of solving the 8 puzzle problem using a priority queue and calculating Manhattan distance between puzzle states.

    Original Description:

    Artificial intelligence practical code

    Original Title

    Ai p8

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses writing a program to solve 8 puzzle problems using Python and Prolog code. It provides an implementation of solving the 8 puzzle problem using a priority queue and calculating Manhattan distance between puzzle states.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views3 pages

    Experiment No: 8 TITTLE: Write A Program To Solve 8 Puzzle Problems. Exercise

    Uploaded by

    Krupa
    The document discusses writing a program to solve 8 puzzle problems using Python and Prolog code. It provides an implementation of solving the 8 puzzle problem using a priority queue and calculating Manhattan distance between puzzle states.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    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

    You might also like