Practical no-1

Write a program to implement depth for search algorithm?

Code:
graph={
"A" :['B','C'],
"B" :['A','D','E'],
"C" :['A','F'],
"D" :['B'],
"E" :['B'],
"F" :['C']
}
path=[]
stack=["A"]
while(len(stack)!=0):
s=stack.pop()
if s not in path:
path.append(s)
if s not in graph:
continue
for neighbour in graph[s]:
stack.append(neighbour)
print(path)

Output:
 Practical no-2

Write a program to implement breadth for search?

Code:
From collections import deque
def bfs(graph,start):
visited=set()
queue=deque([start])
while queue:
vertex=queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex)
for neighbour in graph:
if neighbour not in visited:
queue.append(neighbour)

graph={
"A":['B','C'],
"B":['A','D','E'],
"C":['A','F'],
"D":['B'],
"E":['B'],
"F":['C']
}
start_vertex=’A’
bfs(graph,start_vertex)

Output:
 Practical no-3

Write a program to shuffle deck of cards ?

Code:

import itertools, random

#make a deck of card
deck=list(itertools.product(range(1,14),['Spade','Heart','Diamond','Club']))
#shuffle a cards
random.shuffle(deck)
#draw five cards
print("You got:")
for i in range(5):
print(deck[i] [0],"of",deck[i] [1])

Output:
 Practical no-4

Write a code for hill climbing problem ?

Code:
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph,s):
vertex=[]
for i in range(V):
if i!=s:
vertex.append(i)
min_path=maxsize
next_permutation=permutation(vertex)
for i in next_permutation:
current_pathweight=0
k=s
for j in i:
current_pathweight +=graph[k] [j]
k=j
min_path=min(min_path,current_pathweight)
return min_path
if_name_=="_main_";
graph=[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
s=0
print(travellingSalesmanProblem(graph,s))

Output:
 Practical no-5

Write a program to derive the predicate ?

Code:

footballer(ronaldo).
batsman(rohit).
keeper(msdhoni).
bowler(bhumra).
cricketer(X) :-batsman(X);keeper(X);bowler(X).

Output:
 Practical no-6
Write a program to solve tower of Hanoi problem ?
Code:
%TOWER OF HANOI
move(1,X,Y,_):-
write('move top disk from'),
write(X),
write(' to '),
write(Y),nl.
move(N,X,Y,Z):-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).

Ouput:
 Practical no-7
Derive the expression based on associative law ?
Code:
%define associative law for adittion
associative_law(A,B,C,Result):-Result is A*(B*C).
expression1(2,3,7). %expression
expression2(5,6,7).
%drive the results using law
derive_results:-
expression1(A,B,C),
associative_law(A,B,C,Result1),
expression2(X,Y,Z),
associative_law(X,Y,Z,Result2),
write('result of expression1 using associative
law:'),write(Result1),nl,
write('result of expression2 using associative
law:'),write(Result2),nl.

Output:
 Practical no-8
Derive the expression based on distributive law ?
Code:

%define associative law for adittion

distributive_law(A,B,C,Result):-Result is A*(B+C).
expression1(2,3,7). %expression
expression2(5,6,7).
%drive the results using law
derive_results:-
expression1(A,B,C),
distributive_law(A,B,C,Result1),
expression2(X,Y,Z),
distributive_law(X,Y,Z,Result2),
write('result of expression1 using associative law:'),write(Result1),nl,
write('result of expression2 using associative law:'),write(Result2),nl.

Output:
 Practical no-10B
Write a program which contains three
predicate:male,female,parent make rules for following family
relation:father,mother,grandfather,grandmother etc
Family tree.
Code:

female(koyal).
female(bulbul).
female(sonu).
female(rohini).
parent(popatlal,tapu). %popatlal is parent of tapu.
parent(popatlal,bulbul). %popatlal is parent of bulbul.
parent(koyal,tapu).
parent(koyal, bulbul).
parent(tapu,sumit).
parent(sonu,sumit).
parent(bulbul,rohini).
parent(raman,rohini).
mother(X,Y):-parent(X,Y),female(X).
father(X,Y):-parent(X,Y),male(X).
grandfather(X,Z):-father(X,Y),parent(Y,Z).
grandmother(X,Z):-mother(X,Y),parent(Y,Z).

Output:
 Practical no-8B
Solve constraint satisfaction problem ?
Code:
coloring(MH,GO,AP,GJ,RJ,HR,MP):-
different(MH,GO),
different(MH,AP),
different(MH,GJ),
different(MH,MP),
different(GJ,RJ),
different(RJ,HR),
different(GO,AP).
different(red,blue).
different(blue,red).
different(blue,green).
different(green,blue).
different(green,red).
different(red,green).

Output:
 Practical no-2A
Write a program to simulate 4-queen/n-queen problem ?
Code:

#Number of queens
print ("Enter the number of queens")
N = int(input())

#chessboard
#NxN matrix with all elements 0
board = [[0]*N for _ in range(N)]

def is_attack(i, j):

#checking if there is a queen in row or column
for k in range(0,N):
if board[i][k]==1 or board[k][j]==1:
return True
#checking diagonals
for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j):
if board[k][l]==1:
return True
return False

def N_queen(n):
#if n is 0, solution found
if n==0:
return True
for i in range(0,N):
for j in range(0,N):
'''checking if we can place a queen here or not
queen will not be placed if the place is being attacked
or already occupied'''
if (not(is_attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
#recursion
 #wether we can put the next queen with this arrangment or not
if N_queen(n-1)==True:
return True
board[i][j] = 0

return False

N_queen(N)
for i in board:
print (i)

Output:
 Practical no-5A
Write a program to solve water jug problem ?
Code:
from collections import defaultdict
jug1, jug2, aim = 4, 3, 2
visited = defaultdict(lambda: False)
def waterJugSolver(amt1, amt2):
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True
if visited[(amt1, amt2)] == False:
print(amt1, amt2)
visited[(amt1, amt2)] = True
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))
else:
return False
print("Steps: ")
waterJugSolver(0, 0)

Output:
 Practical no-5B
Design the simulation of tic-tac-toe game using min-max
algorithm ?
Code:
#!/usr/bin/env python3
from math import inf as infinity
from random import choice
import platform
import time
from os import system

HUMAN = -1
COMP = +1
board = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
]

