AI AI Practicals 1-11 Python Standard Library
ISBM COE AI Laboratory Python 3.8+ Standard Library 11 Complete Experiments

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.

How to Run Any Practical Locally:
  1. Clone or download this repository.
  2. Open a terminal in the project folder.
  3. Run: python pract1.py (or python3 pract1.py / py pract1.py).
  4. Replace 1 with any experiment number (1 to 11).
  5. 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:

The 7-Step Formula for Every Practical:
Input → State Representation → Transition / Successors → Algorithm → Termination Condition → Output → Limitations
  • 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 LIFO list stack; A* uses a min-heap priority queue via heapq; 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 Intelligent Agents pract1.py

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 ElementSystem Description for Practical 1
Performance MeasureMaximize clean rooms; minimize energy consumption and time spent moving.
EnvironmentTwo interconnected rooms (A and B); each room status is either Clean or Dirty.
ActuatorsSuction motor (Suck), movement motors (Left, Right).
SensorsDirt 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

  1. Receive current percept (location, status) from the environment.
  2. Evaluate condition-action rules: If status == 'Dirty', action is 'Suck'.
  3. If status == 'Clean' and location == 'A', action is 'Right'.
  4. If status == 'Clean' and location == 'B', action is 'Left'.
  5. Apply action to simulator: update room status or agent location.
  6. Record step in history and repeat until the simulator detects all rooms are Clean.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
