Practical 1A) Write a program to implement depth first search algorithm.

Program:

​

# DFS algorithm

def dfs(graph, start, visited=None):

    if visited is None:

        visited = set()

    visited.add(start)

    print(start)

    for next in graph[start] - visited:

        dfs(graph, next, visited)

    return visited

​

graph = {'0': set(['1', '2']),

         '1': set(['0', '3', '4']),

         '2': set(['0']),

         '3': set(['1']),

         '4': set(['2', '3'])}

​

dfs(graph, '0')

​

​

Practical 1B) Write a program to implement breadth first search algorithm.

Program:

graph = {

  '5' : ['3','7'],

  '3' : ['2', '4'],

  '7' : ['8'],

  '2' : [],

  '4' : ['8'],

  '8' : []

}

​

visited = [] # List for visited nodes.

queue = []     #Initialize a queue

​

def bfs(visited, graph, node): #function for BFS

visited.append(node)

    queue.append(node)

    while queue:          # Creating loop to visit each node

            m = queue.pop(0) 

            print (m, end = " ") 

​

        for neighbour in graph[m]:

            if neighbour not in visited:

                    visited.append(neighbour)

                    queue.append(neighbour)

​

# Driver Code

print("Following is the Breadth-First Search")

bfs(visited, graph, '5')    # function calling

​

​

​

Practical 2A) Write a program to simulate 4-Queen / N-Queen problem.

Program:

​

global N

N = 4

def printSolution(board):

    for i in range(N):

        for j in range(N):

            print (board[i][j],end=' ')

        print()

​