def evaluate(state):
"""
Function to heuristic evaluation of state.
:param state: the state of the current board
:return: +1 if the computer wins; -1 if the human wins; 0 draw
"""
if wins(state, COMP):
score = +1
elif wins(state, HUMAN):
 score = -1
else:
score = 0

return score

def wins(state, player):

"""
This function tests if a specific player wins. Possibilities:
* Three rows [X X X] or [O O O]
* Three cols [X X X] or [O O O]
* Two diagonals [X X X] or [O O O]
:param state: the state of the current board
:param player: a human or a computer
:return: True if the player wins
"""
win_state = [
[state[0][0], state[0][1], state[0][2]],
[state[1][0], state[1][1], state[1][2]],
[state[2][0], state[2][1], state[2][2]],
[state[0][0], state[1][0], state[2][0]],
[state[0][1], state[1][1], state[2][1]],
[state[0][2], state[1][2], state[2][2]],
[state[0][0], state[1][1], state[2][2]],
[state[2][0], state[1][1], state[0][2]],
]
if [player, player, player] in win_state:
return True
else:
return False

def game_over(state):
"""
This function test if the human or computer wins
:param state: the state of the current board
:return: True if the human or computer wins
"""
return wins(state, HUMAN) or wins(state, COMP)

def empty_cells(state):
"""
Each empty cell will be added into cells' list
:param state: the state of the current board
:return: a list of empty cells
"""
cells = []

for x, row in enumerate(state):

 for y, cell in enumerate(row):
if cell == 0:
cells.append([x, y])

return cells

def valid_move(x, y):

"""
A move is valid if the chosen cell is empty
:param x: X coordinate
:param y: Y coordinate
:return: True if the board[x][y] is empty
"""
if [x, y] in empty_cells(board):
return True
else:
return False

def set_move(x, y, player):

"""
Set the move on board, if the coordinates are valid
:param x: X coordinate
:param y: Y coordinate
:param player: the current player
"""
if valid_move(x, y):
board[x][y] = player
return True
else:
return False

def minimax(state, depth, player):

"""
AI function that choice the best move
:param state: current state of the board
:param depth: node index in the tree (0 <= depth <= 9),
but never nine in this case (see iaturn() function)
:param player: an human or a computer
:return: a list with [the best row, best col, best score]
"""
if player == COMP:
best = [-1, -1, -infinity]
else:
best = [-1, -1, +infinity]

if depth == 0 or game_over(state):
score = evaluate(state)
return [-1, -1, score]
 for cell in empty_cells(state):
x, y = cell[0], cell[1]
state[x][y] = player
score = minimax(state, depth - 1, -player)
state[x][y] = 0
score[0], score[1] = x, y

if player == COMP:
if score[2] > best[2]:
best = score # max value
else:
if score[2] < best[2]:
best = score # min value

return best

def clean():
"""
Clears the console
"""
os_name = platform.system().lower()
if 'windows' in os_name:
system('cls')
else:
system('clear')

def render(state, c_choice, h_choice):

"""
Print the board on console
:param state: current state of the board
"""

chars = {
-1: h_choice,
+1: c_choice,
0: ' '
}
str_line = '---------------'

print('\n' + str_line)
for row in state:
for cell in row:
symbol = chars[cell]
print(f'| {symbol} |', end='')
print('\n' + str_line)

def ai_turn(c_choice, h_choice):

 """
It calls the minimax function if the depth < 9,
else it choices a random coordinate.
:param c_choice: computer's choice X or O
:param h_choice: human's choice X or O
:return:
"""
depth = len(empty_cells(board))
if depth == 0 or game_over(board):
return

clean()
print(f'Computer turn [{c_choice}]')
render(board, c_choice, h_choice)

if depth == 9:
x = choice([0, 1, 2])
y = choice([0, 1, 2])
else:
move = minimax(board, depth, COMP)
x, y = move[0], move[1]