Step 0StartAgent placed at Room A. Room A=Dirty, Room B=Dirty.
Step 1Percept: (A, Dirty) -> Action: SuckRoom A is cleaned. State: {'A': 'Clean', 'B': 'Dirty'}.
Step 2Percept: (A, Clean) -> Action: RightAgent moves to Room B. State: {'A': 'Clean', 'B': 'Dirty'}.
Step 3Percept: (B, Dirty) -> Action: SuckRoom B is cleaned. State: {'A': 'Clean', 'B': 'Clean'}.
StopCondition MetBoth rooms are clean. Total actions executed = 3.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (23 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract1_simple.py
# 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

pract1.py
# 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:

  • rooms is a dictionary: {"A": "Dirty", "B": "Dirty"}. location is either "A" or "B".
  • reflex_agent(location, status) is the decision-making part. Dirty means Suck; clean A means Right; clean B means Left.
  • 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 while loop 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. Change LOCATION and ROOMS for 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:

Terminal: python pract1.py
Initial: {'A': 'Dirty', 'B': 'Dirty'} Location: A 1. At A, status=Dirty: Suck 2. At A, status=Clean: Right 3. At B, status=Dirty: Suck Final: {'A': 'Clean', 'B': 'Clean'} Actions: 3 Simulation stopped: both rooms are clean.

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is an intelligent agent?
An entity that perceives its environment through sensors and acts through actuators to achieve a performance objective.
Q2. What is a simple reflex agent?
An agent that selects an action using only its current percept and fixed condition-action rules.
Q3. What is a percept here?
The current room's location and cleanliness status, such as (A, Dirty).
Q4. What are sensors and actuators here?
Sensors detect location and dirt. Actuators perform cleaning and movement.
Q5. What is a condition-action rule?
An IF-THEN rule; for example, IF the current room is dirty, THEN clean it.
Q6. What is PEAS for this task?
Performance: cleanliness with low time/energy cost. Environment: two rooms. Actuators: suck and move. Sensors: current location and dirt sensor.
Q7. Does the agent remember previous rooms?
No. The action function has no stored history or internal model.
Q8. Is the environment fully observable?
With only the current room's status visible, the whole two-room environment is partially observable. The simulator knows both rooms, but the agent does not.
Q9. What makes an action rational?
It should maximise expected performance using available information. Cleaning dirt is useful, but unnecessary movement wastes energy if movement has a cost.
Q10. Why is a dictionary used?
It maps room labels directly to their statuses, making lookup and updates easy.
Q11. Can the reflex agent decide that both rooms are clean?
Not from one local percept alone. The simulation stops externally; a memory-based agent could track both rooms.
Q12. What are its limitations?
No memory, no multi-step planning and repeated actions when the current percept is insufficient.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Intelligent Agents & Planning pract2.py

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 ElementSystem Description for Practical 2
Performance MeasureReach the target goal G with minimum path steps without colliding with obstacles.
Environment2D rectangular grid with Start (S), Goal (G), Free cells (.), and Obstacles (X).
ActuatorsOrthogonal movement (Up, Down, Left, Right).
SensorsLocal 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

  1. Initialize internal model grid with ? (unseen) using simple nested loops.
  2. Sense current cell and 4 adjacent orthogonal neighbours; record actual contents into internal model.
  3. Mark current position as visited.
  4. While position != goal:
  5.   a. Run BFS planner targeting the Goal G using only known free cells (., S, G).
  6.   b. If route to goal exists, follow it.
  7.   c. If no route to goal, identify all sensed, free, unvisited cells and BFS plan to the nearest one (exploration mode).
  8.   d. If no exploration target is reachable, terminate with failure (unreachable goal).
  9.   e. Traverse each step of the planned route, sense newly adjacent cells after each move, and replan.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
StartAt (0, 0)Model senses neighbours (0,1) and (1,0). Both are free.
Moves 1-9ExplorationAgent moves through column 0, hits obstacle at (4,0), moves right along row 3 and up column 2.
Moves 10-14MappingSenses upper and central obstacles; gradually uncovers passage towards column 4.
Moves 15-20Goal PathUncovers clear path down column 4 into (4,4) [Goal]. Goal reached in 20 moves.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (44 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract2_simple.py
# 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

pract2.py
# 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:

  • GRID is a list of equal-length strings. S is start, G is goal, . is free and X is blocked.
  • ModelBasedAgent.__init__() creates the position, known goal coordinates, visited set, actual travel path and 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:

Terminal: python pract2.py
Goal reached! Actual travel path: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (2, 2), (1, 2), (0, 2), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (1, 4), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)] Moves: 20 Remembered map (? = unseen): S . . X . . X . X . . X . . . . . . X . X X . . G

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is a model-based agent?
An agent that maintains internal state representing what it has learned about the environment.
Q2. How does it differ from a simple reflex agent?
A simple reflex agent uses only the current percept. A model-based agent combines the percept with remembered state.
Q3. What is the internal state in this code?
The discovered map, position, visited locations and movement history.
Q4. What does `?` mean?
The cell has not yet been sensed. It is neither assumed free nor assumed blocked for planning; traversal is disallowed until known free.
Q5. Why is the environment partially observable?
The sensor reveals only the current cell and adjacent cells, not the whole grid.
Q6. Why use BFS?
On the known grid with equal-cost moves, BFS finds a shortest route to a selected reachable target.
Q7. Does this guarantee the globally shortest start-to-goal trip?
No. Exploration is needed because the full map is initially unknown.
Q8. Why keep a visited set?
It prevents selecting already explored cells as fresh exploration targets. Returning through a visited cell may still be necessary.
Q9. What happens at a dead end?
The agent can plan back through remembered free cells to another unvisited target.
Q10. What happens when the goal is unreachable?
After exhausting reachable exploration targets, it returns failure instead of moving forever.
Q11. Is this only a reflex agent?
It is a model-based agent with a planning component; the BFS component additionally uses goals.
Q12. What assumptions are made?
A static rectangular grid, four-direction movement, known map dimensions and goal coordinates, and reliable local sensing.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Heuristic Search pract3.py

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), where g(n) is the exact cost from start to node n, and h(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

  1. Validate state (all digits 0..8 present) and verify parity(start) == parity(goal).
  2. Initialize priority queue (min-heap) with (f=h(start), g=0, start).
  3. Initialize best_g = {start: 0} and parent = {start: (None, 'START')}.
  4. While frontier is not empty:
  5.   a. Pop state with lowest f. If g > best_g[current], discard stale entry.
  6.   b. If current == goal, reconstruct solution path and return.
  7.   c. Increment expanded node counter.
  8.   d. Generate legal blank swaps (UP, DOWN, LEFT, RIGHT).
  9.   e. For each neighbour, compute new_g = g + 1. If new_g < best_g[nxt], record best_g, parent, calculate f = new_g + h(nxt), and push to min-heap.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
Initialf = 0 + 6 = 6Board has tiles 5, 6, 4 misplaced.
Step 1-6Blank NavigationBlank slides LEFT, LEFT, DOWN, RIGHT, RIGHT, UP around tiles.
Step 7-12Tile AlignmentTiles 5 and 6 placed into top rows; tiles 7 and 8 aligned.
Step 13DOWN -> Goal reached!Final tile 4 placed into row 1. Solved in 13 moves; 91 nodes expanded.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (37 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract3_simple.py
# 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

pract3.py
# 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; 0 means 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 using index(0), converts its index to row and column using divmod, and generates legal swaps.
  • manhattan() adds each numbered tile's horizontal and vertical distance from its goal location. It excludes the blank.
  • frontier is 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:

Terminal: python pract3.py
Step 0: START 1 2 3 5 6 0 7 8 4 Step 1: LEFT 1 2 3 5 0 6 7 8 4 Step 2: LEFT 1 2 3 0 5 6 7 8 4 Step 3: DOWN 1 2 3 7 5 6 0 8 4 Step 4: RIGHT 1 2 3 7 5 6 8 0 4 Step 5: RIGHT 1 2 3 7 5 6 8 4 0 Step 6: UP 1 2 3 7 5 0 8 4 6 Step 7: LEFT 1 2 3 7 0 5 8 4 6 Step 8: DOWN 1 2 3 7 4 5 8 0 6 Step 9: LEFT 1 2 3 7 4 5 0 8 6 Step 10: UP 1 2 3 0 4 5 7 8 6 Step 11: RIGHT 1 2 3 4 0 5 7 8 6 Step 12: RIGHT 1 2 3 4 5 0 7 8 6 Step 13: DOWN 1 2 3 4 5 6 7 8 0 Moves: 13 Nodes expanded (excluding goal): 91

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is heuristic search?
Search that uses an estimate of remaining cost to choose promising states.
Q2. What is A*'s evaluation function?
f(n)=g(n)+h(n), actual cost so far plus estimated remaining cost.
Q3. What is the difference between g and h?
g is known cost from the start; h is an estimate of cost to the goal.
Q4. What is an admissible heuristic?
A heuristic that never overestimates the true cheapest remaining cost.
Q5. What is a consistent heuristic?
For every edge n to n', h(n) <= cost(n,n') + h(n'); the goal has h=0.
Q6. Why is Manhattan distance admissible here?
Each legal move moves one numbered tile by only one grid step. Ignoring other tiles cannot require more moves than the real constrained problem.
Q7. Why not count the blank?
One action moves both a tile and the blank. Counting both can overestimate the required number of moves.
Q8. How does A* differ from Greedy Best-First Search?
Greedy uses h alone; A* uses g+h. Greedy does not generally guarantee a cheapest solution.
Q9. What is OPEN?
The frontier of discovered states awaiting expansion, held in a priority queue.
Q10. What is CLOSED?
Conventionally the set of expanded states. This implementation instead keeps best costs and skips stale heap entries, allowing cheaper routes to be processed.
Q11. When is A* optimal?
With an admissible heuristic and correct handling of improved paths under standard nonnegative-cost search conditions. Consistency is sufficient when expanded states are never reopened. Our Manhattan heuristic is consistent.
Q12. When is this 8-puzzle unsolvable?
When start and goal inversion parities differ. For the standard goal, the start must have even inversion parity.
Q13. What happens if h is always zero?
A* becomes Uniform-Cost Search. With unit edge costs, it finds solutions by depth like BFS.
Q14. What is its complexity?
Worst-case search time and memory can be exponential in solution depth. A commonly taught search-tree bound is O(b^d), subject to the problem's cost/heuristic assumptions.
Q15. Where else is A* useful?
Game pathfinding and robot path planning when states, transitions, costs and a suitable heuristic are defined.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Game Theory & Search pract4.py

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 take min(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

  1. Define terminal leaf scores in power-of-2 array, and calculate tree depth.
  2. Minimax(leaves, depth, index, is_maximizing):
    If depth is 0, return leaves[index]. Recurse on left child 2*index and right child 2*index+1. Return max() if maximizing else min().
  3. AlphaBeta(leaves, depth, index, is_maximizing, α, β):
    If depth is 0, return leaves[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)

PhaseAction TakenSystem State Transition
Leaf Array16 leaves[6, 8, 0, 5, 8, 9, 1, 1, 3, 5, 2, 9, 0, 9, 6, 5]
MinimaxExhaustiveVisits all 31 nodes in the binary game tree. Returns root score = 6.
Alpha-BetaWith PruningVisits only 18 nodes. Skips 13 nodes (41.9% reduction). Returns root score = 6.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (36 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract4_simple.py
# 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

pract4.py
# 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:

  • LEAVES holds 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 using bit_length()-1.
  • In minimax(), depth zero returns the leaf value. Otherwise recurse on child indices 2*index and 2*index+1 at the next level.
  • not maximizing alternates 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 using min.
  • if alpha >= beta: break skips 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:

Terminal: python pract4.py
Leaves: [6, 8, 0, 5, 8, 9, 1, 1, 3, 5, 2, 9, 0, 9, 6, 5] Minimax: value=6, nodes visited=31 Alpha-Beta: value=6, nodes visited=18 Nodes avoided: 13 (41.9%)

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is adversarial search?
Search in a competitive setting where another agent's choices affect the outcome.
Q2. What is a zero-sum game?
One player's gain is balanced by the other player's loss; the total payoff is zero.
Q3. What does Minimax assume?
Both players choose optimal moves: MAX maximises the score and MIN minimises MAX's score.
Q4. What is a game tree?
A tree of game states connected by legal moves, with leaf scores representing outcomes or evaluations.
Q5. What is alpha?
A lower bound on what MAX can already secure along the relevant search path.
Q6. What is beta?
An upper bound on what MIN can already enforce along that path.
Q7. When does pruning occur?
When alpha >= beta, meaning the remaining children cannot improve the relevant ancestor's decision.
Q8. Does pruning change the correct Minimax root value?
No; it removes unnecessary evaluation, not a potentially better root decision.
Q9. Why initialise alpha=-infinity and beta=+infinity?
Initially neither player has established a limiting bound.
Q10. How does move ordering affect pruning?
Good moves examined first tighten bounds sooner and allow more cutoffs.
Q11. What is the worst-case time?
O(b^d), like Minimax, when ordering provides little pruning.
Q12. What is the best-case time?
Approximately O(b^(d/2)) with ideal ordering in the standard analysis.
Q13. What is a heuristic evaluation function?
A function estimating a nonterminal state's value when search stops at a depth limit.
Q14. Where is this used?
Two-player game programs such as chess, checkers and tic-tac-toe search.
Q15. Does standard Alpha-Beta directly cover all multi-player or random games?
No. More players or chance outcomes require different modelling and algorithms, such as Max-n or expectiminimax.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 pract5.py

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

  1. Define start state (tuple(N..1), (), ()) and goal state ((), (), tuple(N..1)).
  2. Initialize FIFO queue with start and parent dictionary {start: (None, 'START')}.
  3. While queue is not empty:
  4.   a. Pop current state from the front of the queue.
  5.   b. If current == goal, trace back parent pointers and return the move sequence.
  6.   c. Increment expanded nodes counter.
  7.   d. For each source peg (0..2) and target peg (0..2):
        If legal move: construct next state.
        If next state not in parent: record parent and append to queue.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
Step 0STARTA: [3, 2, 1], B: [], C: []
Step 1Disk 1: A -> CA: [3, 2], B: [], C: [1]
Step 2Disk 2: A -> BA: [3], B: [2], C: [1]
Step 3Disk 1: C -> BA: [3], B: [2, 1], C: []
Step 4Disk 3: A -> CA: [], B: [2, 1], C: [3]
Step 5Disk 1: B -> AA: [1], B: [2], C: [3]
Step 6Disk 2: B -> CA: [1], B: [], C: [3, 2]
Step 7Disk 1: A -> CA: [], B: [], C: [3, 2, 1] [Goal reached in exactly 7 moves]

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (29 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract5_simple.py
# 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

pract5.py
# 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 a for loop 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() uses deque and popleft() for FIFO order.
  • parent stores 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:

Terminal: python pract5.py
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] Moves: 7 Theoretical minimum: 7 Nodes expanded (excluding goal): 24

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is Tower of Hanoi?
Move a stack of differently sized disks between three pegs, one top disk at a time, without placing a larger disk on a smaller one.
Q2. What is the state?
The ordered contents of all three pegs, not only the number of disks on each peg.
Q3. What is the initial and goal state?
Initially all disks are on A; finally all disks are on C, in valid size order.
Q4. What is a legal action?
Move one top disk to an empty peg or onto a larger top disk.
Q5. Why use BFS?
Every move costs one, so BFS finds a path with the fewest moves.
Q6. What is the minimum number of moves?
2^n-1. For n=3 it is 7; for n=4 it is 15.
Q7. What recurrence gives that formula?
T(n)=2T(n-1)+1 with T(0)=0.
Q8. How is ordinary recursion different?
It directly applies the known strategy. BFS discovers a solution by exploring legal states.
Q9. Why is a visited collection needed?
Moves can reverse previous moves, producing cycles and repeated configurations.
Q10. How many legal arrangements are there?
3^n: each disk is assigned to one of three pegs, and legal size order then determines its position.
Q11. What is the maximum branching factor?
At most three legal moves for a nontrivial classical three-peg configuration.
Q12. What if the legal-move rules change?
Change the successor function. BFS still finds a shortest reachable solution when all move costs are equal.
Q13. Can there be more than three pegs?
Yes, but the optimal strategy and move count differ; 2^n-1 is the classical three-peg formula.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Problems pract6.py

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

  1. Compute legal candidate digits for any cell: DIGITS - (used_row | used_col | used_box) using simple loops.
  2. 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.
  3. solve(board, use_mrv):
      a. If improved mode: run propagate(); if contradiction, return None.
      b. Find all empty cells. If none remain, return board (solved).
      c. In improved mode: select cell with min(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)

PhaseAction TakenSystem State Transition
Initial Board30 clues provided52 cells are empty.
Plain BacktrackingBlind Search9,127 calls, 9,074 failed branches, 9,126 guesses before finding the solution.
Propagation + MRVConstraint Deduction1 recursive call, 0 guesses, 52 forced assignments, 0 failed branches!

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (37 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract6_simple.py
# 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

pract6.py
# 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:

  • PUZZLE is 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:

Terminal: python pract6.py
Initial 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 Plain backtracking 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 Search statistics: {'calls': 9127, 'guesses': 9126, 'forced': 0, 'failed_branches': 9074} Propagation + MRV 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 Search statistics: {'calls': 1, 'guesses': 0, 'forced': 52, 'failed_branches': 0}

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is Sudoku?
A 9-by-9 digit puzzle where each row, column and 3-by-3 box must contain 1 through 9 once each.
Q2. Why is it a CSP?
It assigns values to variables while satisfying a set of restrictions.
Q3. What are its variables?
The cells; in the implementation we search only unfilled cells because clue cells are fixed.
Q4. What is the domain?
Digits 1-9, reduced to the currently legal candidates.
Q5. What are the three main constraints?
No repeated digit in a row, column or 3-by-3 box.
Q6. What is backtracking?
Try a choice, continue recursively, and undo the choice when it cannot lead to a solution.
Q7. Why is backtracking needed?
A locally legal digit can cause a contradiction later; the algorithm must reconsider it.
Q8. What is constraint propagation?
Using constraints and current assignments to eliminate impossible values and derive further forced assignments.
Q9. How does propagation reduce the search space?
It removes invalid candidates and sometimes fills cells without guessing.
Q10. What is a candidate value?
A digit that does not currently violate the cell's row, column or box constraints.
Q11. What is MRV?
Minimum Remaining Values: select the unassigned variable with the fewest legal values.
Q12. What happens if a cell has no candidate?
The current branch fails, so backtrack to an earlier choice.
Q13. What is recursion?
A function solving a smaller instance by calling itself until a base case is reached.
Q14. What is the worst-case search time?
A simple loose bound is O(9^m) for m initially empty cells, ignoring bookkeeping. Pruning usually reduces actual work substantially.
Q15. How does backtracking differ from brute force?
It rejects invalid partial assignments early, instead of waiting until every cell is filled.
Q16. How can performance improve?
MRV, candidate propagation, least-constraining values and efficient row/column/box tracking.
Q17. Define a CSP generally.
A set of variables, a domain for each variable and constraints on their permitted combinations.
Q18. Give two real-world CSP applications.
Timetable generation and resource allocation.
Q19. Can backtracking solve every Sudoku?
Exhaustive correct search can find a solution whenever one exists, but some inputs are invalid or unsatisfiable, and hard puzzles may take longer.
Q20. What is the role of a heuristic here?
It chooses a promising search order, such as MRV, without changing Sudoku's rules.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Heuristic Optimization pract7.py

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 k candidate 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 k best 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

  1. Generate k distinct random initial permutations with city 0 fixed.
  2. Evaluate tour costs: sum consecutive edge weights plus edge returning from last city to city 0.
  3. 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 top k distinct tours.
      d. If the new beam is identical to the previous beam, break (stabilized).
      e. Update beam = next_beam.
  4. Return best-found tour and cost history.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
Cities5 Cities (A, B, C, D, E)Cost matrix with 5 nodes; beam k=3.
Iteration 0Initial Best Cost = 94Tour: A -> B -> D -> E -> C -> A
Iteration 1Swap Neighbours EvaluatedBest cost drops to 88: Tour: A -> B -> E -> D -> C -> A (10+17+16+30+15=88)
Iteration 2Beam UnchangedPool produces no better tours; beam stabilizes. Final cost: 88.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (37 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract7_simple.py
# 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

pract7.py
# 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:

Terminal: python pract7.py
Best-found tour: 0 -> 1 -> 4 -> 3 -> 2 -> 0 City labels: 0=A, 1=B, 2=C, 3=D, 4=E Best-found cost: 88 Best cost at initialization and after each iteration: [94, 88, 88] Local Beam Search does not guarantee the global optimum.

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is TSP?
Find a minimum-cost tour visiting each city exactly once and returning to the starting city.
Q2. Why is it an optimisation problem?
Many valid tours can exist; we want the one with the lowest objective value.
Q3. What is a Hamiltonian cycle?
A cycle that visits every vertex once and returns to its start.
Q4. What is local search?
Improving complete candidate solutions by moving to nearby solutions.
Q5. What is Local Beam Search?
A method that maintains k states and repeatedly selects promising states from their combined successors.
Q6. How does it differ from single-state local search?
It considers several candidates at once instead of only one current solution.
Q7. What is beam width?
The number of candidate states retained at each iteration.
Q8. What does k represent here?
The beam width; the default value is 3.
Q9. How are neighbours generated?
By swapping two non-start city positions; other valid methods include reversing a segment.
Q10. What is the evaluation function?
Total tour cost, including return to the starting city.
Q11. Why minimise distance?
It is the defined objective. The same formulation could instead minimise time or another stated cost.
Q12. What happens to a lower-cost candidate?
It ranks ahead of more expensive candidates when selecting the next beam.
Q13. Does Local Beam Search guarantee an optimum?
No. It can discard useful paths and converge to a locally good region.
Q14. Why retain multiple candidates?
They can explore different regions and provide more alternatives than a single current tour.
Q15. What happens when k increases?
More candidates and neighbours can be considered, but computation and memory use rise; improvement is not guaranteed for every run.
Q16. What are stopping conditions?
An unchanged beam, a maximum iteration count or another explicitly defined budget/target.
Q17. What is a local optimum?
A solution with no better neighbour under the chosen neighbourhood, even though a better distant solution may exist.
Q18. How can beam search lose diversity?
The selected candidates may become very similar, concentrating search in one region.
Q19. Give applications.
Delivery route planning, logistics and other combinatorial optimisation tasks.
Q20. Compare hill climbing and Local Beam Search.
Hill climbing normally keeps one state. Local Beam Search keeps k and selects globally from their combined candidates; k=1 in this elitist implementation behaves like best-improvement hill climbing with plateau tie handling.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 AI Planning pract8.py

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.deque for O(1) FIFO pops, and a parent dictionary mapping child states to (parent_state, action) for cycle prevention and path reconstruction.

Step-by-Step Algorithm & Dry Run

  1. Validate start and goal board states and ensure identical inversion parity.
  2. Initialize queue deque([start]) and parent = {start: (None, 'START')}.
  3. While queue has states:
      a. Pop oldest state: current = queue.popleft().
      b. If current == 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)

PhaseAction TakenSystem State Transition
Start State1 move away from intermediate(1, 2, 3, 4, 0, 6, 7, 5, 8)
Step 1: DOWNBlank moves DOWN(1, 2, 3, 4, 5, 6, 7, 0, 8)
Step 2: RIGHTBlank moves RIGHT(1, 2, 3, 4, 5, 6, 7, 8, 0) [Goal reached]
ResultMoves: 2Expanded 8 nodes. Shortest path guaranteed.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (30 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract8_simple.py
# 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

pract8.py
# 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:

Terminal: python pract8.py
Step 0: START 1 2 3 4 0 6 7 5 8 Step 1: DOWN 1 2 3 4 5 6 7 0 8 Step 2: RIGHT 1 2 3 4 5 6 7 8 0 Moves: 2 Nodes expanded (excluding goal): 8

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is BFS?
Breadth-First Search explores states level by level from the starting state.
Q2. Why is BFS uninformed?
It does not use an estimate of how far a state is from the goal.
Q3. Which data structure does it use?
A FIFO queue.
Q4. What is a state in planning?
A representation of the current situation, here the complete arrangement of tiles and blank.
Q5. What is an initial state?
The configuration where planning begins.
Q6. What is a goal state?
A configuration satisfying the desired condition, here the target board.
Q7. What is a successor?
A state produced by applying one legal action.
Q8. What is state-space search?
Exploring states and transitions to find a path from an initial state to a goal.
Q9. How is BFS applied here?
Enqueue the board, generate valid blank moves and process boards in FIFO order.
Q10. What represents the blank?
The number 0.
Q11. What actions are allowed?
Up, down, left and right, subject to board boundaries.
Q12. Why track visited states?
Sliding moves can reverse one another, so the graph has cycles and repeated boards.
Q13. What is path reconstruction?
Following saved predecessor links from the goal back to the start and reversing them.
Q14. Is BFS complete?
Yes on this finite reachable graph with repeated-state checking. More generally, standard BFS is complete with finite branching and a finite-depth solution.
Q15. Is BFS optimal?
It returns a path with the fewest actions. This is also least cost when every action has equal cost.
Q16. What if action costs differ?
Fewest actions need not mean lowest cost; use Uniform-Cost Search or appropriately configured A*.
Q17. What is its time complexity?
O(V+E) on an explicit graph. In search-tree terms, a common bound is O(b^(d+1)) depending on when goal testing occurs.
Q18. What is its space complexity?
O(V) with graph search. Its frontier can be exponential in solution depth in large implicit search spaces.
Q19. What is its main limitation?
Large memory use and exploring many states without heuristic guidance.
Q20. How is it different from DFS?
BFS uses a queue and explores shallow states first; DFS uses a stack and goes deeper first.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • Why deque.popleft() instead of list pop(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 parent replace 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 State-Space Search pract9.py

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

  1. Validate capacities A, B > 0 and target >= 0.
  2. Check solvability: if target > max(A, B) or target % gcd(A, B) != 0, return None.
  3. Initialize stack [(0, 0)] and parent = {(0, 0): (None, 'START')}.
  4. While stack is not empty:
      a. Pop most recently pushed state: current = stack.pop().
      b. If target 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)

PhaseAction TakenSystem State Transition
0. STARTJug A=0, Jug B=0Both jugs empty.
1. Fill BJug A=0, Jug B=3Jug B filled to 3L capacity.
2. Pour B -> AJug A=3, Jug B=03L poured into Jug A.
3. Fill BJug A=3, Jug B=3Jug B filled again.
4. Pour B -> AJug A=4, Jug B=21L transferred into Jug A (reaches 4L capacity); exactly 2L left in B! Goal reached in 4 operations.

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (28 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract9_simple.py
# 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

pract9.py
# 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. parent prevents revisiting states and stores actions.
  • target in current means 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:

Terminal: python pract9.py
0. START: Jug A=0 litres, Jug B=0 litres 1. Fill B: Jug A=0 litres, Jug B=3 litres 2. Pour B -> A: Jug A=3 litres, Jug B=0 litres 3. Fill B: Jug A=3 litres, Jug B=3 litres 4. Pour B -> A: Jug A=4 litres, Jug B=2 litres Operations: 4 Goal reached. DFS does not guarantee the shortest path.

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is DFS?
Depth-First Search explores a branch deeply before returning to other alternatives.
Q2. Why is it called depth-first?
Its last-added candidate is explored before older candidates, encouraging deeper traversal.
Q3. Which data structure is used?
A LIFO stack; recursion can also provide an implicit call stack.
Q4. What is the initial state here?
(0,0), meaning both jugs are empty.
Q5. What is the goal condition?
Either jug contains the target amount; the other jug may contain any legal amount.
Q6. What are the allowed operations?
Fill, empty, or pour from one jug into the other until one is empty or the other is full.
Q7. Why is a visited collection needed?
Filling and emptying can lead back to previous states; visited tracking prevents cycles.
Q8. What is state-space search here?
Exploring legal water-amount pairs connected by jug operations.
Q9. Does DFS always find the shortest solution?
No. It finds a reachable solution, whose length depends on exploration order.
Q10. What is its time complexity here?
O(V+E); there are at most (A+1)(B+1) integer amount pairs and at most six generated operations per state.
Q11. What is its space complexity here?
O(V), because this implementation stores discovered states and parent information. The common O(bm) DFS tree-search bound refers to a different storage model.
Q12. What is the difference between BFS and DFS?
FIFO versus LIFO; BFS finds fewest steps with equal costs, while DFS does not guarantee that.
Q13. How is the problem represented mathematically?
States (a,b) satisfy 0<=a<=A and 0<=b<=B, with defined transitions and a target condition.
Q14. How would DFS solve Missionaries and Cannibals?
Represent people counts and boat side; generate legal boat trips and reject unsafe states before exploring.
Q15. How would it solve a maze?
Represent a position, generate unblocked neighbouring cells and search until the exit is reached.
Q16. What is backtracking?
Returning to an earlier decision to try another branch after a branch fails or finishes.
Q17. What if the stack becomes empty?
No reachable goal was found under the defined rules.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Problems pract10.py

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 remove col, col - delta, col + delta from the candidate domains of all remaining future rows later > 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

  1. Initialize queens = [-1] * n using a simple loop.
  2. search(row, domains):
      a. If row == 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 to row + 1.
        • Backtrack: reset queens[row] = -1.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
First SolutionColumns by Row[0, 4, 7, 5, 2, 6, 1, 3]
Board Row 0Queen at Col 0Q . . . . . . .
Board Row 1Queen at Col 4. . . . Q . . .
Board Row 2Queen at Col 7. . . . . . . Q
Board Row 3Queen at Col 5. . . . . Q . .
Board Row 4Queen at Col 2. . Q . . . . .
Board Row 5Queen at Col 6. . . . . . Q .
Board Row 6Queen at Col 1. Q . . . . . .
Board Row 7Queen at Col 3. . . Q . . . .

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (28 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract10_simple.py
# 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

pract10.py
# 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]=col represents the board without storing all squares. -1 means unassigned.
  • safe() checks earlier rows. A conflict exists when columns match or abs(queens[r]-col)==row-r.
  • solve_queens() defines recursive search(row,domains).
  • If row==n, every queen is placed. Save queens.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), remove col, col-delta and col+delta from each later row, where delta=later-row.
  • An empty future domain means failure can be detected immediately, before that row is reached.
  • After exploring a placement, set queens[row]=-1 to 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:

Terminal: python pract10.py
Plain backtracking Total solutions: 92 First solution, columns by row: [0, 4, 7, 5, 2, 6, 1, 3] Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . Statistics for ALL solutions: {'calls': 2057, 'candidates_tried': 15720, 'domain_wipeouts': 0} Forward checking Total solutions: 92 First solution, columns by row: [0, 4, 7, 5, 2, 6, 1, 3] Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . Statistics for ALL solutions: {'calls': 1165, 'candidates_tried': 1724, 'domain_wipeouts': 560}

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is the 8-Queens problem?
Place eight queens so no pair attacks along a row, column or diagonal.
Q2. Why is it a CSP?
Each row chooses a column subject to non-attacking constraints.
Q3. What are the variables?
Q0 through Q7, one per row.
Q4. What is each domain?
Columns 0 through 7 before pruning.
Q5. What are the constraints?
One queen per row, different columns and no shared diagonals. The row constraint is built into the representation.
Q6. How are diagonal attacks checked?
Two queens attack diagonally when absolute row difference equals absolute column difference.
Q7. What is backtracking?
Choose a column, recurse, and undo the placement to try alternatives when necessary.
Q8. Why do we need it?
A safe placement now may leave later rows without a legal position.
Q9. What is constraint propagation?
Using assignments and constraints to reduce other variables' available values.
Q10. What is forward checking?
After a placement, remove attacked values from unassigned variables' domains and detect empty domains.
Q11. How does it reduce search?
It detects some inevitable failures before deeper recursive calls.
Q12. What if a row has no safe column?
Return to the previous row and try another placement.
Q13. How many solutions are there?
92 when rotated/reflected boards are counted separately; 12 fundamental symmetry classes.
Q14. How large is the naive search space?
With one queen per row and unrestricted columns, 8^8 arrangements. Unique-column assignments reduce complete candidates to 8!.
Q15. How is backtracking better than brute force?
Invalid partial placements are rejected before generating every complete board.
Q16. What is the time complexity?
Exponential/factorial growth; O(N!) is the common high-level bound for a column-restricted search, with additional checking and copying costs in straightforward code.
Q17. How can it be improved?
Forward checking, MRV, fast column/diagonal sets or bitmasks, and symmetry reduction.
Q18. What is MRV?
Choose the unassigned row with the fewest remaining legal columns. Our code uses fixed row order; adding MRV requires tracking which rows are assigned.
Q19. Give two applications of CSP techniques.
Scheduling and resource allocation.
Q20. Does N-Queens have a solution for every N>3?
Yes. N=1 also has a solution; N=2 and N=3 do not.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • 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 Natural Language Processing pract11.py

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 \b ensures 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

  1. Preprocess input text: lowercase, substitute non-alphanumeric characters with spaces, collapse spaces.
  2. Test termination condition using re.fullmatch(r'bye|goodbye|exit|quit', text).
  3. If empty message, return prompt asking for input.
  4. Iterate through RULES list in priority order.
  5. On first matching regex: extract captured dictionary entities via match.groupdict(), title-case names, format template response, and return.
  6. If no rule matches, return DEFAULT response.
  7. Run interactive loop in main() with clean exit check.

Step-by-Step Execution Trace (Dry Run)

PhaseAction TakenSystem State Transition
User: 'HELLO!!!'Rule: \b(hello|hi|hey)\bAI-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 matchesAI-Bot: I do not have a rule for that. Try asking about AI or chatbots.
User: 'bye'Exit fullmatchAI-Bot: Goodbye! (Loop terminates)

Python Source Code (Two Versions Available)

Exam Tip — Choose Your Code Version:
Version 1 (Exam Quick Version): Short, minimal (29 lines), max 30-40 lines, perfect for memorizing and writing quickly on answer sheets or IDLE during exams.
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)

pract11_simple.py
# 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

pract11.py
# 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:

  • RULES is 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.
  • \b matches word boundaries, so the greeting hi does not accidentally match inside this.
  • (?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.
  • EOFError and KeyboardInterrupt are 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:

Terminal: python pract11.py
AI-Bot: Hello! Type bye, goodbye, exit or quit to stop. You: AI-Bot: Hello! How can I help you? You: AI-Bot: Nice to meet you, Akamal Shaikh! You: AI-Bot: Glad you feel happy! You: AI-Bot: I do not have a rule for that. Try asking about AI or chatbots. You: AI-Bot: I do not have a rule for that. Try asking about AI or chatbots. You: AI-Bot: Please type a message. You: AI-Bot: Goodbye!

Viva Voce Questions & Model Answers

Frequently asked laboratory exam and oral viva questions with model examiner responses:

Q1. What is a chatbot?
A program that interacts with a user through conversation, usually text or voice.
Q2. What is a rule-based chatbot?
A chatbot whose replies are selected using manually written rules rather than learned behaviour.
Q3. What is pattern matching?
Checking whether input text contains or follows a specified pattern.
Q4. What is a regular expression?
A compact notation describing a pattern of characters or words.
Q5. What does Python's re module provide?
Regular-expression operations such as search, fullmatch and substitution.
Q6. What is a rule's structure?
A condition/pattern and an associated response; ours stores each as a pair.
Q7. Why preprocess input?
To make matching less sensitive to capital letters, punctuation and repeated spaces.
Q8. What does `\b` do?
It represents a word boundary, helping match complete words instead of substrings.
Q9. What are capture groups?
Pattern portions that store matched text for later use, such as inserting a user's name into a reply.
Q10. What if no pattern matches?
The program gives a fallback response explaining its limited topic coverage.
Q11. Why does rule order matter?
The first matching rule wins, so broad rules could hide more specific ones if placed earlier.
Q12. How does it stop?
re.fullmatch recognises bye, goodbye, exit or quit as the complete normalised message.
Q13. What is its response-time complexity?
A useful rough estimate is O(R*L) for R simple rules on input length L. Regex complexity depends on the patterns; this is not a universal guarantee for arbitrary regexes.
Q14. What was ELIZA?
An early chatbot that generated conversational replies using pattern matching and substitution rules.
Q15. Rule-based versus machine-learning chatbot?
Rules are explicitly programmed; an ML system learns patterns from data and may generalise to new wording.
Q16. What is the Turing Test?
An evaluation of whether an evaluator can distinguish a machine's conversational responses from a human's under the test's conditions.
Q17. What are this chatbot's limitations?
Limited rules, no learned understanding, no persistent conversational memory and weak handling of unanticipated wording.
Q18. How could it remember the user's name?
Store the captured name in a session dictionary and consult it when later questions refer to the name.
Q19. How can it be improved?
Add focused rules, synonyms, contextual state or a learned intent classifier, and test conflicting patterns.
Q20. Give applications.
Small FAQ systems, college enquiry assistants and simple support menus.

Practical Exam Variations & Edge Cases

Common Examiner Test Cases & Code Tweaks:
  • Difference between re.search, re.match and re.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.
Comprehensive Revision Algorithm Benchmarking General Python Viva

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:

Q1. List versus tuple?
A list can be changed; a tuple cannot. Tuples containing hashable values can be dictionary keys or set elements.
Q2. Why use a set?
For unique elements and efficient membership tests, typically O(1) average time.
Q3. Why use a dictionary?
To associate states with parents/costs or labels with values; lookup is typically O(1) average time.
Q4. What does `yield` do?
It returns the next item from a generator while preserving the function's state for later iteration.
Q5. What does `return None` mean?
The function returns Python's absence value. In these searches it often signals no solution.
Q6. Why distinguish `None` from an empty list?
An empty path or collection can sometimes be a valid result; explicitly checking is None avoids confusing it with failure.
Q7. What does `if __name__ == "__main__"` do?
It runs the demonstration only when the file is executed directly, allowing functions to be imported without starting the demo.
Q8. What is a base case?
The condition that ends recursion, such as all rows assigned or depth zero.
Q9. What is a shallow copy?
A new outer container that still refers to nested objects. For a grid, copying each row separately is needed when rows will be modified.
Q10. Why avoid `[[0]*9]*9` for an editable Sudoku?
It repeats references to the same row. A change in one row can appear in all rows. Use a comprehension to create separate rows.
Q11. What does `[::-1]` do?
It returns a reversed sequence; parent reconstruction uses it to put a goal-to-start trace into start-to-goal order.
Q12. What is a priority queue?
A structure that removes the item with the best priority, not necessarily the oldest or newest item.
Q13. What are completeness and optimality?
Completeness means finding a solution if one exists under stated assumptions; optimality means returning a best-cost solution.
Q14. What is a branching factor?
The number of successors per state, or an upper/average value used in search analysis.
Q15. What is the difference between a state and a node?
A state describes the world; a search node may additionally store a path, cost, parent and action. Several search nodes can represent the same state.

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 deque is used instead of list.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.