Ex.

No:1(a) Implement Basic search strategies – 8 Puzzle

Date:

INPUT:
import copy

# Importing the heap methods from the python

# library for the Priority Queue
from heapq import heappush, heappop

# This particular var can be changed to transform

# the program from 8 puzzle(n=3) into 15
# puzzle(n=4) and so on ...
n=3

# bottom, left, top, right

rows = [ 1, 0, -1, 0 ]
cols = [ 0, -1, 0, 1 ]

# creating a class for the Priority Queue

class priorityQueue:

# Constructor for initializing a

# Priority Queue
def __init__(self):
self.heap = []

# Inserting a new key 'key'

def push(self, key):
heappush(self.heap, key)

# funct to remove the element that is minimum,

# from the Priority Queue
def pop(self):
return heappop(self.heap)

# funct to check if the Queue is empty or not

def empty(self):
if not self.heap:
return True
else:
return False

# structure of the node

class nodes:

def __init__(self, parent, mats, empty_tile_posi,

costs, levels):

# This will store the parent node to the

# current node And helps in tracing the
# path when the solution is visible
self.parent = parent

# Useful for Storing the matrix

self.mats = mats

# useful for Storing the position where the

# empty space tile is already existing in the matrix
self.empty_tile_posi = empty_tile_posi

# Store no. of misplaced tiles

self.costs = costs

# Store no. of moves so far

self.levels = levels

# This func is used in order to form the

# priority queue based on
# the costs var of objects
def __lt__(self, nxt):
return self.costs < nxt.costs

# method to calc. the no. of

# misplaced tiles, that is the no. of non-blank
# tiles not in their final posi
def calculateCosts(mats, final) -> int:

count = 0
for i in range(n):
for j in range(n):
if ((mats[i][j]) and
(mats[i][j] != final[i][j])):
count += 1

return count

def newNodes(mats, empty_tile_posi, new_empty_tile_posi,

levels, parent, final) -> nodes:

# Copying data from the parent matrixes to the present matrixes

new_mats = copy.deepcopy(mats)

# Moving the tile by 1 position

x1 = empty_tile_posi[0]
y1 = empty_tile_posi[1]
x2 = new_empty_tile_posi[0]
y2 = new_empty_tile_posi[1]
new_mats[x1][y1], new_mats[x2][y2] = new_mats[x2][y2], new_mats[x1][y1]

# Setting the no. of misplaced tiles

costs = calculateCosts(new_mats, final)

new_nodes = nodes(parent, new_mats, new_empty_tile_posi,

costs, levels)
return new_nodes

# func to print the N by N matrix

def printMatsrix(mats):

for i in range(n):
for j in range(n):
print("%d " % (mats[i][j]), end = " ")

print()

# func to know if (x, y) is a valid or invalid

# matrix coordinates
def isSafe(x, y):

return x >= 0 and x < n and y >= 0 and y < n

# Printing the path from the root node to the final node
def printPath(root):

if root == None:
return

printPath(root.parent)
printMatsrix(root.mats)
print()

# method for solving N*N - 1 puzzle algo

# by utilizing the Branch and Bound technique. empty_tile_posi is
# the blank tile position initially.
def solve(initial, empty_tile_posi, final):

# Creating a priority queue for storing the live

# nodes of the search tree
pq = priorityQueue()

# Creating the root node

costs = calculateCosts(initial, final)
root = nodes(None, initial,
empty_tile_posi, costs, 0)

# Adding root to the list of live nodes

pq.push(root)

# Discovering a live node with min. costs,

# and adding its children to the list of live
# nodes and finally deleting it from
# the list.
while not pq.empty():

# Finding a live node with min. estimatsed

# costs and deleting it form the list of the
# live nodes
minimum = pq.pop()

# If the min. is ans node

if minimum.costs == 0:

# Printing the path from the root to

# destination;
printPath(minimum)
return

# Generating all feasible children

for i in range(n):
new_tile_posi = [
minimum.empty_tile_posi[0] + rows[i],
minimum.empty_tile_posi[1] + cols[i], ]

if isSafe(new_tile_posi[0], new_tile_posi[1]):