def isSafe(board, row, col):

    # Check this row on left side

    for i in range(col):

        if board[row][i] == 1:

            return False

    # Check upper diagonal on left side

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

    # Check lower diagonal on left side

    for i, j in zip(range(row, N, 1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

    return True

def solveNQUtil(board, col):

    # base case: If all queens are placed

    # then return true

    if col >= N:

        return True

    for i in range(N):

        if isSafe(board, i, col):

            board[i][col] = 1

            if solveNQUtil(board, col + 1) == True:

                return True

            board[i][col] = 0

    return False

​

def solveNQ():

    board = [ [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0] ]

    if solveNQUtil(board, 0) == False:

        print ("Solution does not exist")

        return False

    printSolution(board)

    return True

​

solveNQ()

​

​

Practical 2B) Write a program to solve tower of Hanoi problem.

Program:

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 = 3

TowerOfHanoi(n,'A','B','C')

# A, C, B are the name of rods

​

​

# Alpha-Beta Pruning

print("Practical 3a - Alpha Beta Search")

print("\nDharmik Pansuriya 53003200001")

# Initial values of Alpha and Beta

MAX, MIN = 100, -100

​

# Returns optimal value for current player

def minmax(depth, nodeIndex, maximizingPlayer, values, alpha, beta):

    # Terminating condition. i.e     # leaf node is reached

    if depth == 4:

        return values[nodeIndex]

    if maximizingPlayer:

        best = MIN

        # Recur for left and right children

        for i in range(0, 2):

            val = minmax(depth + 1, nodeIndex * 2 + i,

                         False, values, alpha, beta)

            best = max(best, val)

            alpha = max(alpha, best)

            # Alpha Beta Pruning

            if alpha >= beta:

                print(alpha)

                break

        return best

    else:

        best = MAX

​

        # Recur for left and

        # right children

        for i in range(0, 2):

​

            val = minmax(depth + 1, nodeIndex * 2 +

                         i, True, values, alpha, beta)

            best = min(best, val)

            beta = min(beta, best)

​

            # Alpha Beta Pruning

            if beta <= alpha:

                print(beta)

                break

​

        return best

# Driver Code

if __name__ == "__main__":

​

    values = [10, 11, 9, 12, 14, 15, 13, 14, 5, 2, 4,

              1, 3, 22, 20, 21]  # [2, 3, 5, 9, 0, 1, 7, 5]

    print("The optimal value is :", minmax(0, 0, True, values, MIN, MAX))

​

​

​

PRACTICAL : 3A ALPHA BETA SEARCH

​

# Alpha-Beta Pruning

print("Practical 3a - Alpha Beta Search")

print("\nDharmik Pansuriya 53003200001")

# Initial values of Alpha and Beta

MAX, MIN = 100, -100

​

# Returns optimal value for current player

def minmax(depth, nodeIndex, maximizingPlayer, values, alpha, beta):

    # Terminating condition. i.e     # leaf node is reached

    if depth == 4:

        return values[nodeIndex]

    if maximizingPlayer:

        best = MIN

        # Recur for left and right children

        for i in range(0, 2):

            val = minmax(depth + 1, nodeIndex * 2 + i,

                         False, values, alpha, beta)

            best = max(best, val)

            alpha = max(alpha, best)

            # Alpha Beta Pruning

            if alpha >= beta:

                print(alpha)

                break

        return best

    else:

        best = MAX

​

        # Recur for left and

        # right children

        for i in range(0, 2):

​

            val = minmax(depth + 1, nodeIndex * 2 +

                         i, True, values, alpha, beta)

            best = min(best, val)

            beta = min(beta, best)

​

            # Alpha Beta Pruning

            if beta <= alpha:

                print(beta)

                break

​

        return best

# Driver Code

if __name__ == "__main__":

​

    values = [10, 11, 9, 12, 14, 15, 13, 14, 5, 2, 4,

              1, 3, 22, 20, 21]  # [2, 3, 5, 9, 0, 1, 7, 5]

    print("The optimal value is :", minmax(0, 0, True, values, MIN, MAX))

​

​

PRACTICAL:3B HILL CLIMBING:

print("Practical 3b - Hill Climbing")

print("Dharmik Pansuriya - 53003200001\n")

import math

increment = 0.1

startingPoint = [1, 1]

point1 = [1,5]

point2 = [6,4]

point3 = [5,2]

point4 = [2,1]

def distance(x1, y1, x2, y2):

    dist = math.pow(x2-x1, 2) + math.pow(y2-y1, 2)

    return dist

def sumOfDistances(x1, y1, px1, py1, px2, py2, px3, py3, px4, py4):

    d1 = distance(x1, y1, px1, py1)

    d2 = distance(x1, y1, px2, py2)

    d3 = distance(x1, y1, px3, py3)

    d4 = distance(x1, y1, px4, py4)

    return d1 + d2 + d3 + d4

def newDistance(x1, y1, point1, point2, point3, point4):

    d1 = [x1, y1]

    d1temp = sumOfDistances(x1, y1, point1[0],point1[1], point2[0],point2[1],point3[0],point3[1],

point4[0],point4[1] )

    d1.append(d1temp)

    return d1

minDistance = sumOfDistances(startingPoint[0], startingPoint[1], point1[0],point1[1],

point2[0],point2[1],point3[0],point3[1], point4[0],point4[1] )

flag = True

def newPoints(minimum, d1, d2, d3, d4):

    if d1[2] == minimum:

        return [d1[0], d1[1]]

    elif d2[2] == minimum:

        return [d2[0], d2[1]]

    elif d3[2] == minimum:

        return [d3[0], d3[1]]

    elif d4[2] == minimum:

        return [d4[0], d4[1]]

i = 1

while flag:

    d1 = newDistance(startingPoint[0]+increment, startingPoint[1], point1, point2, point3, point4)

    d2 = newDistance(startingPoint[0]-increment, startingPoint[1], point1, point2, point3, point4)

    d3 = newDistance(startingPoint[0], startingPoint[1]+increment, point1, point2, point3, point4)

    d4 = newDistance(startingPoint[0], startingPoint[1]-increment, point1, point2, point3, point4)

    print (i,'', round(startingPoint[0], 2), round(startingPoint[1], 2))

    minimum = min(d1[2], d2[2], d3[2], d4[2])

    if minimum < minDistance:

        startingPoint = newPoints(minimum, d1, d2, d3, d4)

        minDistance = minimum

 #print I,’ ‘, round(startingPoint[0], 2), round(startingPoint[1], 2)

        i+=1

    else:

        flag = False

​

​

​

​

practical4a:A-Star

​

# A-Star

print("Practical 4a - A* Algorithm")

print("Dharmik Pansuriya - 53003200001\n")

​

def aStarAlgo(start_node, stop_node):

    open_set = set(start_node)

    closed_set = set()

    g = {}  # store distance from starting node

    parents = {}         # parents contains an adjacency map of all nodes

    # distance of starting node from itself is zero

    g[start_node] = 0

    parents[start_node] = start_node

    while len(open_set) > 0:

        n = None

        # node with lowest f() is found

        for v in open_set:

            if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):

                n = v

        if n == stop_node or Graph_nodes[n] == None:

            pass

        else:

            for (m, weight) in get_neighbors(n):

                # nodes 'm' not in first and last set are added to first

                # n is set its parent

                if m not in open_set and m not in closed_set:

                    open_set.add(m)

                    parents[m] = n

                    g[m] = g[n] + weight

                else:

                    if g[m] > g[n] + weight:

                        # update g(m)

                        g[m] = g[n] + weight

                        # change parent of m to n

                        parents[m] = n

                        # if m in closed set,remove and add to open

                        if m in closed_set:

                            closed_set.remove(m)

                            open_set.add(m)

        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:

            path = []

            while parents[n] != n:

                path.append(n)

                n = parents[n]

            path.append(start_node)

            path.reverse()

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

            return path

        # remove n from the open_list, and add it to closed_list  because all of his neighbors were inspected

        open_set.remove(n)

        closed_set.add(n)

    print('Path does not exist!')

    return None

