Practical 1A & 1B: DFS & BFS

This single script runs both DFS and BFS on the same graph.

Python

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}

# 1A: Depth First Search (DFS)

print("DFS Output:")

visited_dfs = set()

def dfs(node):

if node not in visited_dfs:

print(node, end=' ')

visited_dfs.add(node)

for neighbour in graph[node]:

dfs(neighbour)

dfs('A')

# 1B: Breadth First Search (BFS)

print("\n\nBFS Output:")

from collections import deque

def bfs(start_node):

visited_bfs = {start_node}

queue = deque([start_node])

while queue:

vertex = queue.popleft()

print(vertex, end=' ')

for neighbour in graph[vertex]:

if neighbour not in visited_bfs:

visited_bfs.add(neighbour)

queue.append(neighbour)

bfs('A')

Expected Output:

DFS Output:

A B D C

BFS Output:

A B C D

Practical 2A: N-Queen Problem

This code is set up to find and print all solutions for the 4-Queen problem.

Python

N = 4

def print_solution(board):

for row in board:

print(" ".join(map(str, row)))

print()

def is_safe(board, row, col):

# Check row, upper-left diagonal, and lower-left diagonal

for i in range(col):

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

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

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

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

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

return True

def solve_n_queen(board, col):

if col >= N: # Base case: all queens placed

print_solution(board)

return True

res = False

for i in range(N): # Try placing a queen in each row of this column

if is_safe(board, i, col):

board[i][col] = 1

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

board[i][col] = 0 # BACKTRACK

return res

# --- Driver Code ---

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

print(f"Solutions for {N}-Queens:")

solve_n_queen(board, 0)

Practical 2B: Tower of Hanoi

This recursive solution prints every move required to solve the puzzle.

Python

def tower_of_hanoi(n, source, destination, aux):

if n == 1:

print(f"Move disk 1 from {source} to {destination}")

return

tower_of_hanoi(n-1, source, aux, destination)

print(f"Move disk {n} from {source} to {destination}")

tower_of_hanoi(n-1, aux, destination, source)

# --- Driver Code ---

num_disks = 3

print(f"Solving Tower of Hanoi for {num_disks} disks:")

tower_of_hanoi(num_disks, 'A', 'C', 'B')

Practical 4B: Water Jug Problem

This uses BFS to find the shortest sequence of moves.

Python

from collections import deque

def water_jug(cap1, cap2, target):

q = deque([((0, 0), [(0, 0)])]) # State: ((jug1, jug2), path_list)

visited = {(0, 0)}

while q:

(state, path) = q.popleft()

j1, j2 = state

if j1 == target or j2 == target: return path

# Generate all 6 possible next states

next_states = [

(cap1, j2), (j1, cap2), (0, j2), (j1, 0), # Fill/Empty

(j1 - min(j1, cap2-j2), j2 + min(j1, cap2-j2)), # Pour 1->2

(j1 + min(j2, cap1-j1), j2 - min(j2, cap1-j1)) # Pour 2->1

]

for ns in set(next_states): # Use set to avoid duplicate states

if ns not in visited:

visited.add(ns)

q.append((ns, path + [ns]))

return None

# --- Driver Code ---

path = water_jug(5, 3, 4)

if path:

print("Solution found!")

for i, state in enumerate(path):

print(f"Step {i}: Jug1={state[0]}, Jug2={state[1]}")

else:

print("No solution found.")

Practical 5B: Shuffle Deck of Cards

This is the simplest one. It just creates and shuffles a deck.

Python

import random

suits = ['Hearts', 'Diamonds', 'Clubs', 'Spades']

ranks = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'Jack', 'Queen', 'King', 'Ace']

deck = [f"{rank} of {suit}" for suit in suits for rank in ranks]

print("Original deck (first 5 cards):", deck[:5])

random.shuffle(deck)

print("Shuffled deck (first 5 cards):", deck[:5])

Practical 7A: Constraint Satisfaction Problem (Map Coloring)

This uses backtracking to find a valid coloring for a map of Australia.

Python

# --- Setup ---

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

domains = {var: ['red', 'green', 'blue'] for var in variables}

constraints = {

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

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

}

# --- Logic ---

def is_consistent(var, val, assignment):

for neighbor in constraints.get(var, []):

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

return False

return True

def solve_csp(assignment={}):

if len(assignment) == len(variables): return assignment # Solved

var = [v for v in variables if v not in assignment][0]

for value in domains[var]:

if is_consistent(var, value, assignment):

assignment[var] = value

result = solve_csp(assignment)

if result: return result

del assignment[var] # Backtrack

return None

# --- Driver Code ---

solution = solve_csp()

if solution:

print("Solution found:")

for region, color in sorted(solution.items()):

print(f"{region}: {color}")

else:

print("No solution found.")

Practicals 9 & 10: Logic in Prolog

Save this code as a .pl file (e.g., logic.pl) and load it into a Prolog interpreter.

Prolog

% --- Practical 9A: Simple Predicate ---

batsman(sachin).

cricketer(X) :- batsman(X).

% --- Practical 10A: Family Tree ---

% Facts

male(john). male(peter). male(bob). male(tom).

female(mary). female(susan). female(jane). female(lily). female(ann).

parent(john, peter). parent(mary, peter).

parent(john, jane). parent(mary, jane).

parent(peter, tom). parent(susan, tom).

parent(peter, lily). parent(susan, lily).

parent(bob, ann). parent(jane, ann).

% Rules

father(F, C) :- parent(F, C), male(F).

mother(M, C) :- parent(M, C), female(M).

grandfather(GF, GC) :- father(GF, P), parent(P, GC).

sibling(A, B) :- parent(P, A), parent(P, B), A \= B. % A and B are not the same person

brother(B, S) :- sibling(B, S), male(B).

cousin(A, B) :- parent(P1, A), parent(P2, B), sibling(P1, P2).

How to Run in Prolog:

1. 1. Load the file: consult('logic.pl').
   2. Ask queries:
   • ?- cricketer(sachin). (Expected: true.)
   • ?- father(peter, tom). (Expected: true.)
   • ?- grandfather(john, lily). (Expected: true.)
   • ?- brother(peter, X). (Expected: X = jane.)
   • ?- cousin(tom, ann). (Expected: true.)

Good luck with the exam!