# Creating a child node

child = newNodes(minimum.mats,
minimum.empty_tile_posi,
new_tile_posi,
minimum.levels + 1,
minimum, final,)

# Adding the child to the list of live nodes

pq.push(child)

# Main Code

# Initial configuration
# Value 0 is taken here as an empty space
initial = [ [ 1, 2, 3 ],
[ 5, 6, 0 ],
[ 7, 8, 4 ] ]

# Final configuration that can be solved

# Value 0 is taken as an empty space
final = [ [ 1, 2, 3 ],
[ 5, 8, 6 ],
[ 0, 7, 4 ] ]

# Blank tile coordinates in the

# initial configuration
empty_tile_posi = [ 1, 2 ]

# Method call for solving the puzzle

solve(initial, empty_tile_posi, final)
OUTPUT:

123
560
784

123
506
784

123
586
704

123
586
074

Result:
Thus the program for implementing a basic search strategies for 8 puzzles was
implemented successfully.
Ex.No:1(b) Implementing a basic search strategy – 8 Queens
Date:

INPUT:
defis_safe(board, row, col, n):
# Check this row on left side
fori in range(col):
if board[row][i] == 1:
return False

# Check upper diagonal on left side

fori, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False

# Check lower diagonal on left side

fori, j in zip(range(row, n, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False

return True

defforward_checking(board, col, n):

if col >= n:
return True
for row in range(n):
ifis_safe(board, row, col, n):
board[row][col] = 1
ifforward_checking(board, col + 1, n):
return True
board[row][col] = 0 # Backtrack

return False

defprint_solution(board):
for row in board:
print(" ".join('Q' if x == 1 else '.' for x in row))

defeight_queens_forward_checking():
n=8
board = [[0] * n for _ in range(n)]
ifforward_checking(board, 0, n):
print_solution(board)
else:
print("No solution exists")

eight_queens_forward_checking()
OUTPUT:
Q.......
......Q.
....Q...
.......Q
.Q......
...Q....
.....Q..
..Q.....

RESULT:
Thus the Program for implementing of basic search strategies for 8 queens problem is
implemented successfully.
Ex. No:1(c) Implementation of basic search strategy –
Date: Cryptarithmetic

INPUT:
fromitertools import permutations

# Define the cryptarithmetic equation

defis_valid_solution(send, more, money):
return send + more == money

defsolve_cryptarithmetic():
# Letters in the problem
letters = 'SENDMOREMONEY'
unique_letters = set(letters)

# Check if the problem has unique letters

iflen(unique_letters) > 10:
print("Too many unique letters for a single digit assignment.")
return

# Create a list of all possible digits

digits = range(10)

# Iterate over all permutations of digits of length equal to the number of unique letters
for perm in permutations(digits, len(unique_letters)):
# Create a mapping of letters to digits
letter_to_digit = dict(zip(unique_letters, perm))

# Convert SEND, MORE, MONEY to actual numbers based on the mapping

send = int(''.join(str(letter_to_digit[c]) for c in 'SEND'))
more = int(''.join(str(letter_to_digit[c]) for c in 'MORE'))
money = int(''.join(str(letter_to_digit[c]) for c in 'MONEY'))

# Check if the current assignment satisfies the equation

ifis_valid_solution(send, more, money):
print(f"Solution found:")
print(f"SEND = {send}")
print(f"MORE = {more}")
print(f"MONEY = {money}")
return

print("No solution exists")

# Run the solver

solve_cryptarithmetic()

OUTPUT:
Solution found:
SEND = 6853
MORE = 728
MONEY = 7581

RESULT:
Thus the python program for implementing a basic strategies for crptarithmetic was
successfully implemented.
Ex.No;2(a) Implementation of A* Algorithm
Date:

INPUT:
importheapq

defastar(start, goal, graph, heuristic):

open_list = []
heapq.heappush(open_list, (0, start))
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic[start]}

whileopen_list:
current = heapq.heappop(open_list)[1]

if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1]

for neighbor, cost in graph[current]:

tentative_g_score = g_score[current] + cost
if neighbor not in g_score or tentative_g_score<g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + heuristic[neighbor]
heapq.heappush(open_list, (f_score[neighbor], neighbor))

return None

# Example usage:
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('D', 3), ('E', 5)],
'C': [('F', 2)],
'D': [('F', 1)],
'E': [('F', 2)],
'F': []
}

heuristic = {
'A': 7,
'B': 6,
'C': 2,
'D': 1,
'E': 3,
'F': 0
}

start = 'A'
goal = 'F'
path = astar(start, goal, graph, heuristic)
print("Path found:", path)

OUTPUT:
Path found: ['A', 'C', 'F']

RESULT:
Thus the python program for implementing a A* algorithm was successfully
implemented.
Ex. No.2(b) Implementation of memory bounded A* Algorithm
Date:

INPUT:

defida_star(grid, start, goal):

def search(path, g, bound):
current = path[-1]
f = g + heuristic(current, goal)
if f > bound:
return f
if current == goal:
return True
min_bound = float('inf')
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
neighbor = (current[0] + dx, current[1] + dy)
if 0 <= neighbor[0] <len(grid) and 0 <= neighbor[1] <len(grid[0]) and
grid[neighbor[0]][neighbor[1]] == 0:
if neighbor not in path:
path.append(neighbor)
t = search(path, g + 1, bound)
if t == True:
return True
if t <min_bound:
min_bound = t
path.pop()
returnmin_bound

bound = heuristic(start, goal)

path = [start]
while True:
t = search(path, 0, bound)
if t == True:
return path
if t == float('inf'):
return None
bound = t

# Example usage
grid = [[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]]

start = (0, 0)
goal = (4, 4)
path = ida_star(grid, start, goal)

print("Path:", path)

OUTPUT:

Path: [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]

RESULT:
Thus the python program for implementing memory bounded A* Algorithm was
Successfully implemented.
Ex.No:3 Implement Minimas algorithm for game playing
Date; (Alpha Beta Pruning)

INPUT:
# Python3 program to demonstrate
# working of Alpha-Beta Pruning

# Initial values of Alpha and Beta

MAX, MIN = 1000, -1000

# Returns optimal value for current player

#(Initially called for root and maximizer)
def minimax(depth, nodeIndex, maximizingPlayer,
values, alpha, beta):

# Terminating condition. i.e

# leaf node is reached
if depth == 3:
return values[nodeIndex]

ifmaximizingPlayer:

best = MIN

# Recur for left and right children

fori in range(0, 2):

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

False, values, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)

# Alpha Beta Pruning

if beta <= alpha:
break

return best

else:
best = MAX

# Recur for left and

# right children
fori in range(0, 2):

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

True, values, alpha, beta)
best = min(best, val)
beta = min(beta, best)

# Alpha Beta Pruning

if beta <= alpha:
break

return best

# Driver Code
if __name__ == "__main__":

values = [3, 5, 6, 9, 1, 2, 0, -1]

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

# This code is contributed by Rituraj Jain

OUTPUT:

The optimal value is : 5

RESULT:
Thus the python program for implement minimax algorithm for game pruning(Alpha
Beta Pruning) was successfully implemented.
Ex.No:4 Solve Constraint satisfaction problems
Date;
INPUT:

importnumpy as np

# Helper function to print the Sudoku grid

defprint_grid(grid):
for row in grid:
print(" ".join(str(num) if num != 0 else '.' for num in row))
print()

# Function to check if placing a number is valid

defis_valid(grid, row, col, num):
# Check if num is not in the current row and column
ifnum in grid[row]:
return False
ifnum in [grid[i][col] for i in range(9)]:
return False

# Check if num is not in the current 3x3 subgrid

start_row, start_col = 3 * (row // 3), 3 * (col // 3)
fori in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if grid[i][j] == num:
return False

return True

# Function to solve Sudoku using backtracking

defsolve_sudoku(grid):
empty = find_empty_location(grid)
if not empty:
return True # Puzzle solved

row, col = empty

fornum in range(1, 10):

ifis_valid(grid, row, col, num):
grid[row][col] = num
ifsolve_sudoku(grid):
return True
grid[row][col] = 0 # Undo the move
return False # Trigger backtracking

# Function to find an empty location in the grid

deffind_empty_location(grid):
fori in range(9):
for j in range(9):
if grid[i][j] == 0:
return (i, j)
return None

# Example Sudoku puzzle (0 represents empty cells)

sudoku_grid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]

