AAI301 ARTIFICIAL INTELLIGENCE LAB MANUAL

YEAR/SEM: II/III REGULATION: 2024

1.a

Python program that implements the classic 8-puzzle (sliding puzzle) problem.
This version includes:

 A representation of the puzzle as a 3x3 grid

 A function to shuffle the puzzle
 A function to make a move (up, down, left, right)
 A simple command-line loop to play the puzzle

import random

class EightPuzzle:

def __init__(self):

self.goal_state = [[1, 2, 3],

[4, 5, 6],

[7, 8, 0]] # 0 represents the empty space

[Link] = [row[:] for row in self.goal_state]

[Link]()

def shuffle(self):

# Perform random moves to shuffle the puzzle

 moves = ['up', 'down', 'left', 'right']

for _ in range(100):

move = [Link](moves)

self.make_move(move)

def find_empty(self):

for i in range(3):

for j in range(3):

if [Link][i][j] == 0:

return i, j

def make_move(self, direction):

i, j = self.find_empty()

if direction == 'up' and i < 2:

[Link][i][j], [Link][i+1][j] = [Link][i+1][j], [Link][i][j]

elif direction == 'down' and i > 0:

[Link][i][j], [Link][i-1][j] = [Link][i-1][j], [Link][i][j]

elif direction == 'left' and j < 2:

[Link][i][j], [Link][i][j+1] = [Link][i][j+1], [Link][i][j]

elif direction == 'right' and j > 0:

[Link][i][j], [Link][i][j-1] = [Link][i][j-1], [Link][i][j]

else:

print("Invalid move!")

def is_solved(self):

return [Link] == self.goal_state

 def display(self):

for row in [Link]:

print(' '.join(str(n) if n != 0 else ' ' for n in row))

print()

def main():

puzzle = EightPuzzle()

print("Welcome to the 8-Puzzle Game!")

print("Goal state:")

for row in puzzle.goal_state:

print(row)

print("\nCurrent state:")

[Link]()

while not puzzle.is_solved():

move = input("Enter your move (up/down/left/right): ").lower()

puzzle.make_move(move)

[Link]()

if puzzle.is_solved():

print("Congratulations! You solved the puzzle.")

if __name__ == "__main__":

main()

1.b

8-Queens problem is a classic chess puzzle:

Place 8 queens on a chessboard so that no two queens attack each other.

Here’s a simple Python program that solves the 8-Queens problem using backtracking:
N=8

def print_solution(board):

for row in board:

line = ""

for col in row:

line += "Q " if col else ". "

print(line)

print("\n")

def is_safe(board, row, col):

# Check left side of the row

for i in range(col):

if board[row][i]:

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]:

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]:

return False
 return True

def solve_nq_util(board, col):

# If all queens are placed, print the solution

if col >= N:

print_solution(board)

return True

res = False

for i in range(N):

if is_safe(board, i, col):

board[i][col] = 1

res = solve_nq_util(board, col + 1) or res

board[i][col] = 0 # BACKTRACK

return res

def solve_nq():

board = [[0 for _ in range(N)] for _ in range(N)]

if not solve_nq_util(board, 0):

print("No solution exists.")

return False

return True
if __name__ == "__main__":

solve_nq()

1.c

cryptarithmetic puzzle solver in Python.

import itertools

def solve():

# Unique letters in the puzzle

letters = 'SENDMORY'

# Possible digits (0-9)

digits = range(10)

# The first letters of SEND, MORE, MONEY must not be zero

for perm in [Link](digits, len(letters)):

s, e, n, d, m, o, r, y = perm

if s == 0 or m == 0:

continue # SEND and MORE must not start with zero

send = s * 1000 + e * 100 + n * 10 + d

more = m * 1000 + o * 100 + r * 10 + e

money = m * 10000 + o * 1000 + n * 100 + e * 10 + y

if send + more == money:

print(f"SOLUTION FOUND:")
 print(f" {send} + {more} = {money}")