​

# define fuction to return neighbor and its distance from the passed node

​

def get_neighbors(v):

    if v in Graph_nodes:

        return Graph_nodes[v]

    else:

        return None

​

def heuristic(n):

    H_dist = {

        'A': 11,

        'B': 6,

        'C': 5,

        'D': 7,

        'E': 3,

        'F': 6,

        'G': 5,

        'H': 3,

        'I': 1,

        'J': 0

    }

    return H_dist[n]

​

Graph_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': [('E', 5), ('G', 3), ('H', 2), ('J', 3)],

}

aStarAlgo('A', 'J')

​

​

4B) AO Star

​

# AO-star algorithm

print("Practical 4b - AO* Algorithm")

print("Dharmik Pansuriya - 53003200001\n")

​

class Graph:

    # instantiate graph object with graph topology, heuristic values, start node

    def __init__(self, graph, heuristicNodeList, startNode):

        self.graph = graph

        self.H = heuristicNodeList

        self.start = startNode

        self.parent = {}

        self.status = {}

        self.solutionGraph = {}

​

    def applyAOStar(self):  # starts a recursive AO* algorithm

        self.aoStar(self.start, False)

​

    def getNeighbors(self, v):  # gets the Neighbors of a given node

        return self.graph.get(v, '')

​

    def getStatus(self, v):  # return the status of a given node

        return self.status.get(v, 0)

​

    def setStatus(self, v, val):  # set the status of a given node

        self.status[v] = val

​

    def getHeuristicNodeValue(self, n):

        # always return the heuristic value of a given node

        return self.H.get(n, 0)

​

    def setHeuristicNodeValue(self, n, value):

        self.H[n] = value  # set the revised heuristic value of a given node

​

    def printSolution(self):

        print("FOR GRAPH SOLUTION, TRAVERSE THE GRAPH FROM THE START NODE:", self.start)

        print("------------------------------------------------------------")

        print(self.solutionGraph)

        print("------------------------------------------------------------")

​

    # Computes the Minimum Cost of child nodes of a given node v

    def computeMinimumCostChildNodes(self, v):

        minimumCost = 0

        costToChildNodeListDict = {}

        costToChildNodeListDict[minimumCost] = []

        flag = True

        # iterate over all the set of child node/s

        for nodeInfoTupleList in self.getNeighbors(v):

            cost = 0

            nodeList = []

            for c, weight in nodeInfoTupleList:

                cost = cost+self.getHeuristicNodeValue(c)+weight

                nodeList.append(c)

            if flag == True:  # initialize Minimum Cost with the cost of first set of child node/s

                minimumCost = cost

                # set the Minimum Cost child node/s

                costToChildNodeListDict[minimumCost] = nodeList

                flag = False

            else:  # checking the Minimum Cost nodes with the current Minimum Cost

                if minimumCost > cost:

                    minimumCost = cost

                    # set the Minimum Cost child node/s

                    costToChildNodeListDict[minimumCost] = nodeList

        # return Minimum Cost and Minimum Cost child node/s

        return minimumCost, costToChildNodeListDict[minimumCost]

​

    def aoStar(self, v, backTracking):  # AO* algorithm for a start node and backTracking status flag

        print("HEURISTIC VALUES :", self.H)

        print("SOLUTION GRAPH :", self.solutionGraph)

        print("PROCESSING NODE :", v)

        print("-----------------------------------------------------------------------------------------")

        if self.getStatus(v) >= 0:  # if status node v >= 0, compute Minimum Cost nodes of v

            minimumCost, childNodeList = self.computeMinimumCostChildNodes(v)

            print(minimumCost, childNodeList)

            self.setHeuristicNodeValue(v, minimumCost)

            self.setStatus(v, len(childNodeList))

            solved = True  # check the Minimum Cost nodes of v are solved

            for childNode in childNodeList:

                self.parent[childNode] = v

                if self.getStatus(childNode) != -1:

                    solved = solved & False

            # if the Minimum Cost nodes of v are solved, set the current node status as solved(-1)

            if solved == True:

                self.setStatus(v, -1)

                # update the solution graph with the solved nodes which may be a part of solution

                self.solutionGraph[v] = childNodeList

            if v != self.start:

                self.aoStar(self.parent[v], True)

            if backTracking == False:  # check the current call is not for backtracking

                for childNode in childNodeList:  # for each Minimum Cost child node

                    # set the status of child node to 0(needs exploration)

                    self.setStatus(childNode, 0)

                    self.aoStar(childNode, False)