print("Initial Sudoku Puzzle:")

print_grid(sudoku_grid)

ifsolve_sudoku(sudoku_grid):
print("Solved Sudoku Puzzle:")
print_grid(sudoku_grid)
else:
print("No solution exists")
OUTPUT:
Initial Sudoku Puzzle:
53..7....
6..195...
.98....6.
8...6...3
4 . . 8 .3 . . 1
7...2...6
.6....28.
...419..5
....8..79

Solved Sudoku Puzzle:

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

RESULT:
Thus the python program for solving constraint Satisfaction problems was
successfully implemented.
Ex.No: 5 Implementation propositional model checking Algorithms
Date:

INPUT:

# Define the grid

wumpus_world = [
["Safe", "Breeze", "Pit", "Breeze"],
["Stench", "Safe", "Breeze", "Safe"],
["Wumpus", "Gold", "Pit", "Breeze"],
["Stench", "Safe", "Breeze", "Pit"]
]

# Define the agent's initial position

agent_position = (0, 0)

# Function to check if a move is safe

defis_safe(position):
row, col = position
ifwumpus_world[row][col] in ["Pit", "Wumpus"]:
return False
return True

# Function to move the agent

defmove_agent(position, direction):
row, col = position
if direction == "up" and row > 0:
row -= 1
elif direction == "down" and row < 3:
row += 1
elif direction == "left" and col > 0:
col -= 1
elif direction == "right" and col < 3:
col += 1
return (row, col)

# Example moves
moves = ["right", "down", "down", "right"]
for move in moves:
new_position = move_agent(agent_position, move)
ifis_safe(new_position):
agent_position = new_position
print(f"Moved to {agent_position}, it's safe!")
else:
print(f"Move to {new_position} is not safe!")

# Output the final position

print(f"Agent's final position: {agent_position}")

OUTPUT:

Moved to (0, 1), it's safe!

Moved to (1, 1), it's safe!
Moved to (2, 1), it's safe!
Move to (2, 2) is not safe!
Agent's final position: (2, 1)

RESULT:
Thus the python program for implementing propositional model checking algorithms
was successfully implemented.
Ex. No:6 (a) Implementation of forward chaining
Date:

INPUT:

# Define the knowledge base

knowledge_base = {
"facts": {"A", "B"},
"rules": [
{"if": {"A", "B"}, "then": "C"},
{"if": {"C"}, "then": "D"},
]
}

# Function to apply forward chaining

defforward_chaining(kb):
inferred = set()
while True:
new_inferred = set()
for rule in kb["rules"]:
if rule["if"].issubset(kb["facts"]) and rule["then"] not in kb["facts"]:
new_inferred.add(rule["then"])
if not new_inferred:
break
kb["facts"].update(new_inferred)
inferred.update(new_inferred)
return inferred

# Apply forward chaining

inferred_facts = forward_chaining(knowledge_base)
print("Inferred Facts:", inferred_facts)

OUTPUT:
Inferred Facts: {'D', 'C'}

RESULT:
Thus the python program of implementing forward chaining was successfully
implemented.
Ex.No:6(b) Implementation of Backward chaining
Date:

INPUT:
classKnowledgeBase:
def __init__(self):
self.rules = []
self.facts = set()

defadd_rule(self, rule):
self.rules.append(rule)

defadd_fact(self, fact):
self.facts.add(fact)

defbackward_chain(self, goal):
if goal in self.facts:
return True
for rule in self.rules:
ifrule.conclusion == goal:
if all(self.backward_chain(cond) for cond in rule.conditions):
self.facts.add(goal)
return True
return False

class Rule:
def __init__(self, conditions, conclusion):
self.conditions = conditions
self.conclusion = conclusion

