Artificial Intelligence Laboratory Hub
Complete standalone source code, deep conceptual theory, step-by-step algorithms, dry runs, actual sample outputs, and oral viva questions for all 11 practicals.
Fast Track Exam Preparation
This hub contains fully tested, standalone Python implementations designed specifically for college practical examinations and viva voce.
Every practical runs using only the Python Standard Library without any pip install or third-party dependencies.
- Clone or download this repository.
- Open a terminal in the project folder.
- Run:
python pract1.py(orpython3 pract1.py/py pract1.py). - Replace
1with any experiment number (1 to 11). - Example inputs are clearly labelled inside
main()in each file for easy exam modifications.
Experiments Directory (1 to 11)
Master Syllabus & Algorithm Matrix
| # | File | Topic & Experiment Name | Domain Category | Core Algorithm |
|---|---|---|---|---|
| 1 | pract1.py |
Vacuum Cleaner (Reflex Agent) | Intelligent Agents | Simple Reflex Agent |
| 2 | pract2.py |
Grid Navigation (Model-Based Agent) | Intelligent Agents & Planning | Model-Based Agent |
| 3 | pract3.py |
8-Puzzle Solver (A* Heuristic) | Heuristic Search | Informed Search |
| 4 | pract4.py |
Game Tree (Minimax & Alpha-Beta) | Game Theory & Search | Adversarial Search |
| 5 | pract5.py |
Tower of Hanoi (BFS Search) | State-Space Search | State-Space Search |
| 6 | pract6.py |
Sudoku Solver (CSP & MRV) | Constraint Satisfaction Problems | CSP |
| 7 | pract7.py |
TSP (Local Beam Search) | Heuristic Optimization | Combinatorial Optimization |
| 8 | pract8.py |
8-Puzzle Planning (BFS) | AI Planning | Classical Planning |
| 9 | pract9.py |
Water Jug Problem (DFS) | State-Space Search | Uninformed Search |
| 10 | pract10.py |
8-Queens (Backtracking & FC) | Constraint Satisfaction Problems | CSP |
| 11 | pract11.py |
Rule-Based Chatbot (NLP Regex) | Natural Language Processing | NLP |
Practical Exam & Viva Strategy
Before typing code in front of the examiner, speak the 7-step formula in your own words:
- State the exact algorithm: Don't just say "I solved the puzzle"; say "I used A* search with Manhattan distance because it is admissible and finds an optimal path."
- Know the data structures: BFS uses a FIFO
deque; DFS uses a LIFOliststack; A* uses a min-heap priority queue viaheapq; Sudoku uses Sets for candidate constraints. - Be ready for edge cases: Teachers frequently ask "What if both rooms are clean initially?", "What if target water cannot be divided by GCD?", or "What if start and goal 8-puzzle have different inversion parities?".
Practical 1: Simple Reflex Agent - Vacuum Cleaner
Simple Reflex Agent • PEAS • Discrete Environment
Aim & Objective
To design and implement a Simple Reflex Agent for the two-room Vacuum Cleaner World that perceives room status and location, and executes rational cleaning and movement actions based on condition-action rules.
Theory & Core Concepts
| PEAS Element | System Description for Practical 1 |
|---|---|
| Performance Measure | Maximize clean rooms; minimize energy consumption and time spent moving. |
| Environment | Two interconnected rooms (A and B); each room status is either Clean or Dirty. |
| Actuators | Suction motor (Suck), movement motors (Left, Right). |
| Sensors | Dirt detection sensor (Clean/Dirty), Location sensor (Room A / Room B). |
- Agent Concept: An agent is anything that perceives its environment through sensors and acts upon it via actuators.
- Simple Reflex Architecture: Actions are chosen solely using the current percept (location, dirt status) and condition-action (IF-THEN) rules. The agent maintains zero history or memory of past states.
- Partial Observability: The agent only perceives the room it currently occupies, not both rooms simultaneously. The global world state is known only to the simulator.
- Rationality: In this setup, cleaning a dirty room is immediately rational. However, once both rooms are clean, a pure reflex agent with no memory or stopping check would oscillate back and forth indefinitely; the simulation provides the external termination condition.
Step-by-Step Algorithm & Dry Run
- Receive current percept
(location, status)from the environment. - Evaluate condition-action rules: If
status == 'Dirty', action is'Suck'. - If
status == 'Clean'andlocation == 'A', action is'Right'. - If
status == 'Clean'andlocation == 'B', action is'Left'. - Apply action to simulator: update room status or agent location.
- Record step in history and repeat until the simulator detects all rooms are Clean.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Step 0 | Start | Agent placed at Room A. Room A=Dirty, Room B=Dirty. |
| Step 1 | Percept: (A, Dirty) -> Action: Suck | Room A is cleaned. State: {'A': 'Clean', 'B': 'Dirty'}. |
| Step 2 | Percept: (A, Clean) -> Action: Right | Agent moves to Room B. State: {'A': 'Clean', 'B': 'Dirty'}. |
| Step 3 | Percept: (B, Dirty) -> Action: Suck | Room B is cleaned. State: {'A': 'Clean', 'B': 'Clean'}. |
| Stop | Condition Met | Both rooms are clean. Total actions executed = 3. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (23 lines)
# Practical 1: Vacuum Cleaner Agent (Simple Reflex Agent)
# Max 25 lines - Clean & Exam-Ready
rooms = {"A": "Dirty", "B": "Dirty"}
location = "A"
print(f"Initial State: {rooms}, Agent starts at: {location}")
step = 1
while "Dirty" in rooms.values():
status = rooms[location]
if status == "Dirty":
print(f"Step {step}: Room {location} is Dirty -> Action: SUCK")
rooms[location] = "Clean"
elif location == "A":
print(f"Step {step}: Room A is Clean -> Action: MOVE RIGHT")
location = "B"
else:
print(f"Step {step}: Room B is Clean -> Action: MOVE LEFT")
location = "A"
step += 1
print(f"Final State: {rooms} (All rooms clean in {step - 1} actions!)")
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 1: Simple Reflex Agent - Vacuum Cleaner World
# Decision function for the reflex agent based on current percept
def reflex_agent(location, status):
if status == "Dirty": # If the room is dirty
return "Suck" # Action: suck the dirt
elif location == "A": # If room A is already clean
return "Right" # Action: move to room B
else: # If room B is already clean
return "Left" # Action: move to room A
# Main simulation function
def main():
location = "A" # Start location of the vacuum agent
rooms = {} # Dictionary to store cleanliness status
rooms["A"] = "Dirty" # Initial status of room A
rooms["B"] = "Dirty" # Initial status of room B
print("Initial:", rooms, "Location:", location)
step = 1 # Step counter
# Run loop while either room A or room B is still dirty
while rooms["A"] == "Dirty" or rooms["B"] == "Dirty":
status = rooms[location] # Sense dirt in current room
action = reflex_agent(location, status) # Decide action based on reflex rules
print(str(step) + ". At " + location + ", status=" + status + ": " + action)
# Apply the action to update the environment
if action == "Suck":
rooms[location] = "Clean" # Room becomes clean
elif action == "Right":
location = "B" # Agent moves to room B
elif action == "Left":
location = "A" # Agent moves to room A
step = step + 1 # Increment step count
print("Final:", rooms)
print("Actions:", step - 1)
print("Simulation stopped: both rooms are clean.")
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
roomsis a dictionary:{"A": "Dirty", "B": "Dirty"}.locationis either"A"or"B".reflex_agent(location, status)is the decision-making part. Dirty meansSuck; clean A meansRight; clean B meansLeft.simulate()validates the input, copies the room dictionary, obtains an action and applies it to the environment.history.append(...)records the old percept and selected action for printing. This recording belongs to the simulator; the reflex function does not read history.- The
whileloop ends when the simulator finds no dirty room. Without a global stopping check or added memory, the simple reflex rules would keep moving between two clean rooms. main()sets the input and prints each action. ChangeLOCATIONandROOMSfor other cases.
Dry run: (A, Dirty) -> Suck -> (A, Clean) -> Right -> (B, Dirty) -> Suck. Both rooms are now clean; total 3 actions.
Actual Verified Sample Output
Exact terminal output produced by running python pract1.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
(A, Dirty).Practical Exam Variations & Edge Cases
- Start at B with only A dirty. Change
LOCATION="B"and room statuses. Expected actions: Left, Suck. - Both rooms are already clean. Expected zero actions; the simulation stops immediately.
- Add a score. Subtract movement/cleaning costs when each action occurs; add a reward for cleaning a dirty room. State your scoring rules before comparing agents.
- Extend to more rooms. Store the rooms in a list and define neighbour movement. Tracking all previously cleaned rooms changes the policy into a memory-based one.
Decision time and memory are O(1) for the fixed two-room world.
Practical 2: Model-Based Intelligent Agent - Grid Navigation
Model-Based Agent • Local Sensing • BFS Planning
Aim & Objective
To implement a Model-Based Intelligent Agent that navigates an initially unknown obstacle grid by sensing local surroundings, maintaining an internal world map, and planning paths using Breadth-First Search (BFS).
Theory & Core Concepts
| PEAS Element | System Description for Practical 2 |
|---|---|
| Performance Measure | Reach the target goal G with minimum path steps without colliding with obstacles. |
| Environment | 2D rectangular grid with Start (S), Goal (G), Free cells (.), and Obstacles (X). |
| Actuators | Orthogonal movement (Up, Down, Left, Right). |
| Sensors | Local sensor revealing current cell and its 4 direct neighbours. |
- Model-Based Architecture: To handle partial observability, the agent maintains an internal world model (
model) tracking discovered free cells, obstacles, and unexplored cells (?). - Unknown Cell Safety: Cells marked
?are never traversed by the planner until confirmed safe/free by local sensing. - Dual-Stage Planning: The agent first runs BFS on known free cells to plan to the Goal
G. If the goal is not yet reachable through known territory, it plans to the nearest reachable unvisited free cell to explore. - BFS Guarantee: On an unweighted grid, BFS finds the shortest route across known free cells to the selected sub-target.
Step-by-Step Algorithm & Dry Run
- Initialize internal model grid with
?(unseen) using simple nested loops. - Sense current cell and 4 adjacent orthogonal neighbours; record actual contents into internal model.
- Mark current position as visited.
- While
position != goal: - a. Run BFS planner targeting the Goal
Gusing only known free cells (.,S,G). - b. If route to goal exists, follow it.
- c. If no route to goal, identify all sensed, free, unvisited cells and BFS plan to the nearest one (exploration mode).
- d. If no exploration target is reachable, terminate with failure (unreachable goal).
- e. Traverse each step of the planned route, sense newly adjacent cells after each move, and replan.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Start | At (0, 0) | Model senses neighbours (0,1) and (1,0). Both are free. |
| Moves 1-9 | Exploration | Agent moves through column 0, hits obstacle at (4,0), moves right along row 3 and up column 2. |
| Moves 10-14 | Mapping | Senses upper and central obstacles; gradually uncovers passage towards column 4. |
| Moves 15-20 | Goal Path | Uncovers clear path down column 4 into (4,4) [Goal]. Goal reached in 20 moves. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (44 lines)
# Practical 2: Grid Navigation with Obstacles (BFS Search)
# Max 40 lines - Clean & Exam-Ready
from collections import deque
grid = [
["S", ".", ".", "X", "."],
[".", "X", ".", "X", "."],
[".", "X", ".", ".", "."],
[".", ".", ".", "X", "."],
["X", "X", ".", ".", "G"]
]
rows, cols = len(grid), len(grid[0])
for i in range(rows):
for j in range(cols):
if grid[i][j] == "S": start = (i, j)
if grid[i][j] == "G": goal = (i, j)
directions = [(0, 1, "Right"), (1, 0, "Down"), (0, -1, "Left"), (-1, 0, "Up")]
queue = deque([start])
visited = {start}
parent = {}
while queue:
curr = queue.popleft()
if curr == goal: break
r, c = curr
for dr, dc, move in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "X" and (nr, nc) not in visited:
visited.add((nr, nc))
parent[(nr, nc)] = (curr, move)
queue.append((nr, nc))
if goal not in visited:
print("No path found!")
else:
path, curr = [], goal
while curr != start:
curr, move = parent[curr]
path.append(move)
path.reverse()
print("Shortest Path:", " -> ".join(path))
print("Total Steps:", len(path))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 2: Model-Based Agent - Grid Navigation with Local Sensing & BFS
from collections import deque # Import deque for fast queue operations in BFS
# 4 Orthogonal Movement Directions: (row offset, column offset)
DIRECTIONS = [
(-1, 0), # Move UP
(1, 0), # Move DOWN
(0, -1), # Move LEFT
(0, 1) # Move RIGHT
]
# The actual real-world environment (obstacles 'X' are unknown to the agent at the start)
GRID = [
["S", ".", ".", "X", "."],
[".", "X", ".", "X", "."],
[".", "X", ".", ".", "."],
[".", ".", ".", "X", "."],
["X", "X", ".", ".", "G"]
]
ROWS = len(GRID) # Number of grid rows (5)
COLS = len(GRID[0]) # Number of grid columns (5)
# Find coordinates of Start (S) and Goal (G) using simple loops
start_pos = None # Will hold starting (row, col)
goal_pos = None # Will hold goal (row, col)
for r in range(ROWS):
for c in range(COLS):
if GRID[r][c] == "S":
start_pos = (r, c) # S is at (0, 0)
elif GRID[r][c] == "G":
goal_pos = (r, c) # G is at (4, 4)
# Create agent's internal memory map using plain loops (NO list comprehensions)
model = []
for r in range(ROWS):
row = []
for c in range(COLS):
row.append("?") # Fill with '?' meaning unseen/unknown cell
model.append(row)
visited = set() # Set to remember which cells the agent visited
path = [] # List to record the sequence of visited cells
# Function to find all valid adjacent neighbours within grid boundaries
def get_neighbours(r, c):
valid_neighbours = [] # List to store valid neighbour coordinates
for dr, dc in DIRECTIONS: # Loop through each of the 4 directions
nr = r + dr # Neighbour row
nc = c + dc # Neighbour column
if nr >= 0 and nr < ROWS and nc >= 0 and nc < COLS: # Check within boundaries
valid_neighbours.append((nr, nc)) # Valid coordinate inside grid
return valid_neighbours # Return list of coordinates
# Local sensing: read actual grid content of current cell and its 4 neighbours into model
def sense(r, c):
model[r][c] = GRID[r][c] # Reveal current cell
neighbour_cells = get_neighbours(r, c) # Get adjacent coordinates
for nr, nc in neighbour_cells:
model[nr][nc] = GRID[nr][nc] # Reveal neighbour cell
# BFS pathfinding using ONLY cells known to be safe in the agent's internal model
def bfs(start, targets):
queue = deque() # Create FIFO queue
queue.append(start) # Enqueue start position
parent = {} # Dictionary to store parent of each cell
parent[start] = None # Start cell has no predecessor
while len(queue) > 0: # While queue has positions to explore
curr = queue.popleft() # Pop oldest cell (FIFO)
if curr in targets: # Check if current cell is a target
route = [] # List to reconstruct the route
while curr is not None: # Trace backwards to start
route.append(curr)
curr = parent[curr] # Move to parent cell
route.reverse() # Reverse to get START -> TARGET order
return route # Return planned path
curr_r = curr[0] # Current row
curr_c = curr[1] # Current column
for nxt in get_neighbours(curr_r, curr_c): # Check all 4 neighbours
nr = nxt[0]
nc = nxt[1]
cell_val = model[nr][nc] # Sensed value in internal map
# Move only through cells known to be free ('.', 'S', or 'G')
if (cell_val == "." or cell_val == "S" or cell_val == "G") and nxt not in parent:
parent[nxt] = curr # Save predecessor link
queue.append(nxt) # Enqueue neighbour
return None # Return None if no path found
def main():
curr_pos = start_pos # Place agent at start position
path.append(curr_pos) # Record start in travel path
visited.add(curr_pos) # Mark start as visited
sense(curr_pos[0], curr_pos[1]) # Perform initial local sensing
# Loop until the agent reaches the goal
while curr_pos != goal_pos:
# Step 1: Try planning directly to the goal
goal_target_set = {goal_pos}
route = bfs(curr_pos, goal_target_set)
# Step 2: If goal not reachable yet, find nearest unvisited known free cell to explore
if route is None:
unexplored = [] # Collect known free cells not visited yet
for r in range(ROWS):
for c in range(COLS):
cell_val = model[r][c]
is_free = (cell_val == "." or cell_val == "S" or cell_val == "G")
if is_free and (r, c) not in visited:
unexplored.append((r, c)) # Candidate exploration cell
route = bfs(curr_pos, set(unexplored)) # Plan route to nearest exploration cell
# Step 3: If still no route, reachable area is exhausted
if route is None:
print("No route: reachable area exhausted.")
return
# Step 4: Follow the planned route step-by-step
for i in range(1, len(route)):
next_step = route[i] # Next step in path
curr_pos = next_step # Move agent
path.append(curr_pos) # Record step
visited.add(curr_pos) # Mark as visited
sense(curr_pos[0], curr_pos[1]) # Sense new surroundings after move
if curr_pos == goal_pos: # Stop walking if goal reached
break
print("Goal reached!")
print("Actual travel path:", path)
print("Moves:", len(path) - 1)
print("Remembered map (? = unseen):")
for row in model:
print(" ".join(row)) # Print final remembered grid
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
GRIDis a list of equal-length strings.Sis start,Gis goal,.is free andXis blocked.ModelBasedAgent.__init__()creates the position, known goal coordinates,visitedset, actual travelpathand a model initially filled with?.neighbours()generates only in-bounds up/down/left/right coordinates. It does not read hidden grid contents.sense()is the only method that reads actual cell contents. It copies the current cell and its immediate neighbours into the model.plan(targets)runs BFS over known free cells. Its parent dictionary both records visited search states and reconstructs a route.run()first tries planning to the goal. If that fails, it plans to the nearest reachable known-free cell that the agent has not visited.- It follows the route, senses during movement and then replans. If no reachable exploration target remains, it reports failure.
- The actual grid is stored for simulation, but the planner uses
self.model, not the full environment.
The default example reaches the goal in 20 actual moves. This includes exploration; it is not a claim that the globally shortest route has 20 moves.
Actual Verified Sample Output
Exact terminal output produced by running python pract2.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Change the start, goal or obstacles. Edit
GRID, keeping exactly one S and G. - Add diagonal movement. Add direction offsets, define diagonal cost and whether cutting across blocked corners is allowed. Ordinary BFS is appropriate only if every allowed move has equal cost.
- Handle obstacles that change while moving. Sense and validate the next step immediately before moving, update the model and replan if necessary. The supplied implementation assumes a static grid.
- Show the global shortest path for a known map. Reveal the map first and use BFS once. Explain that this changes the information available to the agent.
One BFS call on an R by C grid uses O(RC) time and space. The whole exploring agent runs multiple BFS calls, so its total work is larger.
Practical 3: Informed Search - A* for 8-Puzzle
Informed Search • Manhattan Distance • Admissible Heuristic
Aim & Objective
To implement the A* heuristic search algorithm to solve the 8-puzzle problem using Manhattan distance as an admissible and consistent heuristic.
Theory & Core Concepts
- A* Evaluation Function:
f(n) = g(n) + h(n), whereg(n)is the exact cost from start to noden, andh(n)is the estimated remaining cost to the goal. - Manhattan Distance: Sum of horizontal and vertical distances of each numbered tile from its goal position:
h(n) = Σ (|r_i - r_goal| + |c_i - c_goal|)for tiles 1..8. The blank tile 0 is excluded so moves are not double counted. - Admissibility & Consistency: Manhattan distance is admissible (never overestimates) because each sliding move can only reduce the distance of one tile by 1 grid step. It is also consistent (monotonic), guaranteeing an optimal shortest path.
- Inversion Parity Solvability: An inversion occurs when a tile with a larger number precedes a tile with a smaller number in row-major order (ignoring 0). In a 3x3 puzzle, blank moves preserve inversion parity. Start and Goal must have the same parity (both even or both odd); otherwise the puzzle is mathematically unsolvable.
Step-by-Step Algorithm & Dry Run
- Validate state (all digits 0..8 present) and verify parity(start) == parity(goal).
- Initialize priority queue (min-heap) with
(f=h(start), g=0, start). - Initialize
best_g = {start: 0}andparent = {start: (None, 'START')}. - While frontier is not empty:
- a. Pop state with lowest
f. Ifg > best_g[current], discard stale entry. - b. If
current == goal, reconstruct solution path and return. - c. Increment expanded node counter.
- d. Generate legal blank swaps (UP, DOWN, LEFT, RIGHT).
- e. For each neighbour, compute
new_g = g + 1. Ifnew_g < best_g[nxt], recordbest_g, parent, calculatef = new_g + h(nxt), and push to min-heap.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Initial | f = 0 + 6 = 6 | Board has tiles 5, 6, 4 misplaced. |
| Step 1-6 | Blank Navigation | Blank slides LEFT, LEFT, DOWN, RIGHT, RIGHT, UP around tiles. |
| Step 7-12 | Tile Alignment | Tiles 5 and 6 placed into top rows; tiles 7 and 8 aligned. |
| Step 13 | DOWN -> Goal reached! | Final tile 4 placed into row 1. Solved in 13 moves; 91 nodes expanded. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (37 lines)
# Practical 3: 8-Puzzle Problem using A* (Manhattan Heuristic)
# Max 35 lines - Clean & Exam-Ready
import heapq
start = (1, 2, 3, 5, 6, 0, 7, 8, 4)
goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
goal_pos = {t: (i // 3, i % 3) for i, t in enumerate(goal)}
def manhattan(s):
return sum(abs(i // 3 - goal_pos[t][0]) + abs(i % 3 - goal_pos[t][1])
for i, t in enumerate(s) if t != 0)
# Priority queue stores: (f, g, state, path)
pq = [(manhattan(start), 0, start, [])]
visited = {start: 0}
while pq:
f, g, s, path = heapq.heappop(pq)
if s == goal:
print(f"Goal reached in {g} moves!")
print("Move sequence:", " -> ".join(path))
break
b = s.index(0)
r, c = b // 3, b % 3
moves = [(-1, 0, "UP"), (1, 0, "DOWN"), (0, -1, "LEFT"), (0, 1, "RIGHT")]
for dr, dc, act in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3:
nb = nr * 3 + nc
nxt = list(s)
nxt[b], nxt[nb] = nxt[nb], nxt[b]
nxt = tuple(nxt)
if nxt not in visited or g + 1 < visited[nxt]:
visited[nxt] = g + 1
heapq.heappush(pq, (g + 1 + manhattan(nxt), g + 1, nxt, path + [act]))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 3: Informed Search - A* Algorithm for 8-Puzzle Problem
import heapq # Import heapq for priority queue (min-heap)
# Check if puzzle state is solvable using inversion count
def is_solvable(state):
tiles = [] # List to store tiles excluding blank
for x in state:
if x != 0: # Ignore blank tile (0)
tiles.append(x)
inversions = 0 # Count of pairs in reverse order
for i in range(len(tiles)):
for j in range(i + 1, len(tiles)):
if tiles[i] > tiles[j]: # If a larger number appears before smaller
inversions = inversions + 1 # Count as an inversion
return inversions % 2 == 0 # Solvable if count of inversions is even
# Calculate Manhattan distance heuristic: sum of distances of tiles to goal positions
def manhattan_distance(state, goal_pos):
distance = 0 # Initialize total distance
for i in range(len(state)):
tile = state[i]
if tile != 0: # Do not count the blank tile (0)
curr_r = i // 3 # Row index in 3x3 grid (0, 1, or 2)
curr_c = i % 3 # Column index in 3x3 grid (0, 1, or 2)
target_r = goal_pos[tile][0] # Goal row for this tile
target_c = goal_pos[tile][1] # Goal column for this tile
distance = distance + abs(curr_r - target_r) + abs(curr_c - target_c)
return distance # Return total heuristic value h(n)
# Generate valid next states by moving the blank tile (0)
def get_neighbours(state):
neighbours = [] # List to store (new_state, move_name)
blank = state.index(0) # Find index position of blank tile (0)
r = blank // 3 # Blank row (0, 1, or 2)
c = blank % 3 # Blank column (0, 1, or 2)
# 4 possible directions to slide the blank: (name, dr, dc)
moves = [
("UP", -1, 0),
("DOWN", 1, 0),
("LEFT", 0, -1),
("RIGHT", 0, 1)
]
for move_name, dr, dc in moves: # Check each direction
nr = r + dr # New blank row
nc = c + dc # New blank column
if nr >= 0 and nr < 3 and nc >= 0 and nc < 3: # Check within 3x3 boundaries
new_blank = nr * 3 + nc # Convert row, col back to 1D index
board = list(state) # Convert tuple to mutable list
temp = board[blank] # Standard swap using temp variable
board[blank] = board[new_blank]
board[new_blank] = temp
neighbours.append((tuple(board), move_name)) # Save new board tuple and move
return neighbours # Return list of reachable neighbours
# A* Search algorithm implementation
def astar(start, goal):
if not is_solvable(start): # Check solvability before searching
print("No solution: initial and goal inversion parities differ.")
return None, 0
# Precompute goal coordinates (r, c) for each tile using a plain loop
goal_pos = {}
for i in range(len(goal)):
tile = goal[i]
goal_pos[tile] = (i // 3, i % 3)
# Priority queue (min-heap) stores entries: (f_score, g_cost, state)
frontier = []
initial_h = manhattan_distance(start, goal_pos) # Heuristic estimate for start
heapq.heappush(frontier, (initial_h, 0, start)) # Push start state with f = 0 + h
best_g = {} # Stores lowest g-cost found for each state
best_g[start] = 0
parent = {} # Stores parent state and action taken
parent[start] = (None, "START")
expanded_nodes = 0 # Count of expanded nodes
while len(frontier) > 0: # Loop until priority queue is empty
f, g, current = heapq.heappop(frontier) # Pop state with lowest f = g + h
if g > best_g.get(current, float("inf")): # Skip if a cheaper route was already processed
continue
if current == goal: # Check if goal board is reached
path = [] # List to reconstruct solution path
while current is not None: # Follow parent pointers back to start
prev_state, action = parent[current]
path.append((current, action)) # Add to path
current = prev_state # Step backward
path.reverse() # Reverse path to get START -> GOAL order
return path, expanded_nodes
expanded_nodes = expanded_nodes + 1 # Increment expanded nodes count
for next_state, action in get_neighbours(current): # Explore legal moves
new_g = g + 1 # Each sliding move has a step cost of 1
if new_g < best_g.get(next_state, float("inf")): # If a shorter route is found
best_g[next_state] = new_g # Record the new cheapest g-cost
parent[next_state] = (current, action) # Record parent and action
h = manhattan_distance(next_state, goal_pos) # Compute heuristic h
new_f = new_g + h # Compute total evaluation f = g + h
heapq.heappush(frontier, (new_f, new_g, next_state)) # Push to priority queue
return None, expanded_nodes # Return None if no solution found
def main():
START = (1, 2, 3, 5, 6, 0, 7, 8, 4) # Initial board configuration (0 is blank)
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0) # Target goal board configuration
path, expanded = astar(START, GOAL) # Execute A* Search
if path:
for step in range(len(path)): # Print each step in the solution
board = path[step][0]
action = path[step][1]
print("Step " + str(step) + ": " + action)
for i in range(0, 9, 3): # Print board as a 3x3 grid
print(board[i], board[i+1], board[i+2])
print("Moves:", len(path) - 1) # Print total steps taken
print("Nodes expanded (excluding goal):", expanded)
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
- A state is a tuple of nine integers;
0means blank. Tuple states can be dictionary keys. validate()checks that every value from 0 through 8 occurs exactly once.parity()counts inversions ignoring 0. A 3-by-3 start can reach a goal only if their inversion parities match.neighbours()locates the blank usingindex(0), converts its index to row and column usingdivmod, and generates legal swaps.manhattan()adds each numbered tile's horizontal and vertical distance from its goal location. It excludes the blank.frontieris a min-heap storing(f, g, state).heapq.heappop()removes the entry with the smallest priority.best_g[state]remembers the cheapest known path to that state. A newly cheaper route updates it and the parent.- If a heap entry's g no longer equals
best_g, it is stale and skipped. Improved states can be reinserted; there is no permanent closed-set prohibition. parent[state]=(previous_state, action)lets the code reconstruct the solution backward and reverse it.- Stop when the goal is removed from the heap, rather than immediately when first generated.
Formula: f(n)=g(n)+h(n). Example: if g=4 and h=6, f=10. In the near-goal board (1,2,3,4,0,6,7,5,8), h=2 because tiles 5 and 8 are one move away each.
The supplied default is the manual's scrambled board. It takes 13 moves. A simpler two-move board is provided above for tracing.
Actual Verified Sample Output
Exact terminal output produced by running python pract3.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Use misplaced tiles instead. Return the number of nonzero tiles not in their goal positions. It is admissible, but generally less informative than Manhattan distance.
- Start already equals the goal. Return a one-state path and 0 moves.
- Swap tiles 7 and 8 in the goal. The inversion test should reject it without a full search.
- Print g, h and f. Store or calculate those values while removing entries from the heap. Do not confuse the number of expanded nodes with the solution length.
Practical 4: Adversarial Search - Minimax & Alpha-Beta Pruning
Adversarial Search • Game Trees • Alpha-Beta Pruning
Aim & Objective
To implement and compare the Minimax algorithm and Alpha-Beta pruning on a two-player zero-sum binary game tree and evaluate the reduction in visited nodes.
Theory & Core Concepts
- Adversarial Search: Search in competitive environments where two opposing agents alternate moves. MAX aims to maximize the terminal utility, while MIN aims to minimize it.
- Minimax Principle: Recursively computes the value of each node: MAX nodes take
max(left, right), MIN nodes takemin(left, right). - Alpha-Beta Bounds: Maintains two cutoff thresholds:
• α (Alpha): The best (highest) score MAX can guarantee along the search path.
• β (Beta): The best (lowest) score MIN can enforce along the search path. - Pruning Condition: Whenever
α ≥ β, the current branch cannot affect the root decision; the search terminates immediately at that node. - Optimality Invariance: Alpha-Beta pruning returns the exact same root game value as full Minimax, but reduces time complexity from O(b^d) to as low as O(b^(d/2)) with optimal move ordering.
Step-by-Step Algorithm & Dry Run
- Define terminal leaf scores in power-of-2 array, and calculate tree depth.
- Minimax(leaves, depth, index, is_maximizing):
If depth is 0, returnleaves[index]. Recurse on left child2*indexand right child2*index+1. Returnmax()if maximizing elsemin(). - AlphaBeta(leaves, depth, index, is_maximizing, α, β):
If depth is 0, returnleaves[index].
For each child in (2*index, 2*index+1):
Recurse and obtain child score.
If maximizing: update value = max(value, score), α = max(α, value).
If minimizing: update value = min(value, score), β = min(β, value).
Ifα ≥ β: break (prune remaining siblings).
Return value.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Leaf Array | 16 leaves | [6, 8, 0, 5, 8, 9, 1, 1, 3, 5, 2, 9, 0, 9, 6, 5] |
| Minimax | Exhaustive | Visits all 31 nodes in the binary game tree. Returns root score = 6. |
| Alpha-Beta | With Pruning | Visits only 18 nodes. Skips 13 nodes (41.9% reduction). Returns root score = 6. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (36 lines)
# Practical 4: Game Tree - Minimax vs. Alpha-Beta Pruning
# Max 35 lines - Clean & Exam-Ready
leaves = [6, 8, 0, 5, 8, 9, 1, 1, 3, 5, 2, 9, 0, 9, 6, 5]
mm_nodes = [0]
ab_nodes = [0]
def minimax(depth, idx, is_max):
mm_nodes[0] += 1
if depth == 0: return leaves[idx]
left = minimax(depth - 1, idx * 2, not is_max)
right = minimax(depth - 1, idx * 2 + 1, not is_max)
return max(left, right) if is_max else min(left, right)
def alphabeta(depth, idx, is_max, alpha, beta):
ab_nodes[0] += 1
if depth == 0: return leaves[idx]
val = float("-inf") if is_max else float("inf")
for child in [idx * 2, idx * 2 + 1]:
res = alphabeta(depth - 1, child, not is_max, alpha, beta)
if is_max:
val = max(val, res)
alpha = max(alpha, val)
else:
val = min(val, res)
beta = min(beta, val)
if alpha >= beta: break
return val
mm_val = minimax(4, 0, True)
ab_val = alphabeta(4, 0, True, float("-inf"), float("inf"))
print("Leaves:", leaves)
print(f"Minimax optimal score: {mm_val} (Nodes visited: {mm_nodes[0]})")
print(f"Alpha-Beta optimal score: {ab_val} (Nodes visited: {ab_nodes[0]})")
print(f"Pruned nodes saved: {mm_nodes[0] - ab_nodes[0]}")
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 4: Adversarial Search - Minimax vs. Alpha-Beta Pruning on a Game Tree
# Global node counters to measure search effort
minimax_nodes = 0 # Tracks total nodes visited by Minimax
alphabeta_nodes = 0 # Tracks total nodes visited by Alpha-Beta
# Standard Minimax algorithm without pruning
def minimax(leaves, depth, index, is_maximizing):
global minimax_nodes # Access global counter
minimax_nodes = minimax_nodes + 1 # Count current node visit
if depth == 0: # Base case: reached a leaf node
return leaves[index] # Return the leaf utility score
left_child = 2 * index # Left child index in binary tree
right_child = 2 * index + 1 # Right child index in binary tree
if is_maximizing: # MAX's turn: maximize the score
left_val = minimax(leaves, depth - 1, left_child, False) # Recurse on left child
right_val = minimax(leaves, depth - 1, right_child, False) # Recurse on right child
if left_val > right_val:
return left_val # Choose larger value
else:
return right_val
else: # MIN's turn: minimize the score
left_val = minimax(leaves, depth - 1, left_child, True) # Recurse on left child
right_val = minimax(leaves, depth - 1, right_child, True) # Recurse on right child
if left_val < right_val:
return left_val # Choose smaller value
else:
return right_val
# Alpha-Beta Pruning algorithm
def alphabeta(leaves, depth, index, is_maximizing, alpha, beta):
global alphabeta_nodes # Access global counter
alphabeta_nodes = alphabeta_nodes + 1 # Count current node visit
if depth == 0: # Base case: reached a leaf node
return leaves[index] # Return the leaf utility score
left_child = 2 * index # Left child index
right_child = 2 * index + 1 # Right child index
children = [left_child, right_child] # List of children to evaluate
if is_maximizing: # MAX's turn: maximize the score
best_val = float("-inf") # Start with lowest possible score
for child in children:
val = alphabeta(leaves, depth - 1, child, False, alpha, beta) # Recurse
if val > best_val:
best_val = val # Update best value
if best_val > alpha:
alpha = best_val # Update alpha threshold
if alpha >= beta: # Pruning condition: beta cutoff!
break # Skip remaining child
return best_val # Return MAX's optimal score
else: # MIN's turn: minimize the score
best_val = float("inf") # Start with highest possible score
for child in children:
val = alphabeta(leaves, depth - 1, child, True, alpha, beta) # Recurse
if val < best_val:
best_val = val # Update best value
if best_val < beta:
beta = best_val # Update beta threshold
if alpha >= beta: # Pruning condition: alpha cutoff!
break # Skip remaining child
return best_val # Return MIN's optimal score
def main():
# 16 terminal leaf scores in left-to-right order
LEAVES = [6, 8, 0, 5, 8, 9, 1, 1, 3, 5, 2, 9, 0, 9, 6, 5]
depth = 4 # Tree depth (2^4 = 16 leaves)
# Run Minimax starting from root (index 0, maximizing=True)
mm_score = minimax(LEAVES, depth, 0, True)
# Run Alpha-Beta starting from root with alpha=-inf, beta=+inf
ab_score = alphabeta(LEAVES, depth, 0, True, float("-inf"), float("inf"))
saved_nodes = minimax_nodes - alphabeta_nodes # Calculate pruned nodes
savings_pct = (saved_nodes / minimax_nodes) * 100 # Calculate percentage savings
print("Leaves:", LEAVES)
print("Minimax: value=" + str(mm_score) + ", nodes visited=" + str(minimax_nodes))
print("Alpha-Beta: value=" + str(ab_score) + ", nodes visited=" + str(alphabeta_nodes))
print("Nodes avoided: " + str(saved_nodes) + " (" + f"{savings_pct:.1f}" + "%)")
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
LEAVESholds utility values in left-to-right order for a full binary tree. Its length must be a power of two.compare()checks the count and computes depth usingbit_length()-1.- In
minimax(), depth zero returns the leaf value. Otherwise recurse on child indices2*indexand2*index+1at the next level. not maximizingalternates players. A MAX node returns the larger child value; a MIN node returns the smaller.alphabeta()starts a MAX node's local value at negative infinity and a MIN node's value at positive infinity.- MAX updates alpha using
max; MIN updates beta usingmin. if alpha >= beta: breakskips remaining children at the current node.- A dictionary counter counts all entered nodes, including root and leaves, in both methods.
Default output: root value 6 for both methods. Minimax visits 31 nodes; Alpha-Beta visits 18. Avoided: 13 nodes, or 41.9%.
Small pruning trace: root MAX has already secured 5, so alpha=5. In another MIN branch, the first examined child gives 3. That MIN branch can return at most 3, so MAX will not prefer it over 5; remaining children can be skipped.
Actual Verified Sample Output
Exact terminal output produced by running python pract4.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Change the leaf values. Keep the count a power of two and compare both returned values.
- Use negative leaf scores. Infinity initialisation ensures negative values work correctly.
- Find the selected move, not only its score. Save the child index whenever a node improves its best value; report the root's saved child. Tied moves can both be optimal.
- All leaves have the same value. Check the actual output: equality can still trigger
alpha >= beta, so pruning may occur.
Auxiliary recursion space is O(d) in this binary-tree implementation, excluding the supplied leaves.
Practical 5: State-Space Search - Tower of Hanoi using BFS
State-Space Search • Breadth-First Search • Shortest Path
Aim & Objective
To solve the classical Tower of Hanoi puzzle using Breadth-First Search (BFS) state-space exploration and verify the theoretical minimum move count 2^N - 1.
Theory & Core Concepts
- Search vs Hardcoded Recursion: Classical Hanoi recursion follows a known divide-and-conquer strategy without state search. This practical explicitly implements state-space search using BFS to explore configurations.
- State Representation: A 3-tuple of tuples
(pegA, pegB, pegC). For N=3, start is((3,2,1), (), ())and goal is((), (), (3,2,1)). Last element in each tuple represents the topmost disk. - Move Constraints: Only the top disk of a peg can move; a larger disk cannot be placed on top of a smaller disk.
- BFS Guarantee: Because each move has equal cost 1, BFS explores all 1-move states, then all 2-move states, guaranteed to find the minimum move sequence (2^N - 1).
Step-by-Step Algorithm & Dry Run
- Define start state
(tuple(N..1), (), ())and goal state((), (), tuple(N..1)). - Initialize FIFO queue with
startand parent dictionary{start: (None, 'START')}. - While queue is not empty:
- a. Pop
currentstate from the front of the queue. - b. If
current == goal, trace back parent pointers and return the move sequence. - c. Increment expanded nodes counter.
- d. For each source peg (0..2) and target peg (0..2):
If legal move: construct next state.
If next state not inparent: record parent and append to queue.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Step 0 | START | A: [3, 2, 1], B: [], C: [] |
| Step 1 | Disk 1: A -> C | A: [3, 2], B: [], C: [1] |
| Step 2 | Disk 2: A -> B | A: [3], B: [2], C: [1] |
| Step 3 | Disk 1: C -> B | A: [3], B: [2, 1], C: [] |
| Step 4 | Disk 3: A -> C | A: [], B: [2, 1], C: [3] |
| Step 5 | Disk 1: B -> A | A: [1], B: [2], C: [3] |
| Step 6 | Disk 2: B -> C | A: [1], B: [], C: [3, 2] |
| Step 7 | Disk 1: A -> C | A: [], B: [], C: [3, 2, 1] [Goal reached in exactly 7 moves] |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (29 lines)
# Practical 5: Tower of Hanoi using BFS State-Space Search
# Max 30 lines - Clean & Exam-Ready
from collections import deque
start = ((3, 2, 1), (), ())
goal = ((), (), (3, 2, 1))
queue = deque([(start, [])])
visited = {start}
while queue:
state, path = queue.popleft()
if state == goal:
print(f"Hanoi solved in {len(path)} moves (BFS):")
for step, (disk, src, dst) in enumerate(path, 1):
print(f"Step {step}: Move Disk {disk} from Peg {src} -> Peg {dst}")
break
for i in range(3):
if not state[i]: continue
disk = state[i][-1]
for j in range(3):
if i != j and (not state[j] or state[j][-1] > disk):
pegs = [list(p) for p in state]
pegs[j].append(pegs[i].pop())
nxt = tuple(tuple(p) for p in pegs)
if nxt not in visited:
visited.add(nxt)
queue.append((nxt, path + [(disk, chr(65 + i), chr(65 + j))]))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 5: Tower of Hanoi Problem - BFS State-Space Search
from collections import deque # Import deque for FIFO queue operations
# Generate all legal moves from the current state
def get_successors(state):
successors = [] # List to store (next_state, action_description)
names = ("A", "B", "C") # Peg labels
for src in range(3): # Try each peg as source
if len(state[src]) == 0: # If source peg is empty, no disk to move
continue
disk = state[src][-1] # Topmost disk from source peg
for dest in range(3): # Try each peg as destination
if src == dest: # Cannot move to same peg
continue
# Rule: Cannot place larger disk on top of smaller disk
if len(state[dest]) > 0 and state[dest][-1] < disk:
continue
# Copy pegs using simple loop (NO list comprehension)
new_pegs = []
for peg in state:
new_pegs.append(list(peg))
new_pegs[src].pop() # Remove disk from source peg
new_pegs[dest].append(disk) # Place disk onto destination peg
# Convert back to tuple of tuples using simple loop
peg_tuples = []
for peg in new_pegs:
peg_tuples.append(tuple(peg))
next_state = tuple(peg_tuples)
action = "Disk " + str(disk) + ": " + names[src] + " -> " + names[dest]
successors.append((next_state, action)) # Save legal transition
return successors # Return list of successors
# BFS search to find the shortest move sequence
def solve_hanoi(n):
# Build initial disk stack on peg A from largest to smallest
disks_list = []
for d in range(n, 0, -1):
disks_list.append(d)
start_disks = tuple(disks_list) # Tuple (3, 2, 1)
start_state = (start_disks, (), ()) # All disks initially on Peg A
goal_state = ((), (), start_disks) # All disks finally on Peg C
queue = deque() # Create FIFO queue
queue.append(start_state) # Enqueue start state
parent = {} # Tracks visited states and predecessors
parent[start_state] = (None, "START")
expanded_count = 0 # Count of expanded states
while len(queue) > 0: # Loop until queue is empty
curr = queue.popleft() # Pop oldest state (BFS exploration)
if curr == goal_state: # If goal configuration is reached
path = [] # Reconstruct solution path
while curr is not None: # Follow parent pointers backward
prev_state, action = parent[curr]
path.append((curr, action))
curr = prev_state # Step back to parent
path.reverse() # Reverse to get START -> GOAL order
return path, expanded_count
expanded_count = expanded_count + 1 # Increment expanded count
for next_state, action in get_successors(curr): # Explore legal moves
if next_state not in parent: # If not visited yet
parent[next_state] = (curr, action) # Mark visited and record parent
queue.append(next_state) # Enqueue state for future expansion
return None, expanded_count # Return None if no path found
def main():
N = 3 # Number of disks
path, expanded = solve_hanoi(N) # Solve using BFS
if path:
for step in range(len(path)): # Print each step
state = path[step][0]
action = path[step][1]
print("Step " + str(step) + ": " + action)
peg_a = str(list(state[0]))
peg_b = str(list(state[1]))
peg_c = str(list(state[2]))
print("A: " + peg_a + " B: " + peg_b + " C: " + peg_c)
print("Moves:", len(path) - 1) # Print total steps taken
print("Theoretical minimum:", 2 ** N - 1) # Print theoretical minimum (2^3 - 1 = 7)
print("Nodes expanded (excluding goal):", expanded)
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
- For three disks, start is
((3,2,1), (), ()); goal is((), (), (3,2,1)). - The last value of each peg is its top disk. Smaller numbers mean smaller disks.
successors()chooses a nonempty source peg and another destination peg.- A move is rejected if the destination top disk is smaller than the moving disk.
pegs = []and aforloop convert the immutable state into editable lists. After popping the disk and appending it to the destination peg, convert each peg back to a tuple.hanoi_bfs()usesdequeandpopleft()for FIFO order.parentstores both discovered states and the move used to reach them. A state is recorded when enqueued, preventing duplicate queue entries.- At the goal, reconstruct the path and print each peg configuration.
For N=3, the moving disks are 1,2,1,3,1,2,1. The seven moves are A-C, A-B, C-B, A-C, B-A, B-C, A-C.
Actual Verified Sample Output
Exact terminal output produced by running python pract5.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Change N to 1, 4 or 0. Expected move counts: 1, 15 and 0.
- Print only actions. Remove intermediate board printing while preserving path reconstruction.
- Compare BFS with direct recursion. BFS stores many explored states. Direct Hanoi recursion generates the known solution using O(n) call-stack space.
BFS explores up to 3^n states. In this tuple-copying implementation, creating and storing length-n states adds an O(n) factor, giving a conservative O(n*3^n) time/storage bound. Large N is unsuitable for exhaustive BFS.
Practical 6: Constraint Satisfaction Problem - Sudoku Solver
CSP • Constraint Propagation • Minimum Remaining Values
Aim & Objective
To solve 9x9 Sudoku puzzles using Constraint Satisfaction Problem (CSP) methods: Plain Backtracking vs Constraint Propagation with Minimum Remaining Values (MRV).
Theory & Core Concepts
- CSP Formulation: Variables = 81 cells (empty cells are search variables); Domain = digits {1..9}; Constraints = All-Different in each row, each column, and each 3x3 subgrid.
- Constraint Propagation: If any unfilled cell has exactly one valid candidate digit remaining, it is filled immediately as a forced assignment without branching. This repeats until no singletons remain.
- Minimum Remaining Values (MRV): When branching is required, select the unassigned cell with the smallest domain (fewest candidates) to minimize the branching factor and detect dead ends immediately.
- Performance Comparison: Plain backtracking makes 9,127 calls, 9,126 guesses, and 9,074 failed branches. Propagation + MRV solves the exact same puzzle in 1 call, 0 guesses, and 52 forced assignments!
Step-by-Step Algorithm & Dry Run
- Compute legal candidate digits for any cell:
DIGITS - (used_row | used_col | used_box)using simple loops. - propagate(board): Repeatedly scan all empty cells. If any has 0 candidates, return False (contradiction). If a cell has 1 candidate, assign it and continue. When no single-candidate cells remain, return True.
- solve(board, use_mrv):
a. If improved mode: runpropagate(); if contradiction, return None.
b. Find all empty cells. If none remain, return board (solved).
c. In improved mode: select cell withmin(candidates)(MRV). In plain mode: select first empty cell.
d. For each candidate value: create board copy, set value, recurse. If valid, return solution.
e. Backtrack and return None.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Initial Board | 30 clues provided | 52 cells are empty. |
| Plain Backtracking | Blind Search | 9,127 calls, 9,074 failed branches, 9,126 guesses before finding the solution. |
| Propagation + MRV | Constraint Deduction | 1 recursive call, 0 guesses, 52 forced assignments, 0 failed branches! |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (37 lines)
# Practical 6: Sudoku Solver using Backtracking (CSP)
# Max 35 lines - Clean & Exam-Ready
board = [
[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],
[0, 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]
]
def is_valid(b, r, c, num):
for i in range(9):
if b[r][i] == num or b[i][c] == num: return False
if b[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == num: return False
return True
def solve():
for r in range(9):
for c in range(9):
if board[r][c] == 0:
for num in range(1, 10):
if is_valid(board, r, c, num):
board[r][c] = num
if solve(): return True
board[r][c] = 0
return False
return True
solve()
print("Solved Sudoku Grid:")
for row in board:
print(*row)
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 6: Sudoku Solver - Backtracking & Constraint Propagation (MRV)
# Get legal candidate digits for an empty cell at row r, column c using plain loops
def get_candidates(board, r, c):
used = set() # Set of digits already present
# 1. Collect numbers in the same row
for val in board[r]:
if val != 0:
used.add(val)
# 2. Collect numbers in the same column
for i in range(9):
val = board[i][c]
if val != 0:
used.add(val)
# 3. Collect numbers in the 3x3 box
box_r = (r // 3) * 3 # Top row of 3x3 box
box_c = (c // 3) * 3 # Left column of 3x3 box
for i in range(box_r, box_r + 3):
for j in range(box_c, box_c + 3):
val = board[i][j]
if val != 0:
used.add(val)
# 4. Find all digits from 1 to 9 that are not used
candidates = []
for d in range(1, 10):
if d not in used:
candidates.append(d)
return candidates # Return list of valid candidate digits
# Single-candidate constraint propagation: repeatedly fill forced single candidates
def propagate(board, stats):
while True: # Repeat until no more forced cells exist
changed = False # Flag to track if any cell was filled
for r in range(9):
for c in range(9):
if board[r][c] == 0: # If cell is empty
candidates = get_candidates(board, r, c) # Find valid digits
if len(candidates) == 0: # Dead end: no valid digit possible!
return False # Return False to trigger backtracking
if len(candidates) == 1: # Forced value: only 1 legal digit exists
board[r][c] = candidates[0] # Fill cell immediately
stats["forced"] = stats["forced"] + 1
changed = True # Mark that board changed
if not changed: # If no cells were forced in this pass
return True # Propagation successful
# Backtracking solver function
def solve(board, use_mrv, stats):
stats["calls"] = stats["calls"] + 1 # Count recursive call
# In improved mode, propagate forced values before branching
if use_mrv and not propagate(board, stats):
stats["failed_branches"] = stats["failed_branches"] + 1
return None # Backtrack
# Find all empty cells using a plain loop
empty_cells = []
for r in range(9):
for c in range(9):
if board[r][c] == 0:
empty_cells.append((r, c))
if len(empty_cells) == 0: # Base case: no empty cells remain
return board # Solved!
# Select cell to branch on
if use_mrv:
# Minimum Remaining Values (MRV): find cell with fewest candidates (NO lambda)
best_cell = None
min_candidates = 999
for cell in empty_cells:
cand_count = len(get_candidates(board, cell[0], cell[1]))
if cand_count < min_candidates:
min_candidates = cand_count
best_cell = cell
r = best_cell[0]
c = best_cell[1]
else:
# Plain mode: pick the first empty cell
first_cell = empty_cells[0]
r = first_cell[0]
c = first_cell[1]
# Try each legal candidate digit
for val in get_candidates(board, r, c):
stats["guesses"] = stats["guesses"] + 1
# Copy board using plain loops (NO list comprehension)
new_board = []
for row in board:
new_row = []
for item in row:
new_row.append(item)
new_board.append(new_row)
new_board[r][c] = val # Place candidate digit
result = solve(new_board, use_mrv, stats) # Recurse
if result is not None:
return result # Propagate solution upward
stats["failed_branches"] = stats["failed_branches"] + 1
return None # Backtrack
def main():
# Initial 9x9 board with clues (0 represents empty cells)
PUZZLE = [
[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],
[0, 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 board:")
for row in PUZZLE:
print(*row)
# Compare Plain Backtracking vs. Propagation + MRV
for use_mrv in (False, True):
mode_header = "\nPropagation + MRV" if use_mrv else "\nPlain backtracking"
stats = {"calls": 0, "guesses": 0, "forced": 0, "failed_branches": 0}
# Copy initial puzzle for each run
board_copy = []
for row in PUZZLE:
board_copy.append(row.copy())
solution = solve(board_copy, use_mrv, stats)
print(mode_header)
if solution:
for row in solution:
print(*row)
print("Search statistics:", stats)
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
PUZZLEis a 9-by-9 list of lists. Zero means empty; all other entries are fixed clues.validate()checks dimensions, value range and repeated nonzero digits in every row, column and box.candidates(board,r,c)gathers used row, column and box values and subtracts them from{1,...,9}.- The containing box begins at
br=(r//3)*3,bc=(c//3)*3. propagate()repeatedly fills cells with exactly one candidate. A cell with no candidate is a contradiction.solve_sudoku(..., improved=False)uses ordinary backtracking, selecting the first empty cell and trying legal values.- With
improved=True, first propagate forced values, then use MRV to select the cell with the smallest candidate set. - A full board is success. Otherwise try a candidate on a copied board and recurse. If it fails, discard that copy and try another value.
- Because branches use separate board copies, the original clues and previous branches remain unchanged. This is the undo mechanism here; an in-place variant would reset the cell to zero.
- The program solves the same puzzle with both methods and reports recursive calls, guesses, forced assignments and failed branches.
Example: if a cell's row, column and box together use {1,2,3,5,6,8,9}, its candidates are {4,7}. If later 4 is ruled out, 7 becomes a forced value.
Actual Verified Sample Output
Exact terminal output produced by running python pract6.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- What is the difference between invalid and unsatisfiable input? Invalid clues directly violate a rule. Locally valid clues may still have no complete solution.
- Does returning one solution prove uniqueness? No. To check uniqueness, continue searching after the first solution and stop once two different solutions are found.
- Why are there no guesses in the default improved run? This sample is solved entirely by repeated forced assignments. Backtracking remains available for harder boards.
- How would you use in-place backtracking? Assign a digit, recurse, and reset it to 0 on failure; also undo every propagated assignment made in that branch.
Practical 7: Combinatorial Optimization - TSP with Local Beam Search
Combinatorial Optimization • Heuristic Search • NP-Hard
Aim & Objective
To solve the Traveling Salesman Problem (TSP) using Local Beam Search with beam width k and 2-city swap neighbourhood.
Theory & Core Concepts
- TSP Formulation: Find a Hamiltonian cycle that visits all n cities exactly once and returns to the starting city with minimum total travel cost. NP-hard combinatorial problem.
- Local Beam Search: Instead of retaining only 1 current state (like Hill Climbing), Local Beam Search maintains
kcandidate tours in parallel. - Neighbourhood Operator (2-City Swap): City 0 is anchored at the start to eliminate cyclic rotational duplicates. Neighbours are formed by swapping any pair of cities at indices 1 <= i < j < n.
- Elitist Pooling: Combines current beam tours and all generated neighbours into a shared pool, evaluates total cost (including return edge), and retains the
kbest distinct tours for the next iteration. - Incomplete Heuristic: Beam search is not guaranteed to find the global optimum; it can get trapped in local plateaus or lose diversity.
Step-by-Step Algorithm & Dry Run
- Generate
kdistinct random initial permutations with city 0 fixed. - Evaluate tour costs: sum consecutive edge weights plus edge returning from last city to city 0.
- Iterate up to
max_iterations:
a. Initialize candidate pool with current beam.
b. For each tour in beam, generate all 2-city swap neighbours and add to pool.
c. Sort pool by tour cost and select topkdistinct tours.
d. If the new beam is identical to the previous beam, break (stabilized).
e. Update beam = next_beam. - Return best-found tour and cost history.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Cities | 5 Cities (A, B, C, D, E) | Cost matrix with 5 nodes; beam k=3. |
| Iteration 0 | Initial Best Cost = 94 | Tour: A -> B -> D -> E -> C -> A |
| Iteration 1 | Swap Neighbours Evaluated | Best cost drops to 88: Tour: A -> B -> E -> D -> C -> A (10+17+16+30+15=88) |
| Iteration 2 | Beam Unchanged | Pool produces no better tours; beam stabilizes. Final cost: 88. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (37 lines)
# Practical 7: Traveling Salesman Problem (TSP) using Local Beam Search
# Max 35 lines - Clean & Exam-Ready
import random
dist = [
[0, 10, 15, 20, 25],
[10, 0, 35, 25, 17],
[15, 35, 0, 30, 28],
[20, 25, 30, 0, 16],
[25, 17, 28, 16, 0]
]
cities = ["A", "B", "C", "D", "E"]
n = len(dist)
def cost(t):
return sum(dist[t[i]][t[(i + 1) % n]] for i in range(n))
random.seed(7)
beam = [[0] + random.sample(range(1, n), n - 1) for _ in range(3)]
for _ in range(50):
cands = list(beam)
for tour in beam:
for i in range(1, n - 1):
for j in range(i + 1, n):
nbr = tour.copy()
nbr[i], nbr[j] = nbr[j], nbr[i]
cands.append(nbr)
cands.sort(key=cost)
new_beam = cands[:3]
if new_beam == beam: break
beam = new_beam
best = beam[0]
route = " -> ".join(cities[c] for c in best + [best[0]])
print(f"Best Tour Found: {route}")
print(f"Minimum Tour Cost: {cost(best)}")
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 7: Traveling Salesman Problem (TSP) using Local Beam Search
import random # Import random for generating initial tours
# Complete 5-city distance matrix (0=A, 1=B, 2=C, 3=D, 4=E)
DISTANCES = [
[0, 10, 15, 20, 25], # Distances from City A
[10, 0, 35, 25, 17], # Distances from City B
[15, 35, 0, 30, 28], # Distances from City C
[20, 25, 30, 0, 16], # Distances from City D
[25, 17, 28, 16, 0] # Distances from City E
]
# Calculate total travel distance of a tour, including returning to start city
def calculate_tour_cost(tour, distances):
total = 0 # Initialize total cost
n = len(tour) # Number of cities
for i in range(n):
city_a = tour[i] # Current city
city_b = tour[(i + 1) % n] # Next city (wraps from last city back to start)
total = total + distances[city_a][city_b] # Add edge distance
return total # Return tour cost
# Generate all 2-city swap neighbours (city 0 is fixed at start to avoid duplicate rotations)
def get_neighbours(tour):
neighbours = [] # List of generated tours
n = len(tour) # Number of cities
for i in range(1, n - 1): # Select first city to swap (skip start 0)
for j in range(i + 1, n): # Select second city to swap
new_tour = list(tour) # Copy tour
temp = new_tour[i] # Standard swap using temp variable
new_tour[i] = new_tour[j]
new_tour[j] = temp
neighbours.append(tuple(new_tour)) # Append new tour as tuple
return neighbours # Return all swap neighbours
# Key function used to sort tours by cost and break ties deterministically (NO lambda)
def get_tour_sort_key(tour):
cost = calculate_tour_cost(tour, DISTANCES)
return (cost, tour) # Primary key: cost, Secondary key: tour tuple
# Local Beam Search algorithm with beam width k
def local_beam_search(distances, k=3, max_iterations=100, seed=7):
n = len(distances) # Number of cities (5)
rng = random.Random(seed) # Seeded random generator
# Generate k distinct initial random tours starting at city 0
beam_set = set() # Set avoids duplicate initial tours
while len(beam_set) < k:
other_cities = rng.sample(range(1, n), n - 1) # Random order of cities 1 to 4
tour_list = [0] # Anchor city 0 at the start
for c in other_cities:
tour_list.append(c)
beam_set.add(tuple(tour_list)) # Add to set
beam = sorted(beam_set, key=get_tour_sort_key) # Sort initial beam
cost_history = [calculate_tour_cost(beam[0], distances)] # Track best cost
# Search loop
for _ in range(max_iterations):
pool = set(beam) # Elitist pool: include current tours
for tour in beam:
for nbr in get_neighbours(tour): # Add all 2-city swap neighbours
pool.add(nbr)
# Sort pool and select top k distinct tours
sorted_pool = sorted(pool, key=get_tour_sort_key)
next_beam = sorted_pool[:k] # Retain best k candidate tours
best_cost = calculate_tour_cost(next_beam[0], distances)
cost_history.append(best_cost) # Record best cost at this iteration
if next_beam == beam: # Stopping check: beam did not change
break
beam = next_beam # Update beam for next iteration
best_tour = beam[0] # The lowest-cost tour found
final_cost = calculate_tour_cost(best_tour, distances)
return best_tour, final_cost, cost_history
def main():
K = 3 # Beam width (3 parallel tours)
best_tour, best_cost, history = local_beam_search(DISTANCES, k=K, max_iterations=100, seed=7)
tour_with_return = best_tour + (best_tour[0],) # Append return to start city
tour_str = " -> ".join(str(c) for c in tour_with_return)
print("Best-found tour:", tour_str)
print("City labels: 0=A, 1=B, 2=C, 3=D, 4=E")
print("Best-found cost:", best_cost)
print("Best cost at initialization and after each iteration:", history)
print("Local Beam Search does not guarantee the global optimum.")
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
DISTANCES[i][j]gives the travel cost from city i to city j.- A tour is a permutation of city indices. City 0 is fixed at the start to avoid storing rotated copies of the same cycle.
tour_cost()sums consecutive edge costs.(i+1)%len(tour)includes the last-to-first edge.neighbours()swaps two positions after position 0, preserving a valid permutation.local_beam_search()validates a complete, finite, nonnegative square matrix and positive k/iteration count.random.Random(seed)generates reproducible initial tours for practice.- Beam width is capped at
(n-1)!, the number of available permutations with city 0 fixed, preventing a request for impossible numbers of distinct initial tours. pool=set(beam)combines current tours and new neighbours without duplicates. This is an elitist variant: existing good tours remain eligible.- Sort by
(tour_cost, tour)and keep[:k]. The tour itself breaks equal-cost ties deterministically. - Stop when the whole beam is unchanged or the iteration limit is reached. A single unchanged best cost is not enough to prove the beam has stopped changing.
Default tour: A-B-E-D-C-A. Cost: 10+17+16+30+15=88. Read the correction at the start of this guide before copying the manual's sample output.
Actual Verified Sample Output
Exact terminal output produced by running python pract7.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Is TSP NP-hard or NP-complete? The optimisation problem is NP-hard. Its decision version asking whether a tour of cost at most a bound exists is NP-complete.
- Is Local Beam Search the same as k independent hill climbers? No. Beam search shares the candidate pool; one parent's neighbours can replace several other beam members.
- How many tours exist? With start fixed, (n-1)! directed orders. For symmetric costs and n>2, reverse tours are equivalent, giving (n-1)!/2 distinct undirected cycles.
- Change the seed, k or matrix. Check that every city appears once and the last-to-first edge is still included.
- Can it use asymmetric costs? Yes, the code uses directed matrix entries. Do not divide by two when counting reversed routes in that setting.
For n cities and beam k, there are O(k*n^2) swap neighbours per iteration. This implementation copies and evaluates length-n tours, so work includes O(k*n^3) plus sorting, and temporary storage is larger than just k tours. Random generation of distinct initial tours is intended for small exam examples, not beam widths near huge factorial limits.
Practical 8: Uninformed Planning - BFS for 8-Puzzle
Classical Planning • Uninformed Search • Breadth-First Search
Aim & Objective
To generate an optimal action plan for solving the 8-puzzle using Breadth-First Search (BFS) in state space.
Theory & Core Concepts
- Planning as State-Space Search: Classical planning problems find an action sequence taking the world from initial state S0 to a goal state G.
- BFS Planning Properties: Explores state space level by level in order of move count. For unit step costs, BFS is guaranteed to find a plan with the minimum number of actions.
- Informed (P3) vs Uninformed (P8): Practical 3 uses A* with Manhattan heuristic guidance; Practical 8 uses pure uninformed BFS. BFS expands states radially without goal distance estimates.
- Data Structures: Uses
collections.dequefor O(1) FIFO pops, and aparentdictionary mapping child states to(parent_state, action)for cycle prevention and path reconstruction.
Step-by-Step Algorithm & Dry Run
- Validate start and goal board states and ensure identical inversion parity.
- Initialize queue
deque([start])andparent = {start: (None, 'START')}. - While queue has states:
a. Pop oldest state:current = queue.popleft().
b. Ifcurrent == goal: trace back parent chain, reverse, and return plan.
c. Increment expanded count.
d. Generate legal blank movements (UP, DOWN, LEFT, RIGHT).
e. If neighbour not in parent dictionary: record parent immediately and append to queue.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| Start State | 1 move away from intermediate | (1, 2, 3, 4, 0, 6, 7, 5, 8) |
| Step 1: DOWN | Blank moves DOWN | (1, 2, 3, 4, 5, 6, 7, 0, 8) |
| Step 2: RIGHT | Blank moves RIGHT | (1, 2, 3, 4, 5, 6, 7, 8, 0) [Goal reached] |
| Result | Moves: 2 | Expanded 8 nodes. Shortest path guaranteed. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (30 lines)
# Practical 8: Classical Planning for 8-Puzzle using BFS
# Max 30 lines - Clean & Exam-Ready
from collections import deque
start = (1, 2, 3, 4, 0, 6, 7, 5, 8)
goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
queue = deque([(start, [])])
visited = {start}
moves = [(-1, 0, "UP"), (1, 0, "DOWN"), (0, -1, "LEFT"), (0, 1, "RIGHT")]
while queue:
state, plan = queue.popleft()
if state == goal:
print(f"Goal Reached in {len(plan)} steps (BFS Planning):")
print("Plan sequence:", " -> ".join(plan))
break
b = state.index(0)
r, c = b // 3, b % 3
for dr, dc, act in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3:
nb = nr * 3 + nc
nxt = list(state)
nxt[b], nxt[nb] = nxt[nb], nxt[b]
nxt = tuple(nxt)
if nxt not in visited:
visited.add(nxt)
queue.append((nxt, plan + [act]))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 8: Classical Planning for 8-Puzzle using Breadth-First Search (BFS)
from collections import deque # Import deque for efficient FIFO queue operations
# Check if puzzle is solvable using inversion parity
def is_solvable(state):
tiles = [] # Collect tiles excluding blank (0)
for x in state:
if x != 0:
tiles.append(x)
inversions = 0 # Count out-of-order pairs
for i in range(len(tiles)):
for j in range(i + 1, len(tiles)):
if tiles[i] > tiles[j]:
inversions = inversions + 1
return inversions % 2 == 0 # Solvable if inversions count is even
# Generate all legal blank tile movements (UP, DOWN, LEFT, RIGHT)
def get_neighbours(state):
neighbours = [] # List of valid next states
blank = state.index(0) # Position of the blank tile (0)
r = blank // 3 # Blank row (0, 1, or 2)
c = blank % 3 # Blank column (0, 1, or 2)
# Allowed actions: (action_name, row_offset, col_offset)
actions = [
("UP", -1, 0),
("DOWN", 1, 0),
("LEFT", 0, -1),
("RIGHT", 0, 1)
]
for action_name, dr, dc in actions: # Test all 4 directions
nr = r + dr # New row
nc = c + dc # New column
if nr >= 0 and nr < 3 and nc >= 0 and nc < 3: # Check within 3x3 boundaries
new_blank = nr * 3 + nc # Target 1D index
board = list(state) # Copy state to list
temp = board[blank] # Swap blank with tile
board[blank] = board[new_blank]
board[new_blank] = temp
neighbours.append((tuple(board), action_name)) # Save new board tuple and action
return neighbours # Return all reachable boards
# Uninformed BFS planning to find the minimum-action plan
def bfs_plan(start, goal):
if not is_solvable(start): # Pre-check solvability
print("No solution: initial and goal inversion parities differ.")
return None, 0
queue = deque() # Create FIFO queue for BFS
queue.append(start) # Enqueue start state
parent = {} # Maps each state to (predecessor_state, action)
parent[start] = (None, "START")
expanded_count = 0 # Track expanded nodes
while len(queue) > 0: # While queue has states to explore
curr = queue.popleft() # Remove oldest state (FIFO)
if curr == goal: # Goal check
path = [] # Reconstruct plan backward
while curr is not None:
prev_state, action = parent[curr]
path.append((curr, action)) # Record board and action taken
curr = prev_state # Move back to predecessor
path.reverse() # Reverse to get START -> GOAL order
return path, expanded_count
expanded_count = expanded_count + 1 # Increment expanded count
for next_state, action in get_neighbours(curr): # Generate successors
if next_state not in parent: # If not visited yet
parent[next_state] = (curr, action) # Mark visited immediately
queue.append(next_state) # Enqueue for exploration
return None, expanded_count # Return None if no plan found
def main():
START = (1, 2, 3, 4, 0, 6, 7, 5, 8) # Initial board (0 is blank)
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0) # Goal board
path, expanded = bfs_plan(START, GOAL) # Execute BFS planning
if path:
for step in range(len(path)):
board = path[step][0]
action = path[step][1]
print("Step " + str(step) + ": " + action)
for i in range(0, 9, 3): # Print as 3x3 grid
print(board[i], board[i+1], board[i+2])
print("Moves:", len(path) - 1)
print("Nodes expanded (excluding goal):", expanded)
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
- This uses the same board representation, validation, parity check and legal blank movements as Practical 3. It is fully standalone; it does not import that program.
queue=deque([start])creates the frontier.popleft()removes the oldest state.parent={start:(None,'START')}stores discovered states and their predecessors.- For each legal unseen neighbour, record the parent before appending it to the queue.
- At the goal, follow parents backward and reverse the result to get actions in execution order.
- Unlike A*, BFS does not compute a heuristic or a priority value.
Default trace: blank DOWN then RIGHT. The start (1,2,3,4,0,6,7,5,8) reaches (1,2,3,4,5,6,7,8,0) in 2 moves.
Actual Verified Sample Output
Exact terminal output produced by running python pract8.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Why
deque.popleft()instead of listpop(0)? Deque removal is O(1); removing the first list item shifts the others and is O(n). - Why mark when enqueuing? It prevents different parents from putting the same state into the queue repeatedly.
- Why can
parentreplace a separate visited set? A state present in the parent dictionary has already been discovered. - Apply BFS to robot planning or Blocks World. Keep the queue/parent logic and change state representation, successor rules and goal test. Practical 2 already shows grid BFS; Blocks World needs legal clear-block moves.
Practical 9: Uninformed Search - DFS for Water Jug Problem
Uninformed Search • Depth-First Search • LIFO Stack
Aim & Objective
To solve the classical Water Jug Problem using Depth-First Search (DFS) with a LIFO stack.
Theory & Core Concepts
- Problem Formulation: Two jugs with integer capacities A and B without markings, measuring target quantity T in either jug. Initial state is (0, 0).
- Six Elementary Operations:
1. Fill Jug A: (A, b)
2. Fill Jug B: (a, B)
3. Empty Jug A: (0, b)
4. Empty Jug B: (a, 0)
5. Pour A into B: (a - t, b + t), where t = min(a, B - b)
6. Pour B into A: (a + t, b - t), where t = min(b, A - a) - Diophantine Solvability Condition: Target T can be measured if and only if T <= max(A, B) and T is divisible by gcd(A, B).
- DFS Characteristics: Uses LIFO stack. Explores deep branches before backtracking. Path depends on operator ordering; finds a valid path, but is not guaranteed to be shortest.
Step-by-Step Algorithm & Dry Run
- Validate capacities A, B > 0 and target >= 0.
- Check solvability: if
target > max(A, B)ortarget % gcd(A, B) != 0, return None. - Initialize stack
[(0, 0)]andparent = {(0, 0): (None, 'START')}. - While stack is not empty:
a. Pop most recently pushed state:current = stack.pop().
b. Iftarget in current: reconstruct path from parent pointers and return.
c. Generate all 6 successors using capacity limits.
d. For each unvisited successor: record parent and push to stack.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| 0. START | Jug A=0, Jug B=0 | Both jugs empty. |
| 1. Fill B | Jug A=0, Jug B=3 | Jug B filled to 3L capacity. |
| 2. Pour B -> A | Jug A=3, Jug B=0 | 3L poured into Jug A. |
| 3. Fill B | Jug A=3, Jug B=3 | Jug B filled again. |
| 4. Pour B -> A | Jug A=4, Jug B=2 | 1L transferred into Jug A (reaches 4L capacity); exactly 2L left in B! Goal reached in 4 operations. |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (28 lines)
# Practical 9: Water Jug Problem using DFS
# Max 30 lines - Clean & Exam-Ready
cap_a, cap_b, target = 4, 3, 2
stack = [((0, 0), [])]
visited = {(0, 0)}
while stack:
(a, b), path = stack.pop()
if a == target or b == target:
print(f"Goal {target}L reached in {len(path)} steps (DFS):")
for step, (act, state) in enumerate(path, 1):
print(f"{step}. {act} -> Jug A: {state[0]}L, Jug B: {state[1]}L")
break
transitions = [
("Fill A", (cap_a, b)),
("Fill B", (a, cap_b)),
("Empty A", (0, b)),
("Empty B", (a, 0)),
("Pour A -> B", (a - min(a, cap_b - b), b + min(a, cap_b - b))),
("Pour B -> A", (a + min(b, cap_a - a), b - min(b, cap_a - a)))
]
for act, nxt in transitions:
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, path + [(act, nxt)]))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 9: Water Jug Problem using Depth-First Search (DFS)
from math import gcd # Import gcd to check mathematical solvability
# Generate all 6 possible water jug transitions from current state (a, b)
def get_successors(state, cap_a, cap_b):
a = state[0] # Water in Jug A
b = state[1] # Water in Jug B
# Calculate how much water can be transferred between jugs
pour_a_to_b = min(a, cap_b - b) # Limited by water in A or remaining space in B
pour_b_to_a = min(b, cap_a - a) # Limited by water in B or remaining space in A
operations = [
((cap_a, b), "Fill A"), # 1. Fill Jug A completely
((a, cap_b), "Fill B"), # 2. Fill Jug B completely
((0, b), "Empty A"), # 3. Empty Jug A completely
((a, 0), "Empty B"), # 4. Empty Jug B completely
((a - pour_a_to_b, b + pour_a_to_b), "Pour A -> B"), # 5. Pour from A into B
((a + pour_b_to_a, b - pour_b_to_a), "Pour B -> A") # 6. Pour from B into A
]
return operations
# DFS search using a LIFO stack to find a solution path
def solve_water_jug_dfs(cap_a, cap_b, target):
# Mathematical solvability check (Bézout's identity)
if target > max(cap_a, cap_b) or target % gcd(cap_a, cap_b) != 0:
print("No solution for these capacities and target.")
return None
start_state = (0, 0) # Initial state: both jugs are empty
stack = [start_state] # LIFO stack initialized with start state
parent = {} # Tracks visited states and action taken
parent[start_state] = (None, "START")
while len(stack) > 0: # Loop while stack is not empty
curr = stack.pop() # Pop the most recently added state (DFS)
# Check if target amount is achieved in either jug
if curr[0] == target or curr[1] == target:
path = [] # Reconstruct solution path
while curr is not None: # Follow parent pointers backward
prev_state, action = parent[curr]
path.append((curr, action))
curr = prev_state # Move back to predecessor
path.reverse() # Reverse to get START -> GOAL order
return path
# Explore all 6 possible operations
for next_state, action in get_successors(curr, cap_a, cap_b):
if next_state not in parent: # If this water configuration is new
parent[next_state] = (curr, action) # Mark visited and record parent
stack.append(next_state) # Push onto stack for deep exploration
return None # Return None if no solution found
def main():
CAP_A = 4 # Capacity of Jug A (4 litres)
CAP_B = 3 # Capacity of Jug B (3 litres)
TARGET = 2 # Target amount to measure (2 litres)
path = solve_water_jug_dfs(CAP_A, CAP_B, TARGET) # Run DFS
if path:
for step in range(len(path)):
state = path[step][0]
action = path[step][1]
a = state[0]
b = state[1]
print(str(step) + ". " + action + ": Jug A=" + str(a) + " litres, Jug B=" + str(b) + " litres")
print("Operations:", len(path) - 1)
print("Goal reached. DFS does not guarantee the shortest path.")
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
- A state
(a,b)means a litres in jug A and b litres in jug B. Initially(0,0). successors()generates six operations: fill A, fill B, empty A, empty B, pour A into B and pour B into A.- Pouring A into B transfers
min(a, capacity_b-b)litres: no more than the source contains or the destination can hold. - For B into A, transfer
min(b, capacity_a-a). water_jug_dfs()checks capacity and target feasibility, then starts a Python list stack.stack.pop()removes the most recently pushed state.parentprevents revisiting states and stores actions.target in currentmeans either jug equals the target, not that their sum equals the target.- Reconstruct the path from the first goal found. The path can depend on successor ordering.
Default trace: (0,0) -> fill B -> (0,3) -> pour B-A -> (3,0) -> fill B -> (3,3) -> pour B-A -> (4,2). Target 2 is in B after 4 operations.
Actual Verified Sample Output
Exact terminal output produced by running python pract9.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
(0,0), meaning both jugs are empty.(A+1)(B+1) integer amount pairs and at most six generated operations per state.(a,b) satisfy 0<=a<=A and 0<=b<=B, with defined transitions and a target condition.Practical Exam Variations & Edge Cases
- What is the solvability condition? For positive integer capacities, unlimited filling/emptying and a target in either jug: target <= max(A,B) and target is divisible by gcd(A,B). Zero target is already satisfied initially.
- Example of impossible input? Capacities 4 and 6 cannot measure 3 litres because gcd(4,6)=2 does not divide 3.
- Convert it to BFS. Use a deque and
popleft()while keeping successor and parent logic. That finds the fewest operations when all cost one. - Why can no-op successors be ignored? They reproduce the current state, which is already discovered.
Practical 10: Constraint Satisfaction Problem - 8-Queens
CSP • Backtracking • Forward Checking • Lookahead
Aim & Objective
To solve the 8-Queens problem and evaluate the efficiency gains of Backtracking with Forward Checking compared to Plain Backtracking.
Theory & Core Concepts
- Problem Formulation: Place 8 queens on an 8x8 chessboard such that no two queens attack each other along any row, column, or diagonal.
- Representation: 1D array
queens[row] = col. Each row naturally receives at most one queen. - Conflict Conditions: Queens at (r, col_r) and (row, col) conflict if:
•col_r == col(same column)
•abs(col_r - col) == row - r(same diagonal) - Forward Checking Lookahead: Whenever a queen is placed at
(row, col), immediately look ahead and removecol, col - delta, col + deltafrom the candidate domains of all remaining future rowslater > row. - Early Wipeout Detection: If any future row's domain becomes empty (domain wipeout), backtrack immediately without descending further into that branch.
- Quantitative Result: Both find all 92 valid arrangements. Plain backtracking makes 2,057 recursive calls and tries 15,720 candidates. Forward checking makes only 1,165 calls, tries 1,724 candidates, and detects 560 domain wipeouts early!
Step-by-Step Algorithm & Dry Run
- Initialize
queens = [-1] * nusing a simple loop. - search(row, domains):
a. Ifrow == n: store solution copy and return.
b. Determine options: sorted domain for current row (in FC) or range(n) (in plain).
c. For each column option:
• If unsafe: skip.
• Place queen:queens[row] = col.
• In FC mode: prune attacked columns from future row domains. If any future domain wipes out, record wipeout and do not recurse.
• If safe: recurse torow + 1.
• Backtrack: resetqueens[row] = -1.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| First Solution | Columns by Row | [0, 4, 7, 5, 2, 6, 1, 3] |
| Board Row 0 | Queen at Col 0 | Q . . . . . . . |
| Board Row 1 | Queen at Col 4 | . . . . Q . . . |
| Board Row 2 | Queen at Col 7 | . . . . . . . Q |
| Board Row 3 | Queen at Col 5 | . . . . . Q . . |
| Board Row 4 | Queen at Col 2 | . . Q . . . . . |
| Board Row 5 | Queen at Col 6 | . . . . . . Q . |
| Board Row 6 | Queen at Col 1 | . Q . . . . . . |
| Board Row 7 | Queen at Col 3 | . . . Q . . . . |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (28 lines)
# Practical 10: 8-Queens Problem using Backtracking
# Max 30 lines - Clean & Exam-Ready
n = 8
board = [-1] * n # board[row] = col
solutions = []
def is_safe(row, col):
for r in range(row):
if board[r] == col or abs(board[r] - col) == row - r:
return False
return True
def solve(row):
if row == n:
solutions.append(board.copy())
return
for col in range(n):
if is_safe(row, col):
board[row] = col
solve(row + 1)
board[row] = -1
solve(0)
print(f"Total Solutions for {n}-Queens: {len(solutions)}")
print("First Solution (col per row):", solutions[0])
for col in solutions[0]:
print(" ".join("Q" if c == col else "." for c in range(n)))
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 10: 8-Queens Problem - Plain Backtracking vs. Forward Checking
# Check if placing a queen at (row, col) is safe from already placed queens
def safe(queens, row, col):
for r in range(row): # Check all previously placed queens
# Conflict if in the same column OR along the same diagonal
if queens[r] == col or abs(queens[r] - col) == row - r:
return False # Position is under attack
return True # Safe to place queen
# Solver function supporting both Plain Backtracking and Forward Checking
def solve_queens(n=8, forward_checking=False):
queens = [] # Build queens array using a simple loop
for i in range(n):
queens.append(-1) # -1 means unassigned
solutions = [] # List to store all valid board arrangements
stats = {"calls": 0, "candidates_tried": 0, "domain_wipeouts": 0} # Performance metrics
# Recursive search function
def search(row, domains):
stats["calls"] = stats["calls"] + 1 # Count recursive call
if row == n: # Base case: all n queens successfully placed
solutions.append(queens.copy()) # Save independent copy of the solution board
return
# Determine available columns for this row (NO ternary operator)
if forward_checking:
options = sorted(domains[row])
else:
options = list(range(n))
for col in options: # Try each column candidate
stats["candidates_tried"] = stats["candidates_tried"] + 1 # Count candidate attempt
if not safe(queens, row, col): # Skip if attacked by earlier queens
continue
queens[row] = col # Place queen at (row, col)
if forward_checking: # Forward Checking mode: lookahead & prune
# Copy future domains using plain loop (NO list comprehension)
next_domains = []
for d in domains:
next_domains.append(d.copy())
possible = True # Flag for domain wipeout
# Prune attacked columns from all future rows (later > row)
for later in range(row + 1, n):
delta = later - row # Diagonal distance
# Remove attacked columns using plain discard()
next_domains[later].discard(col)
next_domains[later].discard(col - delta)
next_domains[later].discard(col + delta)
if len(next_domains[later]) == 0: # If any future row has 0 legal columns
possible = False # Domain wipeout detected!
break # Stop pruning future rows
if possible: # If all future rows still have at least 1 legal spot
search(row + 1, next_domains) # Recurse safely
else:
stats["domain_wipeouts"] = stats["domain_wipeouts"] + 1 # Early failure detected
else:
search(row + 1, domains) # Plain mode: recurse without pruning domains
queens[row] = -1 # Backtrack: remove queen and try next column
# Initial domains: every row initially has all columns {0, 1, ..., n-1} available
initial_domains = []
for i in range(n):
initial_domains.append(set(range(n)))
search(0, initial_domains) # Start search from row 0
return solutions, stats
def main():
N = 8 # 8x8 Chessboard with 8 Queens
for use_fc in (False, True):
mode_header = "\nForward checking" if use_fc else "\nPlain backtracking"
solutions, stats = solve_queens(N, use_fc)
print(mode_header)
print("Total solutions:", len(solutions))
if solutions:
first = solutions[0] # Show first solution found
print("First solution, columns by row:", first)
for col in first: # Print board visualization
row_str = ""
for c in range(N):
if c == col:
row_str = row_str + "Q "
else:
row_str = row_str + ". "
print(row_str.strip())
else:
print("No solution.")
print("Statistics for ALL solutions:", stats)
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
queens[row]=colrepresents the board without storing all squares.-1means unassigned.safe()checks earlier rows. A conflict exists when columns match orabs(queens[r]-col)==row-r.solve_queens()defines recursivesearch(row,domains).- If
row==n, every queen is placed. Savequeens.copy()and return so other branches can still be searched. - In plain mode, try all columns and reject unsafe choices.
- In forward-checking mode, try only columns in the current domain and copy domains before modifying them.
- For a queen at
(row,col), removecol,col-deltaandcol+deltafrom each later row, wheredelta=later-row. - An empty future domain means failure can be detected immediately, before that row is reached.
- After exploring a placement, set
queens[row]=-1to undo it. - Both methods find all solutions, print the first and report counters. With N=8 there are 92 solutions.
First solution, zero-based columns by row: [0,4,7,5,2,6,1,3]. Thus the first queen is at row 0, column 0; the second is at row 1, column 4.
Actual Verified Sample Output
Exact terminal output produced by running python pract10.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
Practical Exam Variations & Edge Cases
- Why
queens.copy()when saving? Later backtracking mutates the original list; without copying, stored results would refer to the same changing board. - Print only the first solution. Return a success flag through recursion immediately after storing it. Then label statistics as first-solution statistics.
- Print all boards. Iterate over the returned solution list; the current program prints only its first board to keep output manageable.
- Try N=4. Both modes should return exactly two solutions.
- Does forward checking enforce full arc consistency? No. It mainly propagates from assigned variables into future domains; stronger propagation also reasons between unassigned variables.
Copying domains at each depth increases memory beyond the basic O(N) board/stack, and storing all solutions adds O(number_of_solutions*N).
Practical 11: Rule-Based Chatbot with Pattern Matching
NLP • Regular Expressions • Conversational AI • Pattern Matching
Aim & Objective
To develop a rule-based conversational chatbot using regular expressions (Python re module) and ordered pattern-matching rules with entity capture.
Theory & Core Concepts
- Rule-Based Architecture: Knowledge is explicitly encoded as ordered
(pattern, response)pairs rather than trained neural models. - Text Normalization Pipeline: Lowercases all characters, strips punctuation, and normalizes multi-whitespace. Makes matching insensitive to punctuation and capitalization.
- Word Boundary Matching: Regex
\bensures complete word matches (e.g., prevents greeting 'hi' from accidentally triggering inside 'this' or 'hit'). - Named Capture Groups: Uses
(?P<name>...)and(?P<mood>...)to extract entities from user input and inject them into dynamic template responses. - Termination & Fallback: Exact command fullmatch detects exit words (
bye|goodbye|exit|quit). Unknown inputs trigger a polite fallback response.
Step-by-Step Algorithm & Dry Run
- Preprocess input text: lowercase, substitute non-alphanumeric characters with spaces, collapse spaces.
- Test termination condition using
re.fullmatch(r'bye|goodbye|exit|quit', text). - If empty message, return prompt asking for input.
- Iterate through
RULESlist in priority order. - On first matching regex: extract captured dictionary entities via
match.groupdict(), title-case names, format template response, and return. - If no rule matches, return
DEFAULTresponse. - Run interactive loop in
main()with clean exit check.
Step-by-Step Execution Trace (Dry Run)
| Phase | Action Taken | System State Transition |
|---|---|---|
| User: 'HELLO!!!' | Rule: \b(hello|hi|hey)\b | AI-Bot: Hello! How can I help you? |
| User: 'My name is Akamal Shaikh' | Capture group (?P<name>...) | AI-Bot: Nice to meet you, Akamal Shaikh! |
| User: 'I feel happy' | Capture group (?P<mood>...) | AI-Bot: Glad you feel happy! |
| User: 'Tell me the weather' | No rule matches | AI-Bot: I do not have a rule for that. Try asking about AI or chatbots. |
| User: 'bye' | Exit fullmatch | AI-Bot: Goodbye! (Loop terminates) |
Python Source Code (Two Versions Available)
Version 2 (Full Lab Manual Version): Comprehensive reference with line-by-line comments, detailed diagnostics, and full state tracing.
⚡ Version 1: Quick Exam Code Exam-Ready (29 lines)
# Practical 11: Rule-Based Chatbot using Regular Expressions
# Max 30 lines - Clean & Exam-Ready
import re
rules = [
(r"\b(hello|hi|hey)\b", "Hello! How can I help you today?"),
(r"\bmy name is (?P<name>\w+)", "Nice to meet you, {name}!"),
(r"\bhow are you\b", "I'm doing well, thank you!"),
(r"\b(ai|artificial intelligence)\b", "AI is the study of systems that perceive and act intelligently."),
(r"\b(what is a chatbot|chatbot)\b", "A chatbot is an NLP program that converses with humans."),
(r"\b(bye|exit|quit)\b", "Goodbye! Have a great day!")
]
def reply(msg):
for pattern, template in rules:
m = re.search(pattern, msg.lower())
if m: return template.format(**m.groupdict()), ("bye" in pattern or "exit" in pattern)
return "I do not understand that. Ask me about AI or say hello!", False
print("AI Chatbot started! (type 'bye' to exit)")
while True:
try:
user = input("You: ")
if not user.strip(): continue
bot_msg, stop = reply(user)
print("Bot:", bot_msg)
if stop: break
except EOFError:
break
📖 Version 2: Complete Lab Reference Code Full Tracing
# Practical 11: Rule-Based Chatbot using Regular Expressions (re module)
import re # Import regular expressions module
# Ordered list of (pattern, template_response) rules
RULES = [
# Rule 1: Capture user name (e.g., "my name is Rahul")
(r"\bmy name is (?P<name>[a-z]+(?: [a-z]+)*)$", "Nice to meet you, {name}!"),
# Rule 2: Bot identity query
(r"\bwhat is your name\b", "I am AI-Bot, a rule-based chatbot."),
# Rule 3: Pleasantry / greeting enquiry
(r"\bhow are you\b", "I am fine, thank you!"),
# Rule 4: Capture positive emotion (e.g., "I feel happy")
(r"\bi (?:am(?: feeling)?|feel) (?P<mood>happy|excited|good)\b", "Glad you feel {mood}!"),
# Rule 5: Capture general emotion
(r"\bi (?:am(?: feeling)?|feel) (?P<mood>[a-z]+)\b", "You said you feel {mood}. Thank you for sharing."),
# Rule 6: Subject questions about Artificial Intelligence
(r"\b(artificial intelligence|ai)\b", "AI builds systems that perform tasks such as reasoning and problem solving."),
# Rule 7: Subject questions about Chatbots
(r"\bchatbot\b", "A chatbot is a program that converses with a user."),
# Rule 8: Technology question
(r"\b(language|python)\b", "I am written in Python using the re module."),
# Rule 9: Concept question
(r"\b(pattern matching|regular expressions?)\b", "Pattern matching checks input against predefined text patterns."),
# Rule 10: Gratitude
(r"\b(thanks|thank you)\b", "You are welcome!"),
# Rule 11: General greeting (placed after specific rules)
(r"\b(hello|hi|hey)\b", "Hello! How can I help you?")
]
DEFAULT = "I do not have a rule for that. Try asking about AI or chatbots."
# Clean and normalize input text
def preprocess(text):
text = text.lower().strip() # Convert text to lowercase and strip edges
text = re.sub(r"[^\w\s]", " ", text) # Replace punctuation marks with spaces
words = text.split() # Split into individual words
cleaned_text = " ".join(words) # Rejoin words with single space
return cleaned_text
# Match input against predefined rules and return response
def respond(user_input):
text = preprocess(user_input) # Clean the incoming user message
# Check for exit command
if re.fullmatch(r"bye|goodbye|exit|quit", text):
return "Goodbye!", True # Return goodbye message and stop flag True
if len(text) == 0: # If user entered an empty message
return "Please type a message.", False
# Check each rule in priority order
for pattern, reply in RULES:
match = re.search(pattern, text) # Search for pattern in user text
if match: # If a pattern matches
values = match.groupdict() # Extract captured variables (name, mood)
if "name" in values: # Capitalize user's name if captured
values["name"] = values["name"].title()
return reply.format(**values), False # Inject captured values into response
return DEFAULT, False # Return default fallback if no rule matched
def main():
print("AI-Bot: Hello! Type bye, goodbye, exit or quit to stop.")
while True: # Chat loop
message = input("You: ") # Read user message from terminal
if len(message.strip()) == 0: # Skip empty inputs
continue
reply, should_stop = respond(message) # Generate reply from chatbot
print("AI-Bot:", reply) # Print bot's answer
if should_stop: # If user typed an exit word
break # Exit the loop
if __name__ == "__main__":
main()
Detailed Code Explanation
Function-by-function breakdown and key variables explaining the internal logic:
RULESis an ordered list of(pattern,response)pairs. This version uses one deterministic reply per rule to make revision easier.preprocess()converts text to lowercase, replaces punctuation with spaces and collapses repeated whitespace.respond()checks a full-message exit command first. It handles empty input separately.- It tries
re.search(pattern,text)for each rule and stops at the first match. \bmatches word boundaries, so the greetinghidoes not accidentally match insidethis.(?P<name>...)and(?P<mood>...)are named capture groups.match.groupdict()retrieves the captured values.reply.format(**values)places them into{name}or{mood}in the reply. Captured names are title-cased.- If no rule matches, return
DEFAULT. The main loop prints the reply and stops when the returned stop flag is true. EOFErrorandKeyboardInterruptare handled to end cleanly if input closes or Ctrl+C is pressed.
Examples: HELLO!!! gives a greeting; My name is Akamal Shaikh inserts the name; This is a hit does not trigger hi; bye exits. bye bye does not exit because it is not one exact command.
Actual Verified Sample Output
Exact terminal output produced by running python pract11.py:
Viva Voce Questions & Model Answers
Frequently asked laboratory exam and oral viva questions with model examiner responses:
re.fullmatch recognises bye, goodbye, exit or quit as the complete normalised message.Practical Exam Variations & Edge Cases
- Difference between
re.search,re.matchandre.fullmatch? Search looks anywhere; match checks from the beginning; fullmatch requires the entire input to match. - What does the r prefix mean? A raw string preserves backslashes for the regex parser;
r"\bhi\b"expresses word boundaries clearly. - Add a college rule. Add
(r"\bcollege\b", "This is an AI laboratory chatbot.")before the general greeting rule. - Does capturing a name mean it is remembered? No. This code uses the name only in the current reply. Persistent memory requires extra state.
- How would you add several replies per rule? Store a list of response strings and use
random.choice()after a match, before formatting captured groups.
Master Comparison & Exam Viva Notes
High-yield comparison tables across all 11 AI algorithms and essential universal Python viva questions.
Core Algorithms Comparative Matrix
| Method | Frontier / Memory | Selection Rule | Time Complexity | Space Complexity | Completeness & Optimality |
|---|---|---|---|---|---|
| BFS (P5, P8) | FIFO Queue (deque) |
Oldest discovered node first | O(b^(d+1)) | O(b^(d+1)) | Complete; Optimal for unit-cost actions |
| DFS (P9) | LIFO Stack (list) |
Newest discovered node first | O(V + E) | O(V) | Complete on finite graphs with visited set; Not optimal |
| A* Search (P3) | Priority Queue (heapq) |
Minimum f(n) = g(n) + h(n) |
O(b^d) worst-case | O(b^d) | Complete & Optimal with admissible/consistent heuristic |
| Minimax (P4) | Game Tree Recursion | Alternating MAX/MIN decisions | O(b^d) | O(b · d) | Optimal against an optimal opponent in zero-sum game |
| Alpha-Beta (P4) | Recursive with bounds | Prune when α ≥ β |
O(b^(d/2)) best-case | O(b · d) | Guarantees exact same root value as Minimax; saves up to 50%+ nodes |
| Backtracking (P6, P10) | Recursive assignment | Depth-first assign & undo | O(d^n) worst-case | O(n) | Complete for finite CSPs; finds solutions if they exist |
| Forward Checking (P10) | Dynamic row domains | Lookahead & prune empty domains | Significantly reduced calls | O(n · d) | Detects inevitable failures earlier than plain backtracking |
| Local Beam Search (P7) | Set of k candidate tours |
Keep k lowest-cost candidates |
O(max_iter · k · n^2) | O(k · n^2) | Incomplete heuristic; not guaranteed to find global optimum |
Universal Python Viva Questions (Top 15)
These 15 Python questions are repeatedly asked by examiners regardless of which practical you draw:
is None avoids confusing it with failure.Final Exam Success Checklist
- State the algorithm first: Before touching the keyboard, clearly state the algorithm name and rationale to the examiner.
- Explain your data structures: Know why a
dequeis used instead oflist.pop(0)(O(1) vs O(N)). Know why board states are stored as immutable tuples (so they can be dictionary keys). - Trace a small example: Be ready to trace N=3 for Tower of Hanoi or a 2-move 8-puzzle on paper.
- Know the edge cases: Review the "Practical Exam Variations" card at the bottom of each practical page.