Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Ai Exp 4

    Uploaded by

    aditya b
    The document describes using the A* search algorithm to solve the 8 puzzle problem in Python. It provides code to define Node and Puzzle classes to represent game states and perform the A* search. The code accepts start and goal states, generates child nodes by moving the blank space, and uses a heuristic function to find the shortest path from start to goal.

    Copyright:

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

    Ai Exp 4

    Uploaded by

    aditya b
    15 views9 pages
    The document describes using the A* search algorithm to solve the 8 puzzle problem in Python. It provides code to define Node and Puzzle classes to represent game states and perform the A* search. The code accepts start and goal states, generates child nodes by moving the blank space, and uses a heuristic function to find the shortest path from start to goal.

    Original Title

    Ai exp 4

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes using the A* search algorithm to solve the 8 puzzle problem in Python. It provides code to define Node and Puzzle classes to represent game states and perform the A* search. The code accepts start and goal states, generates child nodes by moving the blank space, and uses a heuristic function to find the shortest path from start to goal.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    15 views9 pages

    Ai Exp 4

    Uploaded by

    aditya b
    The document describes using the A* search algorithm to solve the 8 puzzle problem in Python. It provides code to define Node and Puzzle classes to represent game states and perform the A* search. The code accepts start and goal states, generates child nodes by moving the blank space, and uses a heuristic function to find the shortest path from start to goal.

    Copyright:

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

    Ai exp 4

    To implement A* algorithm in the given 8 puzzle problem in python

    A* search is the most commonly known form of best-first search. It uses heuristic function h(n),
    and cost to reach the node n from the start state g(n). A* search algorithm finds the shortest
    path through the search space using the heuristic function.

    f(n) = Estimated cost of the cheapest solution

    g(n)= cost to reach from node n from start state

    h(n)=cost to reach node n from goal node

    State space tree


    Code:

    class Node:

    def __init__(self,data,level,fval):

    """ Initialize the node with the data, level of the node and the calculated fvalue """

    self.data = data

    self.level = level

    self.fval = fval
    def generate_child(self):

    """ Generate child nodes from the given node by moving the blank space

    either in the four directions {up,down,left,right} """

    x,y = self.find(self.data,'_')

    """ val_list contains position values for moving the blank space in either of

    the 4 directions [up,down,left,right] respectively. """

    val_list = [[x,y-1],[x,y+1],[x-1,y],[x+1,y]]

    children = []

    for i in val_list:

    child = self.shuffle(self.data,x,y,i[0],i[1])

    if child is not None:

    child_node = Node(child,self.level+1,0)

    children.append(child_node)

    return children

    def shuffle(self,puz,x1,y1,x2,y2):

    """ Move the blank space in the given direction and if the position value are out

    of limits the return None """

    if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):

    temp_puz = []

    temp_puz = self.copy(puz)

    temp = temp_puz[x2][y2]

    temp_puz[x2][y2] = temp_puz[x1][y1]

    temp_puz[x1][y1] = temp

    return temp_puz

    else:

    return None
    def copy(self,root):

    """ Copy function to create a similar matrix of the given node"""

    temp = []

    for i in root:

    t = []

    for j in i:

    t.append(j)

    temp.append(t)

    return temp

    def find(self,puz,x):

    """ Specifically used to find the position of the blank space """

    for i in range(0,len(self.data)):

    for j in range(0,len(self.data)):

    if puz[i][j] == x:

    return i,j

    class Puzzle:

    def __init__(self,size):

    """ Initialize the puzzle size by the specified size,open and closed lists to empty """

    self.n = size

    self.open = []

    self.closed = []

    def accept(self):

    """ Accepts the puzzle from the user """

    puz = []

    for i in range(0,self.n):
    temp = input().split(" ")

    puz.append(temp)

    return puz

    def f(self,start,goal):

    """ Heuristic Function to calculate hueristic value f(x) = h(x) + g(x) """

    return self.h(start.data,goal)+start.level

    def h(self,start,goal):

    """ Calculates the different between the given puzzles """

    temp = 0

    for i in range(0,self.n):

    for j in range(0,self.n):

    if start[i][j] != goal[i][j] and start[i][j] != '_':

    temp += 1

    return temp

    def process(self):

    """ Accept Start and Goal Puzzle state"""

    print("Enter the start state matrix \n")

    start = self.accept()

    print("Enter the goal state matrix \n")

    goal = self.accept()

    start = Node(start,0,0)

    start.fval = self.f(start,goal)

    """ Put the start node in the open list"""

    self.open.append(start)
    print("\n\n")

    while True:

    cur = self.open[0]

    print("")

    print(" | ")

    print(" | ")

    print(" \\\'/ \n")

    for i in cur.data:

    for j in i:

    print(j,end=" ")

    print("")

    print("h = ", self.h(cur.data,goal))

    print("f = ", self.f(start,goal))

    """ If the difference between current and goal node is 0 we have reached the goal node"""

    if(self.h(cur.data,goal) == 0):

    break

    for i in cur.generate_child():

    i.fval = self.f(i,goal)

    self.open.append(i)

    self.closed.append(cur)

    del self.open[0]

    """ sort the opne list based on f value """

    self.open.sort(key = lambda x:x.fval,reverse=False)

    puz = Puzzle(3)

    puz.process()
    output:

    Enter the start state matrix

    283

    164

    7_5

    Enter the goal state matrix

    123

    8_4

    765

    \'/

    283

    164

    7_5

    h= 4

    f= 4

    \'/

    283

    1_4

    765

    h= 3
    f= 4

    \'/

    283

    _14

    765

    h= 3

    f= 4

    \'/

    2_3

    184

    765

    h= 3

    f= 4

    \'/

    _23

    184

    765
    h= 2

    f= 4

    \'/

    123

    _84

    765

    h= 1

    f= 4

    \'/

    123

    8_4

    765

    h= 0

    f= 4

    You might also like