NAME:VIGNESH.

M
ROLLNO:19EUCS170

EX N0:4 IMPLEMENTATION OF 8-PUZZLE PROBLEM USING A*SEARCH

Objective:

To write a python program for 8 puzzle problem using A* search.

Algorithm:

Step1: Place the starting node in the OPEN list.

Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops.

Step 3: Select the node from the OPEN list which has the smallest value of evaluation function
(g+h), if node n is goal node, then return success and stop, otherwise

Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each
successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute
evaluation function for n' and place into Open list.

Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back
pointer which reflects the lowest g(n') value.

Step 6: Return to Step 2.

Description with sample data:

In this example, we will traverse the given graph using the A* algorithm. The heuristic value of all
states is given in the below table so we will calculate the f(n) of each state using the formula f(n)=
g(n) + h(n), where g(n) is the cost to reach any node from start state.

Here we will use OPEN and CLOSED list.

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

The Solution for the above example is:

Informed Search Algorithms

Initialization: {(S, 5)}

Iteration1: {(S--> A, 4), (S-->G, 10)}

Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}

Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)}

Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with cost 6.

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

Program:

import random

import itertools

import collections

import time

class Node:

"""

A class representing an Solver node

- 'puzzle' is a Puzzle instance

- 'parent' is the preceding node generated by the solver, if any

- 'action' is the action taken to produce puzzle, if any

"""

def __init__(self, puzzle, parent=None, action=None):

self.puzzle = puzzle

self.parent = parent

self.action = action

if (self.parent != None):

self.g = parent.g + 1

else:

self.g = 0

@property

def score(self):

return (self.g + self.h)

@property

def state(self):

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 """

Return a hashable representation of self

"""

return str(self)

@property

def path(self):

"""

Reconstruct a path from to the root 'parent'

"""

node, p = self, []

while node:

p.append(node)

node = node.parent

yield from reversed(p)

@property

def solved(self):

""" Wrapper to check if 'puzzle' is solved """

return self.puzzle.solved

@property

def actions(self):

""" Wrapper for 'actions' accessible at current state """

return self.puzzle.actions

@property

def h(self):

""""h"""

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 return self.puzzle.manhattan

@property

def f(self):

""""f"""

return self.h + self.g

def __str__(self):

return str(self.puzzle)

class Solver:

"""

An '8-puzzle' solver

- 'start' is a Puzzle instance

"""

def __init__(self, start):

self.start = start

def solve(self):

"""

Perform breadth first search and return a path

to the solution, if it exists

"""

queue = collections.deque([Node(self.start)])

seen = set()

seen.add(queue[0].state)

while queue:

queue = collections.deque(sorted(list(queue), key=lambda node: node.f))

node = queue.popleft()

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 if node.solved:

return node.path

for move, action in node.actions:

child = Node(move(), node, action)

if child.state not in seen:

queue.appendleft(child)

seen.add(child.state)

class Puzzle:

"""

A class representing an '8-puzzle'.

- 'board' should be a square list of lists with integer entries 0...width^2 - 1

e.g. [[1,2,3],[4,0,6],[7,5,8]]

"""

def __init__(self, board):

self.width = len(board[0])

self.board = board

@property

def solved(self):

"""

The puzzle is solved if the flattened board's numbers are in

increasing order from left to right and the '0' tile is in the

last position on the board

"""

N = self.width * self.width

return str(self) == ''.join(map(str, range(1,N))) + '0'

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

@property

def actions(self):

"""

Return a list of 'move', 'action' pairs. 'move' can be called

to return a new puzzle that results in sliding the '0' tile in

the direction of 'action'.

"""

def create_move(at, to):

return lambda: self._move(at, to)

moves = []

for i, j in itertools.product(range(self.width),

range(self.width)):

direcs = {'R':(i, j-1),

'L':(i, j+1),

'D':(i-1, j),

'U':(i+1, j)}

for action, (r, c) in direcs.items():

if r >= 0 and c >= 0 and r < self.width and c < self.width and \

self.board[r][c] == 0:

move = create_move((i,j), (r,c)), action

moves.append(move)

return moves

@property

def manhattan(self):

distance = 0

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 for i in range(3):

for j in range(3):

if self.board[i][j] != 0:

x, y = divmod(self.board[i][j]-1, 3)

distance += abs(x - i) + abs(y - j)

return distance

def shuffle(self):

"""

Return a new puzzle that has been shuffled with 1000 random moves

"""

puzzle = self

for _ in range(1000):

puzzle = random.choice(puzzle.actions)[0]()

return puzzle

def copy(self):

"""

Return a new puzzle with the same board as 'self'

"""

board = []

for row in self.board:

board.append([x for x in row])

return Puzzle(board)

def _move(self, at, to):

"""

Return a new puzzle where 'at' and 'to' tiles have been swapped.

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 NOTE: all moves should be 'actions' that have been executed

"""

copy = self.copy()

i, j = at

r, c = to

copy.board[i][j], copy.board[r][c] = copy.board[r][c], copy.board[i][j]

return copy

def pprint(self):

for row in self.board:

print(row)

print()

def __str__(self):

return ''.join(map(str, self))

def __iter__(self):

for row in self.board:

yield from row

# example of use

board = [[1,2,3],[4,5,0],[6,7,8]]

puzzle = Puzzle(board)

#puzzle = puzzle.shuffle()

s = Solver(puzzle)

tic = time.process_time()

p = s.solve()

toc = time.process_time()

steps = 0

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

for node in p:

print(node.action)

node.puzzle.pprint()

steps += 1

print("Total number of steps: " + str(steps))

print("Total amount of time in search: " + str(toc - tic) + " second(s)")

Output:

Result:

Thus the 8-puzzle problem using A*search is implemented successfully.

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY

 Evaluation

Criteria Max Mark Marks

Objective, Algorithm description

20
with sample data

Coding 30

Compilation and debugging 20

Generalization, Execution and

10
Result

Documentation 10

Viva 10

Total 100

Signature of the Faculty In-Charge

SKCET- 18CS502 - ARTIFICIAL INTELLIGENCE & EXPERT SYSTEM LABORATORY