​

print("Graph - 1")

h1 = {'A': 1, 'B': 6, 'C': 2, 'D': 12, 'E': 2,

      'F': 1, 'G': 5, 'H': 7, 'I': 7, 'J': 1}

graph1 = {

    'A': [[('B', 1), ('C', 1)], [('D', 1)]],

    'B': [[('G', 1)], [('H', 1)]],

    'C': [[('J', 1)]],

    'D': [[('E', 1), ('F', 1)]],

    'G': [[('I', 1)]]

}

G1 = Graph(graph1, h1, 'A')

G1.applyAOStar()

G1.printSolution()

​

​

Practical5a: WaterJug

​

print("Practical 5a - WaterJug")

print("Dharmik Pansuriya - 53003200001\n")

class Waterjug:

    def __init__(self,am,bm,a,b,g):

        self.a_max = am;

        self.b_max = bm;

        self.a = a;

        self.b= b;

        self.goal =g;

    def fillA(self):

        self.a=self.a_max;

        print ( self.a,self.b)

    def fillB(self):

        self.b= self.b_max;

        print (self.a,self.b)

    def emptyA(self):

        self.a = 0;

        print (self.a,self.b)

    def emptyB(self):

        self.b = 0;

        print (self.a,self.b)

    def transferAtoB(self):

        while (True):

            self.a = self.a- 1

            self.b=self.b+1

            if (self.a == 0 or self.b ==self.b_max):

                break

            print(self.a, self.b)

    def main(self):

        while (True):

            if (self.a == self.goal or self.b == self.goal):

                break

            if (self.a == 0):

                self.fillA()

            elif (self.a > 0 and self.b != self.b_max):

                self.transferAtoB()

            elif (self.a > 0 and self.b == self.b_max):

                self.emptyB()

waterjug=Waterjug(4,3,0,0,2);

waterjug.main();

​

​

Practical 5B) Tic Tac Tow using Min Max Algo

​

​

print("Practical 5b - Tic Tac Toe")

print("Dharmik Pansuriya - 53003200001\n")

def printBoard(board):

    print(board[1]+'|'+board[2]+'|'+board[3])

    print('-+-+-')

    print(board[4] + '|' + board[5] + '|' + board[6])

    print('-+-+-')

    print(board[7] + '|' + board[8] + '|' + board[9])

    print('\n')

​

def spaceIsFree(position):

    if board[position] == ' ':

        return True

    else:

        return False

​

def insertLetter(letter, position):

    if spaceIsFree(position):

        board[position] = letter

        printBoard(board)

        if (checkDraw()):

            print("Draw!")

            exit()

        if checkForWin():

            if letter == 'X':

                print("Bot Wins")

                exit()

            else:

                print("Player wins!!")

                exit()

        return

    else:

        print("Can insert there!")

        position = int(input("Please enter new position:   "))

        insertLetter(letter, position)

        return

​

def checkForWin():

    if (board[1] == board[2] and board[1] == board[3] and board[1] != ' '):

        return True

    elif (board[4] == board[5] and board[4] == board[6] and board[4] != ' '):

        return True

    elif (board[7] == board[8] and board[7] == board[9] and board[7] != ' '):

        return True

    elif (board[1] == board[4] and board[1] == board[7] and board[1] != ' '):

        return True

    elif (board[2] == board[5] and board[2] == board[8] and board[2] != ' '):

        return True

    elif (board[3] == board[6] and board[3] == board[9] and board[3] != ' '):

        return True

    elif (board[1] == board[5] and board[1] == board[9] and board[1] != ' '):

        return True

    elif (board[7] == board[5] and board[7] == board[3] and board[7] != ' '):

        return True

    else:

        return False

​