set_move(x, y, COMP)
time.sleep(1)

def human_turn(c_choice, h_choice):

"""
The Human plays choosing a valid move.
:param c_choice: computer's choice X or O
:param h_choice: human's choice X or O
:return:
"""
depth = len(empty_cells(board))
if depth == 0 or game_over(board):
return

# Dictionary of valid moves

move = -1
moves = {
1: [0, 0], 2: [0, 1], 3: [0, 2],
4: [1, 0], 5: [1, 1], 6: [1, 2],
7: [2, 0], 8: [2, 1], 9: [2, 2],
}

clean()
print(f'Human turn [{h_choice}]')
render(board, c_choice, h_choice)

while move < 1 or move > 9:

try:
 move = int(input('Use numpad (1..9): '))
coord = moves[move]
can_move = set_move(coord[0], coord[1], HUMAN)

if not can_move:
print('Bad move')
move = -1
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')

def main():
"""
Main function that calls all functions
"""
clean()
h_choice = '' # X or O
c_choice = '' # X or O
first = '' # if human is the first

# Human chooses X or O to play

while h_choice != 'O' and h_choice != 'X':
try:
print('')
h_choice = input('Choose X or O\nChosen: ').upper()
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')

# Setting computer's choice

if h_choice == 'X':
c_choice = 'O'
else:
c_choice = 'X'

# Human may starts first

clean()
while first != 'Y' and first != 'N':
try:
first = input('First to start?[y/n]: ').upper()
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')
 # Main loop of this game
while len(empty_cells(board)) > 0 and not game_over(board):
if first == 'N':
ai_turn(c_choice, h_choice)
first = ''

human_turn(c_choice, h_choice)
ai_turn(c_choice, h_choice)

# Game over message

if wins(board, HUMAN):
clean()
print(f'Human turn [{h_choice}]')
render(board, c_choice, h_choice)
print('YOU WIN!')
elif wins(board, COMP):
clean()
print(f'Computer turn [{c_choice}]')
render(board, c_choice, h_choice)
print('YOU LOSE!')
else:
clean()
render(board, c_choice, h_choice)
print('DRAW!')

exit()

if _name_ == '_main_':
main()

Output:
 Practical no-6A
Write a program to solve missionaries and cannibals problem
Code:
print("\n")
print("\tGame Start\nNow the task is to move all of them to right side of the river")
print("rules:\n1. The boat can carry at most two people\n2. If cannibals num greater then
missionaries then the cannibals would eat the missionaries\n3. The boat cannot cross the river by
itself with no people on board")
lM = 3
lC = 3
rM=0
rC=0
userM = 0
userC = 0
k=0
print("\nM M M C C C | --- | \n")
try:
while(True):
while(True):
print("Left side -> right side river travel")

uM = int(input("Enter number of Missionaries travel => "))

 uC = int(input("Enter number of Cannibals travel => "))

if((uM==0)and(uC==0)):
print("Empty travel not possible")
print("Re-enter : ")
elif(((uM+uC) <= 2)and((lM-uM)>=0)and((lC-uC)>=0)):
break
else:
print("Wrong input re-enter : ")
lM = (lM-uM)
lC = (lC-uC)
rM += uM
rC += uC

print("\n")
for i in range(0,lM):
print("M ",end="")
for i in range(0,lC):
print("C ",end="")
print("| --> | ",end="")
for i in range(0,rM):
print("M ",end="")
for i in range(0,rC):
print("C ",end="")
print("\n")

k +=1

if(((lC==3)and (lM == 1))or((lC==3)and(lM==2))or((lC==2)and(lM==1))or((rC==3)and

(rM == 1))or((rC==3)and(rM==2))or((rC==2)and(rM==1))):
print("Cannibals eat missionaries:\nYou lost the game")

break

if((rM+rC) == 6):
print("You won the game : \n\tCongrats")
print("Total attempt")
print(k)
break
while(True):
print("Right side -> Left side river travel")
userM = int(input("Enter number of Missionaries travel => "))
userC = int(input("Enter number of Cannibals travel => "))

if((userM==0)and(userC==0)):
print("Empty travel not possible")
print("Re-enter : ")
elif(((userM+userC) <= 2)and((rM-userM)>=0)and((rC-userC)>=0)):
break
else:
print("Wrong input re-enter : ")
 lM += userM
lC += userC
rM -= userM
rC -= userC

k +=1
print("\n")
for i in range(0,lM):
print("M ",end="")
for i in range(0,lC):
print("C ",end="")
print("| <-- | ",end="")
for i in range(0,rM):
print("M ",end="")
for i in range(0,rC):
print("C ",end="")
print("\n")

if(((lC==3)and (lM == 1))or((lC==3)and(lM==2))or((lC==2)and(lM==1))or((rC==3)and

(rM == 1))or((rC==3)and(rM==2))or((rC==2)and(rM==1))):
print("Cannibals eat missionaries:\nYou lost the game")
break
except EOFError as e:
print("\nInvalid input please retry !!")

Output: