Solution –Practical 1

# Tic-Tac-Toe Program using

# random number in Python

# importing all necessary libraries

importnumpy as np
import random
from time import sleep

# Creates an empty board

defcreate_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

defrandom_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
defrow_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)

Prepared By: Prof. RishitKantariya AI 3170716

 return(win)

# Checks whether the player has three

# of their marks in a vertical row
defcol_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
defdiag_win(board, player):
win = True
y=0
for x in range(len(board)):
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

ifnp.all(board != 0) and winner == 0:

Prepared By: Prof. RishitKantariya AI 3170716

 winner = -1
return winner

# Main function to start the game

defplay_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 Screenshot:

Prepared By: Prof. RishitKantariya AI 3170716

Prepared By: Prof. RishitKantariya AI 3170716
 Solution –Practical 2

from collections import deque

def BFS(a, b, target):

# Map is used to store the states, every

# state is hashed to binary value to
# indicate either that state is visited
# before or not
m = {}
isSolvable = False
path = []

# Queue to maintain states

q = deque()

# Initialing with initial state

q.append((0, 0))

while (len(q) > 0):

# Current state
u = q.popleft()

# q.pop() #pop off used state

# If this state is already visited

if ((u[0], u[1]) in m):
continue

# Doesn't met jug constraints

if ((u[0] > a or u[1] > b or
u[0] < 0 or u[1] < 0)):
continue

# Filling the vector for constructing

# the solution path
path.append([u[0], u[1]])

# Marking current state as visited

m[(u[0], u[1])] = 1

# If we reach solution state, put ans=1

if (u[0] == target or u[1] == target):
isSolvable = True

Prepared By: Prof. RishitKantariya AI 3170716

 if (u[0] == target):
if (u[1] != 0):

# Fill final state

path.append([u[0], 0])
else:
if (u[0] != 0):

# Fill final state

path.append([0, u[1]])

# Print the solution path

sz = len(path)
for i in range(sz):
print("(", path[i][0], ",",
path[i][1], ")")
break

# If we have not reached final state

# then, start developing intermediate
# states to reach solution state
q.append([u[0], b]) # Fill Jug2
q.append([a, u[1]]) # Fill Jug1

forap in range(max(a, b) + 1):

# Pour amount ap from Jug2 to Jug1

c = u[0] + ap
d = u[1] - ap

# Check if this state is possible or not

if (c == a or (d == 0 and d >= 0)):
q.append([c, d])

# Pour amount ap from Jug 1 to Jug2

c = u[0] - ap
d = u[1] + ap

# Check if this state is possible or not

if ((c == 0 and c >= 0) or d == b):
q.append([c, d])

# Empty Jug2
q.append([a, 0])

# Empty Jug1
q.append([0, b])

Prepared By: Prof. RishitKantariya AI 3170716

 # No, solution exists if ans=0
if (not isSolvable):
print("No solution")

# Driver code
if __name__ == '__main__':

Jug1, Jug2, target = 4, 3, 2

print("Path from initial state "
"to solution state ::")

BFS(Jug1, Jug2, target)

Output Screenshot:

Prepared By: Prof. RishitKantariya AI 3170716

 Solution – Practical 3
import sys
import numpy as np

class Node:
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action

class StackFrontier:
def __init__(self):
self.frontier = []

def add(self, node):

self.frontier.append(node)

def contains_state(self, state):

return any((node.state[0] == state[0]).all() for node in self.frontier)

def empty(self):
return len(self.frontier) == 0

def remove(self):
if self.empty():
raise Exception("Empty Frontier")
else:
node = self.frontier[-1]
self.frontier = self.frontier[:-1]
return node

class QueueFrontier(StackFrontier):
def remove(self):
if self.empty():
raise Exception("Empty Frontier")
else:
node = self.frontier[0]
self.frontier = self.frontier[1:]
return node

class Puzzle:

Prepared By: Prof.Rishit Kantariya AI 31707016

 def __init__(self, start, startIndex, goal, goalIndex):
self.start = [start, startIndex]
self.goal = [goal, goalIndex]
self.solution = None

def neighbors(self, state):

mat, (row, col) = state
results = []

if row > 0:
mat1 = np.copy(mat)
mat1[row][col] = mat1[row - 1][col]
mat1[row - 1][col] = 0
results.append(('up', [mat1, (row - 1, col)]))
if col > 0:
mat1 = np.copy(mat)
mat1[row][col] = mat1[row][col - 1]
mat1[row][col - 1] = 0
results.append(('left', [mat1, (row, col - 1)]))
if row < 2:
mat1 = np.copy(mat)
mat1[row][col] = mat1[row + 1][col]
mat1[row + 1][col] = 0
results.append(('down', [mat1, (row + 1, col)]))
if col < 2:
mat1 = np.copy(mat)
mat1[row][col] = mat1[row][col + 1]
mat1[row][col + 1] = 0
results.append(('right', [mat1, (row, col + 1)]))

return results

def print(self):
solution = self.solution if self.solution is not None else None
print("Start State:\n", self.start[0], "\n")
print("Goal State:\n", self.goal[0], "\n")
print("\nStates Explored: ", self.num_explored, "\n")
print("Solution:\n ")
for action, cell in zip(solution[0], solution[1]):
print("action: ", action, "\n", cell[0], "\n")
print("Goal Reached!!")

def does_not_contain_state(self, state):

for st in self.explored:
if (st[0] == state[0]).all():

Prepared By: Prof.Rishit Kantariya AI 31707016

 return False
return True

def solve(self):
self.num_explored = 0

start = Node(state=self.start, parent=None, action=None)

frontier = QueueFrontier()
frontier.add(start)

self.explored = []

while True:
if frontier.empty():
raise Exception("No solution")

node = frontier.remove()
self.num_explored += 1

if (node.state[0] == self.goal[0]).all():
actions = []
cells = []
while node.parent is not None:
actions.append(node.action)
cells.append(node.state)
node = node.parent
actions.reverse()
cells.reverse()
self.solution = (actions, cells)
return

self.explored.append(node.state)

for action, state in self.neighbors(node.state):

if not frontier.contains_state(state) and self.does_not_contain_state(state):
child = Node(state=state, parent=node, action=action)
frontier.add(child)

start = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])

goal = np.array([[2, 8, 1], [0, 4, 3], [7, 6, 5]])

startIndex = (1, 1)
goalIndex = (1, 0)

Prepared By: Prof.Rishit Kantariya AI 31707016

p = Puzzle(start, startIndex, goal, goalIndex)
p.solve()
p.print()

Screenshot

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution-Practical 4
# Recursive Python function to solve the tower of hanoi

def TowerOfHanoi(n , source, destination, auxiliary):

if n==1:
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)

# Driver code
n=4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods

Screenshot

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution Practial -5
DOMAINS
queen = q(integer, integer)
queens = queen*
freelist = integer*
board = board(queens, freelist, freelist, freelist, freelist)

PREDICATES
nondeterm placeN(integer, board, board)
nondeterm place_a_queen(integer, board, board)
nondeterm nqueens(integer)
nondeterm makelist(integer, freelist)
nondeterm findandremove(integer, freelist, freelist)
nextrow(integer, freelist, freelist)

CLAUSES
nqueens(N):-
makelist(N,L),Diagonal=N*2-1,makelist(Diagonal,LL),
placeN(N,board([],L,L,LL,LL),Final), write(Final).

placeN(_,board(D,[],[],D1,D2),board(D,[],[],D1,D2)):-!.
placeN(N,Board1,Result):-
place_a_queen(N,Board1,Board2),
placeN(N,Board2,Result).

place_a_queen(N,board(Queens,Rows,Columns,Diag1,Diag2),
board([q(R,C)|Queens],NewR,NewC,NewD1,NewD2)):-
nextrow(R,Rows,NewR),
findandremove(C,Columns,NewC),
D1=N+C-R,findandremove(D1,Diag1,NewD1),
D2=R+C-1,findandremove(D2,Diag2,NewD2).
findandremove(X,[X|Rest],Rest).
findandremove(X,[Y|Rest],[Y|Tail]):-
findandremove(X,Rest,Tail).

makelist(1,[1]).
makelist(N,[N|Rest]) :-
N1=N-1,makelist(N1,Rest).
nextrow(Row,[Row|Rest],Rest).

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution-Practical 6

n = 4 # there are four nodes in example graph (graph is 1-based)

# dist[i][j] represents shortest distance to go from i to j

# this matrix can be calculated for any given graph using

# all-pair shortest path algorithms

