AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 1

DATE: 02.08.2023

IMPLEMENTATION OF INTELLIGENT AGENTS –

VACUUM WORLD PROBLEM

QUESTION:

Implement intelligent agents – Vacuum world problem.

AIM:

To implement intelligent agents – Vacuum world problem.

ALGORITHM:

1. Start
2. Declare a list of elements with 0 representing absence of dirt and 1
representing presence of dirt.
3. Use random module to access the elements randomly
4. Clean the dirt if the value is 1
5. Calculate the cost as 1 for moving from one index to another and for
sucking the dirt
6. Keep track of the visited indices to optimise the solution
7. Display the total path cost
8. Stop

PROGRAM:

import random as rd
a=[1,0,1,1,0,0,1]
n=len(a)
visited=[]
count=0
cost=-1
while(count<n+1):
while(True):
i=rd.randint(0,n-1)

Roll Number: 2127220502065 Page No.:

 if(i not in visited):
count+=1
break
print("At index: ",i,end="\t")
cost+=1
print("Total path cost: ",cost)
visited.append(i)
if (a[i]==1):
a[i]=0
cost+=1
print("---Sucking dirt---")
print("Total path cost:
",cost)

SAMPLE INPUT AND OUTPUT:

At index: 2 Total path cost: 0

---Sucking dirt---
Total path cost: 1
At index: 6 Total path cost: 2
---Sucking dirt---
Total path cost:
3
At index: 0 Total path cost: 4
---Sucking dirt---
Total path cost: 5
At index: 1 Total path cost: 6
At index: 5 Total path cost: 7
At index: 3 Total path cost: 8
---Sucking dirt---
Total path cost: 9
At index: 4 Total path cost: 10

RESULT:

Thus, the program has been implemented and executed successfully.

Roll Number: 2127220502065 Page No.:
 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 2a
DATE:
16.08.2023
IMPLEMENTATION OF BASIC SEARCH STRATEGIES –
8-PUZZLE PROBLEM

QUESTION:

Implement basic search strategy – 8-Puzzle problem.

AIM:

To implement basic search strategy – 8-Puzzle problem.

ALGORITHM:

1. Start
2. Define a function find_next() .
3. Define moves = a map defining moves as a list corresponding to each value
4. Define a function get_paths()
5. Find the paths using the given functions along with a count variable
6. Keep track of new paths and new lists
7. Display the number of moves to solve the problem
8. Stop

PROGRAM:

class Solution:
def solve(self, board):
dict = {}
flatten =
[]
for i in range(len(board)):
flatten += board[i]
flatten =
tuple(flatten)

dict[flatten] = 0
Roll Number: 2127220502065 Page No.:
 if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0

return self.get_paths(dict)

def get_paths(self, dict):

cnt = 0
while
True:
current_nodes = [x for x in dict if dict[x] == cnt]
if len(current_nodes) == 0:
return -1

for node in current_nodes:

next_moves = self.find_next(node)
for move in next_moves:
if move not in dict:
dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1

def find_next(self, node):

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

results = []
pos_0 = node.index(0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
results.append(tuple(new_node))

return results
ob = Solution()
matrix = [

Roll Number: 2127220502065 Page No.:

 [3, 1, 2],
[4, 7, 5],
[6, 8, 0]]
print("No. of moves = ",ob.solve(matrix))

SAMPLE INPUT AND OUTPUT:

No. of moves = 4

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502065 Page No.:
 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 2b
DATE:
16.08.2023
IMPLEMENTATION OF BASIC SEARCH STRATEGIES –
8-QUEENS PROBLEM

QUESTION:

Implement basic search strategy – 8-Queens problem.

AIM:

To implement basic search strategy – 8-Queens problem.

ALGORITHM:

1. Start
2. Create an 8x8 board.
3. Create user-defined functions for checking whether any of the queens can
attack each other and for placing the queens on the board by
implementing a recursive function
4. Backtrack if the position is not right
5. Display the result as an 8x8 board with the queens placed.
6. Stop

PROGRAM:

N=8
board = [[0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
def attack(i, j):
for k in range(0,N):
if board[i][k]==1 or board[k][j]==1:
return True
for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j):

Roll Number: 2127220502065 Page No.:

 if board[k][l]==1:
return True
return False
def
N_queens(n):
if n==0:
return True
for i in range(0,N):
for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
if N_queens(n-1)==True:
return True
board[i][j] = 0
return False
N_queens(N)
for i in board:
print (i)

SAMPLE INPUT AND OUTPUT:

Enter the number of queens: 8

[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502065 Page No.:

 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 3

DATE: 13.09.2023

IMPLEMENT A* ALGORITHM – ROUTE-FINDING PROBLEM

QUESTION:

Implement A* algorithm – Route-finding problem.

AIM:

To implement A* algorithm – Route-finding problem.

ALGORITHM:

1. Place the starting node in the list.

2. Check if the list is empty or not, if the list is empty then return failure and
stops.
3. Select the node from the list which has the smallest value of evaluation
function (g+h), if node n is goal node then return success and stop,
otherwise
4. Expand node n and generate all of its successors, and put n into a second
list. For each successor n', check whether n' is already in the first or
second list, if not then compute evaluation function for n' and place into
first list.
5. Else if node n' is already in both the lists, then it should be attached to the
back pointer which reflects the lowest g(n') value.
6. Return to Step 2.
7. Display the result
8. Stop

PROGRAM:

def aStarAlgo(start_node, stop_node):

open_set = set(start_node)
closed_set = set()
g = {}

Roll Number: 2127220502065 Page No.:

 parents = {}
#distance of starting node from itself is zero
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
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):
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
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
if n == None:
print('Path does not exist!')
return None
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
open_set.remove(n)
closed_set.add(n)
print('Path does not exist!')
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:

Roll Number: 2127220502065 Page No.:

 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')

SAMPLE INPUT AND OUTPUT:

Path found: ['A', 'F', 'G', 'I', 'J']

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502065 Page No.:

 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 4

DATE: 20.09.2023

MINIMAX ALGORITHM – ALPHA BETA PRUNING

QUESTION:

Implement Minimax algorithm – Alpha beta pruning.

AIM:

To implement Minimax algorithm – Alpha beta pruning.

ALGORITHM:

1. Start
2. Declare max and min values for alpha-beta pruning
3. Create a user-defined function “minimax” with depth, nodeindex,
maximising or minimising player as a Boolean value. Alpha, beta and
target depth values
4. If maximising player, compare with alpha else compare with beta
5. Assign the values to the nodes corresponding to the results of the
comparison
6. Display the optimal value
7. Stop
PROGRAM:
import math
MAX = 1000
MIN = -1000
def minimax(depth, nodeIndex, maximizingPlayer, values, alpha,
beta,targetdepth):

if depth==targetdepth:
return values[nodeIndex]

if maximizingPlayer:
best = MIN

Roll Number: 2127220502065 Page No.:

 for i in range(0, targetdepth-1):
val = minimax(depth + 1, nodeIndex * 2 + i,
False, values, alpha, beta,targetdepth)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha:
break
return best

else:
best = MAX
for i in range(0, targetdepth-1):
val = minimax(depth + 1, nodeIndex * 2 + i,
True, values, alpha, beta,targetdepth)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha:
break
return best

values = [3, 5, 2, 9, 12, 5, 23, 23]

treeDepth = int(math.log(len(values),
2))
print("The optimal value is :", minimax(0, 0, True, values, MIN,
MAX,treeDepth))

SAMPLE INPUT AND OUTPUT:

The optimal value is: 12

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502065 Page No.:

 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 5a
DATE:
04.10.2023
CONSTRAINT SATISFACTION PROBLEM – CRYPTARITHMETIC

QUESTION:

Implement Constraint satisfaction problem – Cryptarithmetic problem.

AIM:

To implement Constraint satisfaction problem – Cryptarithmetic problem.

ALGORITHM:

1. Start
2. Import itertools
3. Create user-defined functions to get values and to solve the equation
containing the letters using the concept of permutations
4. Convert the solution into a dictionary and zip it as one iterable variable
5. Print all the possible combinations of the letters
6. Stop
PROGRAM:
import
itertools
def get_value(word, substitution):
s=0
factor = 1
for letter in reversed(word):
s += factor * substitution[letter]
factor *= 10
return s
def solve2(equation):
left, right = equation.lower().replace(' ', '').split('=')
left = left.split('+')
letters = set(right)
for word in left:
for letter in word:
letters.add(letter)

Roll Number: 2127220502065 Page No.:

 letters = list(letters)
digits = range(10)
for perm in itertools.permutations(digits, len(letters)):
sol = dict(zip(letters, perm))
if sum(get_value(word, sol) for word in left) == get_value(right, sol):
print(' + '.join(str(get_value(word, sol)) for word in left) + " =
{}".format(get_value(right, sol), sol))
if __name__ == '__main__':
print('SEND + MORE = MONEY')
solve2('SEND + MORE =
MONEY')

SAMPLE INPUT AND OUTPUT:

SEND + MORE = MONEY

9567 + 1085 = 10652
2817 + 368 = 3185
2819 + 368 = 3187
3712 + 467 = 4179
3719 + 457 = 4176
3821 + 468 = 4289
3829 + 458 = 4287
5731 + 647 = 6378
5732 + 647 = 6379
5849 + 638 = 6487
6415 + 734 = 7149
6419 + 724 = 7143
6524 + 735 = 7259
6851 + 738 = 7589
6853 + 728 = 7581
7316 + 823 = 8139
7429 + 814 = 8243
7531 + 825 = 8356
7534 + 825 = 8359
7539 + 815 = 8354
7643 + 826 = 8469
7649 + 816 = 8465
8324 + 913 = 9237
8432 + 914 = 9346
8542 + 915 = 9457

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502068 Page No.:

 AD22311 – ARTIFICIAL INTELIGENCE LABORATORY

EX.NO: 5b
DATE:
04.10.2023
CONSTRAINT SATISFACTION PROBLEM – MAP COLOURING

QUESTION:

Implement Constraint satisfaction problem – Map colouring.

AIM:

To implement Constraint satisfaction problem – Map colouring.

ALGORITHM:

1. Start
2. Create a function to colour the vertices with a list of vertices and coloured
vertices and keep track of unused colours with respect to colour and
connected vertices
3. Check the neighbouring vertices before colouring the vertices every time
4. Colour the vertex if the colour is unused
5. Repeat this process till all the vertices are coloured
6. Display the coloured graph
7. Stop

PROGRAM:

def colour_vertices(graph):
vertices = sorted((list(graph.keys())))
colour_graph = {}
for vertex in vertices:
unused_colours = len(vertices) * [True]
for neighbor in graph[vertex]:
if neighbor in colour_graph:
colour = colour_graph[neighbor]
unused_colours[colour] = False
for colour, unused in enumerate(unused_colours):
if unused:

Roll Number: 2127220502068 Page No.:

 colour_graph[vertex] = colour
break
return colour_graph
graph = { "a" : ["c", "d", "b", "e"],
"b" : ["c", "e", "a"],
"c" : ["a", "b"],
"d" : ["a","e"],
"e" : ["d", "b", "a"], }
result = (colour_vertices(graph))
colour_code={0:’red’,1:’blue’,2:’green’}
for i in result:
result[i]=colour_code[result[i]]
print(result)

SAMPLE INPUT AND OUTPUT:

{'a': ‘red’, 'b': ‘blue’, 'c': ‘green’, 'd': ‘blue’, 'e': ‘green’}

RESULT:

Thus, the program has been executed successfully.

Roll Number: 2127220502068 Page No.: