Ex.
no: 2(b) MEMORY BOUNDED A*ALGORITHM
Date:
AIM:
To write a python program to solve memory bounded A* algorithm.
ALGORITHM:
Step1: Start the program.
Step2: Define a function astar algorithm to perform the algorithm.
Step3: Initialize the starting node.
Step4: If i[1]<min is used find the path with the lowest weight.
Step5: Assign the graph node and call the function a star algorithm.
Step6: Print the result.
Step7: Stop the program.
PROGRAM:
nodes = {
'A': [['B', 6], ['F', 3]],
'B': [['A', 6], ['C', 3], ['D',
2]], 'C': [['B', 3], ['D', 1],
['E', 5]], 'D': [['B', 2], ['C',
1], ['E', 8]], 'E': [['C', 5],
['D', 8], ['I', 5], ['J', 5]],
'F': [['A', 3], ['G', 1],
['H', 7]], 'G': [['F',
1], ['I', 3]],
'H': [['F', 7], ['I', 2]],
'I': [['G', 3], ['H', 2], ['E',
5], ['J', 3]], 'J': [['E', 5], ['I',
3]]
}
h={
'A' : 10,
'B' : 8,
'C' : 5,
'D' : 7,
'E' : 3,
'F' : 6,
'G' : 5,
'H' : 3,
'I' : 1,
'J' : 0
}
def astar(start, goal):
opened = []
closed = []
visited = set()
opened.append([start, h[start]])
while opened :
min = 1000
val = ''
for i in opened:
if i[1] < min:
min = i[1]
val = i[0]
closed.append(val)
visited.add(val)
if goal not in closed:
for i in nodes[val]:
if i[0] not in visited:
opened.append([i[0], (min-h[val]
+i[1]+h[i[0]])]) else:
break
opened.remove([val, min])
closed = closed[::-1]
min = 1000
for i in opened:
if i[1] < min:
min = i[1]
lens = len(closed)
i=0
while i < lens-1:
nei = []
for j in nodes[closed[i]]:
nei.append(j[0])
if closed[i+1] not in nei:
del closed[i+1]
lens-=1
i+=1
closed = closed[::-1]
return closed, min
# Start - 'A', Goal = 'J'
print(astar('A', 'J'))
RESULT:
Thus, the A* algorithm program has been executed successfully and the
required output is displayed.
Ex.no: 3 MINMAX ALGORTHIM FOR GAME PLAYIN TIC_TAC_TOE Date:
AIM:
To write a python program to solve minmax algorithm for game playing
tic_tac_toe program.
ALGORITHM:
Step1: Start the program.
Step2: Importing all necessary libraries.
Step3: Creating for empty place on board and select a random place for the
player. Step4: Checks whether the player has three of their marks in horizontal.
Step5: Evaluate whether there is a win or tie.
Step6: write a drive code.
Step7: Stop the program.
PROGRAM:
import numpy as np
import random
from time import sleep
# Creates an empty board
def create_board():
return(np.array([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]))
# Check for empty
places on board def
possibilities(board):
l = []
for i in range(len(board)):
for j in range(len(board)):
if board[i][j] == 0:
l.append((i, j))
return(l)
# Select a random place for
the player def
random_place(board,
player): selection =
possibilities(board)
current_loc =
random.choice(selection)
board[current_loc] = player
return(board)
# Checks whether the
player has three # of
their marks in a
horizontal row def
row_win(board, player):
for x in range(len(board)):
win = True
for y in
range(len(board)
): if board[x,
y] != player:
win = False
continue
if win == True:
return(win)
return(win)
# Checks whether the
player has three # of
their marks in a vertical
row def col_win(board,
player):
for x in range(len(board)):
win = True
for y in
range(len(board))
: if board[y][x] !
= player: win =
False
continue
if win == True:
return(win)
return(win)
# Checks whether the
player has three # of
their marks in a
diagonal row def
diag_win(board,
player): win = True
y=0
for x in
range(len(boar
d)): if
board[x, x] !=
player: win =
False
if win:
return win
win = True
if win:
for x in
range(len(board)
): y = len(board)
-1-x
if board[x, y] !=
player: win =
False
return win
# Evaluates whether there is
# a winner or a tie
def evaluate(board):
winner = 0
for player in [1, 2]:
if (row_win(board, player) or
col_win(board,player) or
diag_win(board,player)):
winner = player
if np.all(board != 0) and
winner == 0: winner = -1
return winner
# Main function to start the game
def play_game():
board, winner, counter =
create_board(), 0, 1 print(board)
sleep(2)
while winner == 0:
for player in [1, 2]:
board = random_place(board,
player) print("Board after" +
str(counter) + "move") print(board)
sleep(2)
counter += 1
winner =
evaluate(board) if
winner != 0:
break
return(winner)
# Driver Code
print("Winner is" + str(play_game()))
OUTPUT:
RESULT:
Thus, the minmax algorithm for game playing tic_tac_toe program has
been executed successfully and the required output is displayed.
Ex.no: 4 CONTRAINT SATISFACTION PROBLEM
Date:
AIM:
To write a python program to solve constraint satisfaction program.
ALGORITHM:
Step1: Start the program
Step2: Define a function called addcolor to fix a color to a map.
Step3: Define a function check restriction to set a border.
Step4: Then define a function solve csp to implement the program.
Step5: Call the function and pass the argument.
Step6: Display the output.
Step7: Stop the program.
PROGRAM:
def addColor(R, province, color):
ans = []
for rr in R:
res = checkRestriction(rr,
province, color) if res ==
False:
return False
elif res == None:
continue
else:
ans.append(res)
return ans
def checkRestriction(rr,
province, color): index = -
1
other = -1
if rr[0] == province:
index = 0
other = 1
elif rr[1] == province:
index = 1
other = 0
else:
return rr
if isinstance(rr[other], int):
if (color != rr[other]):
return None
else:
return False
else:
return [rr[other], color]
def
solveCSP(province
s, n, R, ci): if (ci
== 0):
newR = addColor(R,
provinces[0], 1) if (newR
== False):
return False
ans = {provinces[0]:1}
res = solveCSP(provinces,
n, newR, 1) if (res ==
False):
return False
ans.update(res)
return ans
elif (ci == len(provinces)):
return {}
for color in range (1,n+1):
ans = {provinces[ci]:color}
newR = addColor(R,
provinces[ci], color) if
(newR == False):
continue
res = solveCSP(provinces,
n, newR, ci+1) if (res ==
False):
continue
ans.update(res)
return ans
return False
n=5
colors=[]
for i in range(1,n+1):
colors.append(i)
cmap = {}
cmap["ab"] = ["bc","nt","sk"]
cmap["bc"] = ["yt","nt","ab"]
cmap["mb"] = ["sk","nu","on"]
cmap["nb"] = ["qc","ns","pe"]
cmap["ns"] = ["nb","pe"]
cmap["nd"] = ["qe"]
cmap["nt"] =
["bc","yt","ab","sk","nu"
] cmap["nu"] =
["nt","mb"]
cmap["on"] = ["mb","qc"]
cmap["pe"] = ["nb","ns"
cmap["qe"] = ["on","nb","nl"]
cmap["sk"] = ["ab","mb","nt"]
cmap["yt"] = ["bc","nt"]
R = []
for x in cmap:
for y in cmap[x]:
R.append([x,y])
provinces = []
for p in cmap:
provinces.append(p)
#print(solveCSP(provinces, 3, R, 0))
while(1):
num=int(input(“Enter number of
the color?”))
print(solveCSP(provinces, num,
R, 0))
RESULT:
Thus, the constraint satisfaction program has been executed successfully
and the required output is displayed.