def checkWhichMarkWon(mark):

    if (board[1] == board[2] and board[1] == board[3] and board[1] == mark):

        return True

    elif (board[4] == board[5] and board[4] == board[6] and board[4] == mark):

        return True

    elif (board[7] == board[8] and board[7] == board[9] and board[7] == mark):

        return True

    elif (board[1] == board[4] and board[1] == board[7] and board[1] == mark):

        return True

    elif (board[2] == board[5] and board[2] == board[8] and board[2] == mark):

        return True

    elif (board[3] == board[6] and board[3] == board[9] and board[3] == mark):

        return True

    elif (board[1] == board[5] and board[1] == board[9] and board[1] == mark):

        return True

    elif (board[7] == board[5] and board[7] == board[3] and board[7] == mark):

        return True

    else:

        return False

​

def checkDraw():

    for key in board.keys():

        if (board[key] == ' '):

            return False

    return True

​

def playerMove():

    position = int(input("Enter position for O:  "))

    insertLetter(player, position)

    return

​

def compMove():

    bestScore = -800

    bestMove = 0

    for key in board.keys():

        if (board[key] == ' '):

            board[key] = bot

            score = minimax(board, 0, False)

            board[key] = ' '

            if (score > bestScore):

                bestScore = score

                bestMove = key

​

    insertLetter(bot, bestMove)

    return

​

​

def minimax(board, depth, isMaximizing):

    if (checkWhichMarkWon(bot)):

        return 1

    elif (checkWhichMarkWon(player)):

        return -1

    elif (checkDraw()):

        return 0

​

    if (isMaximizing):

        bestScore = -800

        for key in board.keys():

            if (board[key] == ' '):

                board[key] = bot

                score = minimax(board, depth + 1,  False)

                board[key] = ' '

                if (score > bestScore):

                    bestScore = score

        return bestScore

    else:

        bestScore = 800

​

        for key in board.keys():

            if (board[key] == ' '):

                board[key] = player

                score = minimax(board, depth + 1, True)

                board[key] = ' '

                if (score < bestScore):

                    bestScore = score

        return bestScore

​

​

board = {1: ' ', 2: ' ', 3: ' ',

         4: ' ', 5: ' ', 6: ' ',

         7: ' ', 8: ' ', 9: ' '}

​

printBoard(board)

print("Computer goes first! Good Luck.")

print("position are as follows:")

print("1, 2, 3 ")

print("4, 5, 6 ")

print("7, 8, 9 ")

print("\n")

player = 'O'

bot = 'X'

​

global firstComputerMove

firstComputerMove = True

​

while not checkForWin():

    compMove()

    playerMove()

​

​

​

Practical 6A) Shuffle Deck Of Card

​

print("Practical 6 - Card Shuffle")

print("Dharmik Pansuriya - 53003200001\n")

import itertools, random

deck=list(itertools.product(range(1,14),['spade','Heart','Diamond','Club']))

random.shuffle(deck)

print("You got: ")

for i in range(5):

    print(deck[i][0],"of",deck[i][1])

​

​

PROLOG::::

​

Practical 7a:ASSOCIATIVE LAW

​

student(rocky).

student(rony).

hscstudent(rocky).

sscstudent(rocky).

sscstudent(rony).

nondetermhscstudent(X).

nondetermsscstudent(X).

lbscitadmission(X):-((student(X),hscstudent(X)),sscstudent(X)).

rbscitadmission(X):-(student(X),(hscstudent(X),sscstudent(X))).

​

Practical 7b:DISTRIBUTIVE LAW

​

male(davinci).

male(vangogh).

artist(davinci).

artist(vangogh).

sculptor(davinci).

lmorefamous(X):-male(X),(artist(X),sculptor(X)).

rmorefamous(X):-((male(X),artist(X));(male(X),sculptor(X))).

​

Practical 8a:DERIVE THE PREDICATE

​

batsman(aniket,batsman).

cricketer(batsman,cricketer).

nondetermbatsman(X,Y).

nondetermcricketer(X,Y).

profile(X,Y):-batsman(X,Z),cricketer(Z,Y).

​

Practical 8b:ANSWER FROM PREDICATE

​

father_of(joe,paul).

father_of(joe,mary).

mother_of(jane,paul).

mother_of(jane,mary).

male(paul).

male(joe).

female(mary).

female(jane).

male(X):-father_of(X,Y).

female(X):-mother_of(X,Y).

son_of(X,Y):-father_of(Y,X),male(X).

son_of(X,Y):-mother_of(Y,X),male(X).

daughter_of(X,Y):-father_of(Y,X),female(X).

daughter_of(X,Y):-mother_of(Y,X),female(X).

​