print(f"Mapping: S={s}, E={e}, N={n}, D={d}, M={m}, O={o}, R={r}, Y={y}")

return

print("No solution found.")

if __name__ == "__main__":

solve()

2.a

Python implementation of the A* search algorithm

from queue import PriorityQueue

class Graph:

def __init__(self):

[Link] = {}

self.h = {} # Heuristic values

def add_edge(self, from_node, to_node, cost):

if from_node in [Link]:

[Link][from_node].append((to_node, cost))

else:

[Link][from_node] = [(to_node, cost)]

def set_heuristic(self, node, h_value):

self.h[node] = h_value
def a_star_search(self, start, goal):

open_set = PriorityQueue()

open_set.put((0, start))

came_from = {}

g_score = {start: 0}

while not open_set.empty():

_, current = open_set.get()

if current == goal:

return self.reconstruct_path(came_from, current)

for neighbor, cost in [Link](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 = tentative_g_score + [Link](neighbor, float('inf'))

open_set.put((f_score, neighbor))

return None

def reconstruct_path(self, came_from, current):

path = [current]

while current in came_from:

current = came_from[current]

[Link](current)
 [Link]()

return path

def main():

graph = Graph()

# Example graph edges

graph.add_edge('A', 'B', 1)

graph.add_edge('A', 'C', 3)

graph.add_edge('B', 'D', 1)

graph.add_edge('C', 'D', 1)

graph.add_edge('B', 'E', 6)

graph.add_edge('D', 'E', 1)

# Example heuristic values (straight-line estimates)

graph.set_heuristic('A', 4)

graph.set_heuristic('B', 2)

graph.set_heuristic('C', 2)

graph.set_heuristic('D', 1)

graph.set_heuristic('E', 0) # Goal

start = 'A'

goal = 'E'

path = graph.a_star_search(start, goal)

if path:

print(f"Path from {start} to {goal}: {' -> '.join(path)}")

 else:

print("No path found.")

if __name__ == "__main__":

main()

2.b

Python implementation of memory bounded A* search algorithm

a Memory Bounded A* algorithm is an enhancement of standard A* to limit memory usage.

One classic version is Iterative Deepening A* (IDA*), which combines the space efficiency
of DFS with the heuristic of A*. Another is Simplified Memory-Bounded A* (SMA*).

👉 IDA* is simpler to implement and commonly used in puzzles like the 8-puzzle or
pathfinding.
👉 SMA* is more advanced, but the core idea is that when memory is full, you discard the
worst nodes.

import copy

goal_state = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 0] # 0 is the blank

MOVES = [(-1,0),(1,0),(0,-1),(0,1)] # Up, Down, Left, Right

def manhattan(state):

distance = 0

for i in range(3):

for j in range(3):
 val = state[i][j]

if val != 0:

goal_x = (val - 1) // 3

goal_y = (val - 1) % 3

distance += abs(i - goal_x) + abs(j - goal_y)

return distance

def find_blank(state):

for i in range(3):

for j in range(3):

if state[i][j] == 0:

return i, j

def neighbors(state):

x, y = find_blank(state)

results = []

for dx, dy in MOVES:

nx, ny = x + dx, y + dy

if 0 <= nx < 3 and 0 <= ny < 3:

new_state = [Link](state)

new_state[x][y], new_state[nx][ny] = new_state[nx][ny], new_state[x][y]

[Link](new_state)

return results

def ida_star(start):

threshold = manhattan(start)

path = [start]
 while True:

temp = search(path, 0, threshold)

if temp == True:

return path

if temp == float('inf'):

return None

threshold = temp

def search(path, g, threshold):

node = path[-1]

f = g + manhattan(node)

if f > threshold:

return f

if node == goal_state:

return True

minimum = float('inf')

for succ in neighbors(node):

if succ not in path: # avoid cycles

[Link](succ)

temp = search(path, g + 1, threshold)