# Example usage
kb = KnowledgeBase()
kb.add_fact('A')
kb.add_rule(Rule(['A'], 'B'))
kb.add_rule(Rule(['B'], 'C'))

goal = 'C'
ifkb.backward_chain(goal):
print(f"{goal} is true")
else:
print(f"{goal} is not true")
OUTPUT:

C is true

RESULT:
Thus the python program of implementing backward chaining was successfully
implemented.
Ex.No:6(c) Implementation of Resolution strategies
Date:

INPUT:

def resolve(clause1, clause2):

resolvents = []
for literal in clause1:
if -literal in clause2:
new_clause = (clause1 - {literal}) | (clause2 - {-literal})
resolvents.append(new_clause)
returnresolvents

# Example usage
clause1 = {1, -2}
clause2 = {2, 3}
print(resolve(clause1, clause2))

OUTPUT:
[{1, 3}]

RESULT:
Thus the python program for implementing resolution strategies was successfully
implemented.
Ex. No:7 Build naïve Bayes models
Date:

INPUT:

importnumpy as np
import pandas as pd
fromsklearn.model_selection import train_test_split
fromsklearn.naive_bayes import GaussianNB
fromsklearn.metrics import accuracy_score
fromsklearn.datasets import load_iris

# Load dataset
data = load_iris()
X = data.data
y = data.target

# Split the dataset

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Train the Naive Bayes model

model = GaussianNB()
model.fit(X_train, y_train)

# Make predictions
y_pred = model.predict(X_test)

# Evaluate the model

accuracy = accuracy_score(y_test, y_pred)
print(f'Accuracy: {accuracy * 100:.2f}%')

OUTPUT:
Accuracy: 97.78%

RESULT:
Thus the python program to build naïve bayes models was successfully implemented.

Ex.No:8 Implement Bayesian Network and perform Inferences

Date:

INPUT:

importnumpy as np
importmatplotlib.pyplot as plt

# Generate some synthetic data

np.random.seed(42)
true_mu = 5
true_sigma = 2
data = np.random.normal(true_mu, true_sigma, size=100)

# Define the prior hyperparameters

prior_mu_mean = 0
prior_mu_precision = 1 # Variance = 1 / precision
prior_sigma_alpha = 2
prior_sigma_beta = 2 # Beta = alpha / beta

# Update the prior hyperparameters with the data

posterior_mu_precision = prior_mu_precision + len(data) / true_sigma**2
posterior_mu_mean = (prior_mu_precision * prior_mu_mean + np.sum(data)) /
posterior_mu_precision

posterior_sigma_alpha = prior_sigma_alpha + len(data) / 2

posterior_sigma_beta = prior_sigma_beta + np.sum((data - np.mean(data))**2) / 2

# Calculate the posterior parameters

posterior_mu = np.random.normal(posterior_mu_mean, 1 /
np.sqrt(posterior_mu_precision), size=10000)
posterior_sigma = np.random.gamma(posterior_sigma_alpha, 1 / posterior_sigma_beta,
size=10000)

# Plot the posterior distributions

plt.figure(figsize=(10, 4))
plt.subplot(1, 2, 1)
plt.hist(posterior_mu, bins=30, density=True, color='skyblue', edgecolor='black')
plt.title('Posterior distribution of $\mu$')
plt.xlabel('$\mu$')
plt.ylabel('Density')
plt.subplot(1, 2, 2)
plt.hist(posterior_sigma, bins=30, density=True, color='lightgreen', edgecolor='black')
plt.title('Posterior distribution of $\sigma$')
plt.xlabel('$\sigma$')
plt.ylabel('Density')

plt.tight_layout()
plt.show()

# Calculate summary statistics

mean_mu = np.mean(posterior_mu)
std_mu = np.std(posterior_mu)
print("Mean of mu:", mean_mu)
print("Standard deviation of mu:", std_mu)

mean_sigma = np.mean(posterior_sigma)
std_sigma = np.std(posterior_sigma)
print("Mean of sigma:", mean_sigma)
print("Standard deviation of sigma:", std_sigma)

OUTPUT:
RESULT:
Thus the python program for implementing Bayesian network and perform inferences
was successfully implemented.