dist = [[0, 0, 0, 0, 0], [0, 0, 10, 15, 20], [

0, 10, 0, 25, 25], [0, 15, 25, 0, 30], [0, 20, 25, 30, 0]]

# memoization for top down recursion

memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]

def fun(i, mask):

# base case

# if only ith bit and 1st bit is set in our mask,

# it implies we have visited all other nodes already

if mask == ((1 << i) | 3):

Prepared By: Prof.Rishit Kantariya AI 31707016

 return dist[1][i]

# memoization

if memo[i][mask] != -1:

return memo[i][mask]

res = 10**9 # result of this sub-problem

# we have to travel all nodes j in mask and end the path at ith node

# so for every node j in mask, recursively calculate cost of

# travelling all nodes in mask

# except i and then travel back from node j to node i taking

# the shortest path take the minimum of all possible j nodes

for j in range(1, n+1):

if (mask & (1 << j)) != 0 and j != i and j != 1:

res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i])

memo[i][mask] = res # storing the minimum value

return res

# Driver program to test above logic

ans = 10**9

for i in range(1, n+1):

# try to go from node 1 visiting all nodes in between to i

Prepared By: Prof.Rishit Kantariya AI 31707016

 # then return from i taking the shortest route to 1

ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])

print("The cost of most efficient tour = " + str(ans))

Screenshot:

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution – Practical 7
from collections import deque

class Graph:
# example of adjacency list (or rather map)
# adjacency_list = {
# 'A': [('B', 1), ('C', 3), ('D', 7)],
# 'B': [('D', 5)],
# 'C': [('D', 12)]
#}

def __init__(self, adjacency_list):

self.adjacency_list = adjacency_list

def get_neighbors(self, v):

return self.adjacency_list[v]

# heuristic function with equal values for all nodes

def h(self, n):
H={
'A': 1,
'B': 1,
'C': 1,
'D': 1
}

return H[n]

def a_star_algorithm(self, start_node, stop_node):

# open_list is a list of nodes which have been visited, but who's neighbors
# haven't all been inspected, starts off with the start node
# closed_list is a list of nodes which have been visited
# and who's neighbors have been inspected
open_list = set([start_node])
closed_list = set([])

# g contains current distances from start_node to all other nodes

# the default value (if it's not found in the map) is +infinity
g = {}

g[start_node] = 0

# parents contains an adjacency map of all nodes

parents = {}
parents[start_node] = start_node

while len(open_list) > 0:

n = None

Prepared By: Prof.Rishit Kantariya AI 31707016

# find a node with the lowest value of f() - evaluation function
for v in open_list:
if n == None or g[v] + self.h(v) < g[n] + self.h(n):
n = v;

if n == None:
print('Path does not exist!')
return None

# if the current node is the stop_node

# then we begin reconstructin the path from it to the start_node
if n == stop_node:
reconst_path = []

while parents[n] != n:
reconst_path.append(n)
n = parents[n]

reconst_path.append(start_node)

reconst_path.reverse()

print('Path found: {}'.format(reconst_path))

return reconst_path

# for all neighbors of the current node do

for (m, weight) in self.get_neighbors(n):
# if the current node isn't in both open_list and closed_list
# add it to open_list and note n as it's parent
if m not in open_list and m not in closed_list:
open_list.add(m)
parents[m] = n
g[m] = g[n] + weight

# otherwise, check if it's quicker to first visit n, then m

# and if it is, update parent data and g data
# and if the node was in the closed_list, move it to open_list
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n

if m in closed_list:
closed_list.remove(m)
open_list.add(m)

# remove n from the open_list, and add it to closed_list

Prepared By: Prof.Rishit Kantariya AI 31707016

 # because all of his neighbors were inspected
open_list.remove(n)
closed_list.add(n)

print('Path does not exist!')

return None

Let's look at an example with the following weighted graph:

We run the code as so:

adjacency_list = {
'A': [('B', 1), ('C', 3), ('D', 7)],
'B': [('D', 5)],
'C': [('D', 12)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('A', 'D')

Screenshot:

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution-Practical 8

Prepared By: Prof.Rishit Kantariya AI 31707016

 Solution-Practical 9

Prepared By: Prof.Rishit Kantariya AI 31707016

Prepared By: Prof.Rishit Kantariya AI 31707016