if temp == True:

return True

if temp < minimum:

minimum = temp

[Link]()

return minimum
def print_state(state):

for row in state:

print(" ".join(str(val) if val != 0 else " " for val in row))

print()

def main():

# Example scrambled state (you can change this!)

start_state = [

[2, 8, 3],

[1, 6, 4],

[7, 0, 5]

print("Start state:")

print_state(start_state)

print("Solving with IDA*...")

solution = ida_star(start_state)

if solution:

print(f"Solution found in {len(solution) - 1} moves:")

for state in solution:

print_state(state)

else:

print("No solution found.")

if __name__ == "__main__":
 main()

3. Alpha – Beta pruning

Alpha-Beta Pruning is a classic improvement over the Minimax algorithm used in game tree
searches (e.g., for Tic-Tac-Toe, Chess, etc.).
It prunes branches that don’t need to be evaluated, saving time without affecting the result.

Here’s a simple Python program that implements Minimax with Alpha-Beta Pruning for a
simple game tree.
I’ll show it with a small example (like a hypothetical game tree), so you can understand the
core logic.

# Simple example of Minimax with Alpha-Beta Pruning

def minimax(depth, node_index, maximizing_player, values, alpha, beta):

# Base case: leaf node

if depth == 3:

return values[node_index]

if maximizing_player:

best = float('-inf')

# Left child

val = minimax(depth + 1, node_index * 2, False, values, alpha, beta)

best = max(best, val)

alpha = max(alpha, best)

# Right child

val = minimax(depth + 1, node_index * 2 + 1, False, values, alpha, beta)

best = max(best, val)

 alpha = max(alpha, best)

if beta <= alpha:

# Prune

return best

return best

else:

best = float('inf')

# Left child

val = minimax(depth + 1, node_index * 2, True, values, alpha, beta)

best = min(best, val)

beta = min(beta, best)

# Right child

val = minimax(depth + 1, node_index * 2 + 1, True, values, alpha, beta)

best = min(best, val)

beta = min(beta, best)

if beta <= alpha:

# Prune

return best

return best
def main():

# Example game tree: leaf nodes with static scores

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

print("Optimal value:", minimax(0, 0, True, values, float('-inf'), float('inf')))

if __name__ == "__main__":

main()

4. Constraint Satisfaction Problem

Constraint Satisfaction Problem (CSP) with Python.

CSPs are a core part of AI — classic examples include map coloring, Sudoku, N-Queens,
scheduling, etc.

Below is a simple Python CSP solver for the classic Map Coloring Problem:

 The goal: Color regions of a map so that no adjacent regions have the same color.

def is_consistent(assignment, var, value, constraints):

for neighbor in constraints[var]:

if neighbor in assignment and assignment[neighbor] == value:

return False

return True

def backtrack(assignment, variables, domains, constraints):

# If assignment is complete, return it

if len(assignment) == len(variables):

return assignment

# Select an unassigned variable

 unassigned = [v for v in variables if v not in assignment]

var = unassigned[0]

for value in domains[var]:

if is_consistent(assignment, var, value, constraints):

assignment[var] = value

result = backtrack(assignment, variables, domains, constraints)

if result is not None:

return result

del assignment[var] # Backtrack

return None # Failure

def main():

# Variables: Regions of Australia

variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']

# Domains: Possible colors

domains = {}

colors = ['Red', 'Green', 'Blue']

for var in variables:

domains[var] = colors

# Constraints: Adjacency

constraints = {

'WA': ['NT', 'SA'],

'NT': ['WA', 'SA', 'Q'],

 'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],

'Q': ['NT', 'SA', 'NSW'],

'NSW': ['Q', 'SA', 'V'],

'V': ['SA', 'NSW'],

'T': [] # Tasmania is isolated

solution = backtrack({}, variables, domains, constraints)

if solution:

print("Solution found:")

for region in variables:

print(f"{region}: {solution[region]}")

else:

print("No solution found.")

if __name__ == "__main__":

main()

5. Implement propositional checking algorithm

Let’s write a simple propositional logic satisfiability checker in Python.

This is basically a SAT solver — a classic propositional checking algorithm.

A minimal implementation of the DPLL algorithm (Davis–Putnam–Logemann–Loveland),

which is the foundation for many SAT solvers.

Python Program: Basic DPLL SAT Solver

This works for propositional formulas in CNF (Conjunctive Normal Form).

def dpll(clauses, assignment):

# If no clauses, it's satisfied

 if not clauses:

return assignment

# If any clause is empty, it's unsatisfiable

if [] in clauses:

return None

# Unit clause propagation

for clause in clauses:

if len(clause) == 1:

literal = clause[0]

return dpll(assign(clauses, literal), assignment + [literal])

# Pure literal elimination

literals = [literal for clause in clauses for literal in clause]

for literal in set(literals):

if -literal not in literals:

return dpll(assign(clauses, literal), assignment + [literal])

# Choose a literal (first from first clause)

literal = clauses[0][0]

result = dpll(assign(clauses, literal), assignment + [literal])

if result is not None:

return result

return dpll(assign(clauses, -literal), assignment + [-literal])

def assign(clauses, literal):

 new_clauses = []

for clause in clauses:

if literal in clause:

continue # Clause is satisfied

new_clause = [l for l in clause if l != -literal]

new_clauses.append(new_clause)

return new_clauses

def main():

# Example CNF: (A ∨ ¬B) ∧ (B ∨ C) ∧ (¬A ∨ ¬C)

# We'll represent literals as integers:

# A = 1, B = 2, C = 3

# Negative for negation: ¬A = -1

clauses = [

[1, -2], # A ∨ ¬B

[2, 3], # B ∨ C

[-1, -3] # ¬A ∨ ¬C

result = dpll(clauses, [])

if result is None:

print("Unsatisfiable")

else:

print("Satisfiable assignment found:")

for literal in result:

 var = abs(literal)

value = literal > 0

print(f"Variable {var} = {value}")

if __name__ == "__main__":

main()

6. a. Implement forward chaining

Python program for Forward Chaining, which is a simple reasoning algorithm used in propositional
logic and rule-based expert systems.

✅ What is Forward Chaining?

Forward Chaining:

 Starts with known facts

 Applies inference rules to derive new facts
 Continues until the goal is reached or no new facts can be inferred

🎯 Example Scenario

Let’s use a classic:

Rules:

1. If it is raining, the ground is wet.

2. If the sprinkler is on, the ground is wet.
3. If the ground is wet, the grass is slippery.

Facts:

 It is raining.
 The sprinkler is on.

Goal:

 Is the grass slippery?

def forward_chaining(facts, rules, goal):

 inferred = set(facts)

new_inferred = True

while new_inferred:

new_inferred = False

for rule in rules:

if rule['if'].issubset(inferred) and rule['then'] not in inferred:

[Link](rule['then'])

print(f"Inferred: {rule['then']}")

new_inferred = True

if rule['then'] == goal:

print(f"Goal '{goal}' reached!")

return True

print(f"Goal '{goal}' NOT reached.")

return False

def main():

# Initial facts

facts = {"raining", "sprinkler_on"}

# Rules: If 'if' conditions are true, then 'then' is inferred

rules = [

{"if": {"raining"}, "then": "ground_wet"},

{"if": {"sprinkler_on"}, "then": "ground_wet"},

{"if": {"ground_wet"}, "then": "grass_slippery"}

 ]

goal = "grass_slippery"

print(f"Initial facts: {facts}")

print(f"Trying to infer: {goal}")

forward_chaining(facts, rules, goal)

if __name__ == "__main__":

main()

6.b Implement backward chaining

Backward chaining is the reverse of forward chaining:

 You start with a goal,

 Try to prove it by finding rules that lead to it,
 Then recursively prove the conditions (premises) of those rules.

It’s commonly used in expert systems (e.g., MYCIN, Prolog).

def backward_chaining(goal, facts, rules, proved=None):

if proved is None:

proved = set()

if goal in facts:

print(f"Fact '{goal}' is known.")

return True

for rule in rules:

if rule['then'] == goal:
 print(f"Trying to prove '{goal}' using rule: IF {rule['if']} THEN {goal}")

all_premises_proved = True

for premise in rule['if']:

if premise not in proved:

if backward_chaining(premise, facts, rules, proved):

[Link](premise)

else:

all_premises_proved = False

break

if all_premises_proved:

print(f"Proved: '{goal}'")

return True

print(f"Cannot prove: '{goal}'")

return False

def main():

# Facts

facts = {"raining", "sprinkler_on"}

# Rules: premises -> conclusion

rules = [

{"if": {"raining"}, "then": "ground_wet"},

{"if": {"sprinkler_on"}, "then": "ground_wet"},

{"if": {"ground_wet"}, "then": "grass_slippery"}

 ]

goal = "grass_slippery"

print(f"Known facts: {facts}")

print(f"Trying to prove: {goal} using backward chaining...")

result = backward_chaining(goal, facts, rules)

if result:

print(f"\nConclusion: '{goal}' IS TRUE.")

else:

print(f"\nConclusion: '{goal}' cannot be proved with current facts and rules.")

if __name__ == "__main__":

main()

6.c Implement resolution strategies

Resolution — a fundamental inference rule for Propositional Logic (and first-order logic).

Resolution is the basis of SAT solvers, theorem provers, and automatic reasoning.
It shows that if you want to prove PPP, you add ¬P\neg P¬P to your knowledge base (KB)
and use resolution:

 If you derive a contradiction (empty clause), then PPP must be true (proof by
refutation).

✅ Python Program: Simple Resolution Refutation

Below is a clear Python program that:
  Uses propositional clauses in CNF.
 Uses binary resolution.
 Shows step-by-step derived clauses.
 Stops when the empty clause is derived (contradiction).

def pl_resolution(KB, alpha):

clauses = KB + [[-x for x in alpha]] # Add negation of alpha

new = set()

print("Initial clauses:")

for c in clauses:

print(c)

while True:

n = len(clauses)

pairs = [(clauses[i], clauses[j]) for i in range(n) for j in range(i + 1, n)]

for (ci, cj) in pairs:

resolvents = resolve(ci, cj)

if [] in resolvents:

print("\nDerived empty clause by resolving:")

print(f"{ci} and {cj}")

return True

[Link](tuple(sorted(r)) for r in resolvents)

new_clauses = [list(c) for c in new if list(c) not in clauses]

if not new_clauses:

return False

for c in new_clauses:

[Link](c)
 print(f"Derived new clause: {c}")

def resolve(ci, cj):

resolvents = []

for di in ci:

for dj in cj:

if di == -dj:

# Resolvent is (ci ∪ cj) without di and dj

new_clause = list(set(ci + cj))

new_clause.remove(di)

new_clause.remove(dj)

if not contains_complementary_literals(new_clause):

[Link](new_clause)

return resolvents

def contains_complementary_literals(clause):

return any(-l in clause for l in clause)

def main():

# Example KB:

# 1. A ∨ B -> [1, 2]

# 2. ¬A -> [-1]

# Goal: Prove B -> alpha = [2]

KB = [

[1, 2], # A ∨ B

[-1] # ¬A
 ]

alpha = [2] # B

result = pl_resolution(KB, alpha)

print("\nResult:")

if result:

print("Alpha is entailed by the KB. (Contradiction found)")

else:

print("Alpha is NOT entailed by the KB. (No contradiction)")

if __name__ == "__main__":

main()

7. Program for building naïve bayes models

Python program that demonstrates how to implement Naive Bayes Classification using the
scikit-learn library. I’ll also include a basic implementation from scratch if you want to see how
it works internally.

# Naive Bayes using scikit-learn

from [Link] import load_iris

from sklearn.model_selection import train_test_split

from sklearn.naive_bayes import GaussianNB

from [Link] import accuracy_score, classification_report

# Load example dataset

iris = load_iris()

X = [Link]
y = [Link]

# Split into train and test sets

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

# Create a Gaussian Naive Bayes classifier

gnb = GaussianNB()

# Train the model

[Link](X_train, y_train)

# Make predictions

y_pred = [Link](X_test)

# Evaluate the model

print("Accuracy:", accuracy_score(y_test, y_pred))

print("\nClassification Report:\n", classification_report(y_test, y_pred))

8. Implement Bayesian networks and perform inferences

Python program that shows how to implement a simple Bayesian Network and perform
inference on it.
We’ll use the pgmpy library — it’s a good library for probabilistic graphical models in
Python.

✅ Step 1: Install pgmpy

If you haven’t installed pgmpy, run this:

bash
CopyEdit
pip install pgmpy
✅ Step 2: Example Program — Bayesian Network &
Inference
Below is a complete example that builds a Bayesian Network for the classic Rain-
Sprinkler-Grass Wet problem.

Rain-Sprinkler-Grass Wet

 Nodes: Cloudy, Sprinkler, Rain, WetGrass

 Cloudy influences Sprinkler and Rain
 Sprinkler and Rain influence WetGrass

python
CopyEdit
from [Link] import BayesianNetwork
from [Link] import TabularCPD
from [Link] import VariableElimination

⃣ Define the structure

# 1️
model = BayesianNetwork([
('Cloudy', 'Sprinkler'),
('Cloudy', 'Rain'),
('Sprinkler', 'WetGrass'),
('Rain', 'WetGrass')
])

⃣ Define CPDs (Conditional Probability Distributions)

# 2️
cpd_cloudy = TabularCPD(variable='Cloudy', variable_card=2, values=[[0.5],
[0.5]])

cpd_sprinkler = TabularCPD(
variable='Sprinkler',
variable_card=2,
values=[[0.5, 0.9], [0.5, 0.1]],
evidence=['Cloudy'],
evidence_card=[2]
)

cpd_rain = TabularCPD(
variable='Rain',
variable_card=2,
values=[[0.8, 0.2], [0.2, 0.8]],
evidence=['Cloudy'],
evidence_card=[2]
)

cpd_wetgrass = TabularCPD(
variable='WetGrass',
variable_card=2,
values=[
[1.0, 0.1, 0.1, 0.01],
[0.0, 0.9, 0.9, 0.99]
],
 evidence=['Sprinkler', 'Rain'],
evidence_card=[2, 2]
)

⃣ Add CPDs to the model

# 3️
model.add_cpds(cpd_cloudy, cpd_sprinkler, cpd_rain, cpd_wetgrass)

⃣ Validate the model

# 4️
assert model.check_model()

⃣ Perform inference
# 5️
infer = VariableElimination(model)

# Example Query: What is P(Rain | WetGrass = True)

query = [Link](variables=['Rain'], evidence={'WetGrass': 1})
print(query)

# Another query: What is P(Sprinkler | WetGrass = True, Rain = False)

query2 = [Link](variables=['Sprinkler'], evidence={'WetGrass': 1,
'Rain': 0})
print(query2)

✅ What this does

1. Builds the network structure
2. Defines CPDs for each node
3. Checks model consistency
4. Runs inference using Variable Elimination

📌 Output
This will print:

 The probability distribution for Rain given WetGrass = True

 The probability distribution for Sprinkler given WetGrass = True and Rain =
False

⚡ Key points
 pgmpy is very flexible. You can also learn structure from data, estimate CPDs, do
MAP estimation, and more.
 For large networks, exact inference can be slow — then you can use approximate
methods like sampling.