ARTIFICIAL INTELLIGENCE

Comprehensive Lecture Notes — Unit I

COMPLETE SYLLABUS COVERAGE

Introduction to AI | General Problem Solving | Characteristics of Problems

State Space Search | Exhaustive Searches | Heuristic Search Techniques

Iterative Deepening | Constraint Satisfaction Problems

Sources: AIMA — Russell & Norvig (4th Ed.) | Luger — AI Structures & Strategies (6th Ed.)

SYLLABUS TOPIC COVERAGE CHECKLIST

Syllabus Topic Module Coverage Status

Introduction to AI Module 1 ✅ Complete
General Problem Solving (GPS, Module 2 ✅ Complete
Means-Ends)
Characteristics of Problems Module 3 ✅ Complete
State Space Search (Formal Module 4 ✅ Complete
Definition)
Exhaustive Searches (Generate- Module 5 ✅ Complete
and-Test, British Museum)
Heuristic Search Techniques (Hill Module 6 ✅ Complete
Climbing, Beam, Best-First, A*)
Iterative Deepening (IDDFS, IDA*) Module 7 ✅ Complete
Constraint Satisfaction Problems Module 8 ✅ Complete
(CSP)

MODULE 1: INTRODUCTION TO ARTIFICIAL

INTELLIGENCE
1.1 What is Artificial Intelligence?
Artificial Intelligence is the science and engineering of creating machines that can perceive, reason,
learn, and act in ways that humans would consider intelligent. AI encompasses building agents that
sense their environment and take actions to maximize their chances of achieving their goals.

Definition (Russell & Norvig, 2021)

AI is the study of agents that receive percepts from the environment and perform actions.
Each agent implements a function that maps percept sequences to actions.

AI currently encompasses: learning, reasoning, perception, language understanding,

game playing, theorem proving, robotics, medical diagnosis, and much more.

1.2 Four Approaches to AI

AI research has pursued four distinct perspectives based on two dimensions: human vs. rational, and
thought vs. behavior:

Approach Goal Key Idea Example

Acting Humanly Pass Turing Test Imitate human behavior ELIZA, ChatGPT
Thinking Humanly Cognitive modelling Understand human GPS (Newell & Simon)
thought
Thinking Rationally Laws of thought Logic-based reasoning Expert systems
Acting Rationally Rational agent Best expected outcome AlphaGo, Self-driving cars

1.2.1 The Turing Test (1950)

Proposed by Alan Turing as a test of machine intelligence: a computer passes if a human interrogator
cannot distinguish it from a human after a text-based conversation.

Six capabilities required to pass the Turing Test:

● Natural Language Processing — communicate in human language
● Knowledge Representation — store knowledge about the world
● Automated Reasoning — draw conclusions and answer questions
● Machine Learning — adapt to new circumstances and detect patterns
● Computer Vision — perceive and interpret the visual world
● Robotics — manipulate objects and move in the world

📌 EXAMPLE: ELIZA (1966) — Turing Test Simulation

ELIZA, developed by Joseph Weizenbaum, simulated a psychotherapist using simple
pattern matching and scripted responses. Many users were convinced they were talking
to a real human — an informal passing of the Turing Test.
 Modern LLMs (GPT-4, Claude) routinely pass Turing Test scenarios but achieve this
through statistical pattern matching, not genuine understanding.

1.2.2 The Rational Agent Approach

The dominant paradigm in modern AI. An agent perceives its environment and takes actions to
maximize its performance measure. This is more general than human imitation — it doesn't require
human-like behavior, just effective behavior.

⚡ KEY POINT: Rational Agent

AGENT = ARCHITECTURE + PROGRAM
Architecture: Physical or software sensors and actuators
Program: The AI function mapping percepts → actions

A RATIONAL AGENT selects actions that maximize its EXPECTED PERFORMANCE MEASURE
given its knowledge, percepts, and computational resources.

1.3 Task Environments — PEAS Framework

Before designing an AI agent, specify the task environment using PEAS:

P — Performance How success is measured: safety, speed, legality, comfort

E — Environment Context where agent operates: roads, weather, other agents

A — Actuators Output mechanisms: steering, accelerator, brake, horn

S — Sensors Input mechanisms: cameras, LIDAR, radar, GPS, speedometer

📌 EXAMPLE: PEAS for Medical Diagnosis AI

Performance: Correct diagnosis rate, minimizing false positives/negatives
Environment: Patient records, symptoms, lab results, medical literature
Actuators: Output: diagnosis report, treatment recommendations
Sensors: Input: patient history, test results, imaging data

1.4 History of AI — Key Milestones

● 1943 McCulloch & Pitts: First neural network model
● 1950 Alan Turing: 'Computing Machinery and Intelligence'; Turing Test proposed
● 1956 Dartmouth Conference: John McCarthy coins 'Artificial Intelligence'
 ● 1957 Newell & Simon: General Problem Solver (GPS)
● 1966 ELIZA: First chatbot; first AI winter begins late 1960s
● 1972–79 MYCIN, DENDRAL: Expert systems era begins
● 1997 Deep Blue defeats Kasparov at chess
● 2012 AlexNet: Deep learning revolution begins
● 2017 AlphaZero: Self-learning game AI
● 2020s Large Language Models: GPT, Claude, Gemini dominate

MODULE 2: GENERAL PROBLEM SOLVING

2.1 What is Problem Solving in AI?

Problem solving in AI refers to finding a sequence of actions (a solution path) that transforms an initial
state into a desired goal state. AI problem solving borrows from human reasoning strategies and
formalizes them into systematic algorithms.

Key Questions in AI Problem Solving (Luger)

1. Is the problem solver guaranteed to find a solution?
2. Will it always terminate? Can it get stuck in infinite loops?
3. When a solution is found, is it guaranteed to be optimal?
4. What is the complexity in terms of time usage? Memory usage?
5. How can the interpreter most effectively reduce search complexity?

2.2 The General Problem Solver (GPS)

Developed by Allen Newell and Herbert Simon (1957), GPS was a landmark AI program that separated
general problem-solving strategy from domain-specific knowledge. GPS demonstrated that intelligence
could arise from a simple, general mechanism applied to diverse problems.

2.2.1 Means-Ends Analysis

The core mechanism of GPS is Means-Ends Analysis — comparing the current state to the goal state
and selecting actions that reduce the difference between them.

📖 DEFINITION: Means-Ends Analysis

A problem-solving technique that:
1. Compares current state to goal state
2. Identifies the most important DIFFERENCE
3. Selects an OPERATOR (action) that reduces that difference
4. If an operator has unsatisfied preconditions, sets them as sub-goals
 5. Recursively applies means-ends analysis to achieve sub-goals
6. Repeats until goal is reached or no operators are applicable

📌 EXAMPLE: Means-Ends Analysis: Driving to the Airport

Goal State: I am at the airport
Current State: I am at home, need to travel

Step 1: Identify difference → I am not at the airport

Step 2: Find operator that changes location → 'Drive car'
Step 3: Precondition: 'Car is here' — satisfied ✓
Precondition: 'I am in the car' — NOT satisfied ✗
Step 4: Sub-goal: 'Get into the car'
Apply operator 'Walk to car and open door'
Step 5: Drive to airport → Goal achieved ✓

This recursive sub-goal structure is the essence of means-ends analysis.

2.2.2 GPS Algorithm

function GPS(current_state, goal_state, operators):
if current_state == goal_state: return SUCCESS
diff = find_difference(current_state, goal_state)
op = select_operator(operators, diff)
if op == None: return FAIL
for precond in [Link]:
if not satisfied(precond, current_state):
result = GPS(current_state, precond, operators) # subgoal
if result == FAIL: return FAIL
new_state = apply(op, current_state)
return GPS(new_state, goal_state, operators)

2.2.3 Problem Reduction

Problem Reduction decomposes a complex problem into simpler sub-problems. This is the foundation
of divide-and-conquer strategies and AND-OR tree search.

● AND node — All sub-problems must be solved (conjunction)

● OR node — Any ONE of the alternatives solves the problem
● Leaf nodes — Primitive problems that can be solved directly

📌 EXAMPLE: Problem Reduction: Prove Theorem T

Goal: Prove Theorem T
OR branches: Use Method A | Use Method B | Use Method C

Method A requires proving Lemma 1 AND Lemma 2 (AND node)

→ Lemma 1: directly provable (leaf node) ✓
 → Lemma 2: requires proving Lemma 2a AND Lemma 2b (AND node)

This AND-OR tree guides the proof search efficiently.

AO* algorithm searches AND-OR trees optimally.

2.3 Forward vs Backward Reasoning

Aspect Forward Chaining (Data-Driven) Backward Chaining (Goal-
Driven)
Direction Start → Goal Goal → Start
Approach Apply rules to known facts Work back from goal to facts
Best when All data given, many goals Clear goal, few data sources
Also called Bottom-up reasoning Top-down reasoning
Example DENDRAL: data to structure MYCIN: disease to symptoms
AI Use Production systems, planning Logic programming, diagnosis

🔍 CASE STUDY: GPS Applied to Symbolic Logic

Newell & Simon used GPS to prove theorems in propositional logic.

PROBLEM: Prove: (P → Q) from premises {P, (P → R), (R → Q)}

GPS Approach (Means-Ends):

Current state: {P, P→R, R→Q}
Goal state: {P→Q}
Difference: P→Q not in current state
Operator: Modus Ponens (if A and A→B, derive B)

Apply P and P→R → derive R

Apply R and R→Q → derive Q
Build P→Q from derivation chain

GPS successfully completed this proof and compared its steps to

those taken by human subjects solving the same problem.

MODULE 3: CHARACTERISTICS OF PROBLEMS

Before choosing a search strategy, an AI designer must analyze the problem's characteristics. These
properties determine which algorithms and representations are appropriate. Luger identifies several key
dimensions along which problems vary:
3.1 Is the Problem Decomposable?
The problem can be broken into independent or semi-independent sub-
Decomposable
problems

● YES — Decomposable → Use problem reduction; AND-OR trees; divide and conquer
● NO — Non-decomposable → Must treat as a single monolithic search problem

📌 EXAMPLE: Decomposability Examples

DECOMPOSABLE: Integrate ∫(x² + sin(x))dx
→ ∫x²dx + ∫sin(x)dx — each part solved independently

DECOMPOSABLE: Tower of Hanoi (n disks → solve n-1 disks first)

NOT DECOMPOSABLE: Chess — the whole board must be considered together;

individual piece movements cannot be solved independently.

3.2 Can Solution Steps Be Ignored or Undone?

This characteristic concerns the REVERSIBILITY of actions taken during problem solving.

3.2.1 Ignorable (Recoverable) Steps

Steps can be undone if they lead to a dead-end — full backtracking
Ignorable
possible

When steps are ignorable, the problem solver can use simple backtracking and explore multiple paths
freely. This is the ideal case — mistakes can always be corrected.

📌 EXAMPLE: Ignorable Steps: Theorem Proving

In propositional logic theorem proving, if applying modus ponens leads to
a dead-end, we can simply ignore that step and try a different inference rule.
The state of our axioms is unchanged — we haven't 'committed' to anything.

3.2.2 Recoverable Steps

Steps can be undone, but recovery requires additional effort and
Recoverable
backtracking

Most game-playing problems have this characteristic. A chess move can be 'taken back' during search,
but the algorithm must maintain the game state carefully.
 📌 EXAMPLE: Recoverable: 8-Puzzle
Moving tile 3 to the right is a recoverable step — we can move it back left.
However, this uses additional moves and time. The search tree must track
all explored paths to avoid cycles and redundant work.

3.2.3 Irrecoverable Steps

Steps cannot be undone — problem solver must make good choices the
Irrecoverable
first time

When actions cannot be undone, the problem solver must use planning and commit to decisions
carefully. Backtracking is not an option — the physical world has already changed.

📌 EXAMPLE: Irrecoverable: Robot Surgery / Chemical Mixing

Once a surgical cut is made, it cannot be 'undone.' The robot must plan
carefully before acting. Once chemicals are mixed, the reaction proceeds.

Solution: Use planning (looking ahead) rather than trial-and-error search.

Best-first and heuristic searches are preferred for irrecoverable problems.

3.3 Is the Goal Fully Specified?

Goal Type Description Example Search Approach
Single Goal One specific target state Bucharest (route finding) Standard search
Multiple Goals Any of several states Any solved Rubik's Cube Set of goal tests
acceptable state
Property Goal Goal defined by a property 'No queen attacks another' Constraint checking
Path Goal The path itself is the goal Salesperson's tour route Path optimization

3.4 What Type of Solution is Required?

3.4.1 Any Solution (Satisficing)
The problem solver accepts the FIRST valid solution found, regardless of quality. Used when any
correct answer is acceptable and finding it quickly is paramount.
● Example → Finding any valid coloring of a map
● Algorithms → DFS, Backtracking (find first solution)

3.4.2 Best Solution (Optimal)

The problem solver must find the OPTIMAL (minimum cost, maximum quality) solution among all valid
solutions.
 ● Example → Shortest route from Arad to Bucharest
● Algorithms → A*, UCS, BFS (for uniform costs)

3.4.3 All Solutions

The problem solver must enumerate EVERY valid solution. Used in some combinatorics and constraint
satisfaction problems.
● Example → All ways to color a map with 3 colors
● Algorithms → Complete backtracking search with no pruning on found solutions

3.5 What Knowledge is Required?

Knowledge Level Description Impact on Search Example
Fully Known Complete and correct Standard algorithms apply Chess rules
model
Partially Known Incomplete information Must handle uncertainty Poker (hidden cards)
Unknown Environment not Must explore to learn Robot in new room
understood
Adversarial Opponent acts to counter Game-tree search Chess, Go
(minimax)

3.6 What is the Problem Space Complexity?

The complexity of the problem space determines which search strategy is feasible:

● Branching factor b — Average number of children per node

● Depth d — Depth of shallowest goal node
● Maximum depth m — Longest possible path
● Total states = b^d — grows exponentially with depth

Combinatorial Explosion
Chess: ~10¹²⁰ possible game states (Shannon Number)
Go: ~10¹⁷² possible game states
8-Puzzle: 181,440 reachable states (manageable)
15-Puzzle: ~10¹² states (requires heuristics)

Branching Factor Formula: T = B + B² + B³ + ... + Bᴸ = B(Bᴸ - 1)/(B-1)

B = branching factor, L = path length, T = total states

Lesson: Even small reductions in branching factor have dramatic effects!

Reducing B from 2.0 to 1.5 doubles the searchable path length.

🔍 CASE STUDY: Problem Characteristic Analysis: Route Finding

 Problem: Find shortest route from Chennai to Mumbai

Decomposable? Partially — can decompose into city-to-city legs

Steps ignorable? YES — road choices can be reconsidered (backtrack freely)
Goal specified? SINGLE — Mumbai is the unique target
Solution type? OPTIMAL — shortest distance required
Knowledge? FULLY KNOWN — road map is complete
Space complexity? ~Millions of intersections, manageable with A*

Recommendation: A* with straight-line distance heuristic

This analysis directly informs the algorithm choice!

MODULE 4: STATE SPACE SEARCH — FORMAL

FRAMEWORK

4.1 State Space Representation

A state space is a mathematical model for representing a problem and its solutions. By representing
problems as graphs, we can use graph theory to analyze complexity and design algorithms.

📖 DEFINITION: State Space [N, A, S, GD] — Luger

N — Set of NODES representing all possible problem states
A — Set of ARCS (operators/moves) connecting states
S — START STATE — the initial state from which search begins
GD — GOAL DESCRIPTION — specifies goal states or a goal property

A solution is a PATH from S to a node that satisfies GD.

4.2 Formal Problem Definition — Five Components (AIMA)

State Space Set of all possible world states the environment can be in

Initial State The state the agent starts in: e.g., Arad

Goal State(s) IS-GOAL(state): one state, set of states, or a property

Actions ACTIONS(s): set of actions applicable in state s

Transition Model RESULT(s,a): state resulting from action a in state s

 Action Cost ACTION-COST(s,a,s'): numeric cost of action a from s to s'

📌 EXAMPLE: Romania Problem — Full Formalization

State Space: All 20 Romanian cities
Initial State: Arad
Goal State: Bucharest (IS-GOAL returns true only for Bucharest)
Actions: ACTIONS(Arad) = {ToSibiu, ToTimisoara, ToZerind}
Transition: RESULT(Arad, ToZerind) = Zerind
Action Cost: ACTION-COST(Arad, ToZerind, Zerind) = 75 (km)

Optimal solution path: Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest = 418 km

4.3 Key Graph Theory Concepts

Term Definition Relevance to Search
Node A state or configuration Each city, board position, etc.
Arc Directed connection between nodes An action/move
Path Ordered sequence of connected A solution candidate
nodes
Tree Graph with unique path between DFS/BFS search structure
nodes
DAG Directed Acyclic Graph — no cycles Tic-tac-toe state space
Cycle Path that returns to a starting node Causes infinite loops in search
Frontier Set of nodes generated but not Active search boundary
expanded
Branching Factor Average children per node Determines complexity

4.4 State Space vs. Search Tree

Critical Distinction
STATE SPACE GRAPH:
→ Describes all possible PROBLEM STATES and transitions
→ May contain cycles and multiple paths to same state
→ Finite or infinite set of real-world configurations

SEARCH TREE:
→ Generated by the algorithm DURING search
→ Each node = one state reached via a specific path
→ Multiple tree nodes may correspond to the SAME state
→ The root is the initial state; leaves are unexplored states

KEY: The state space is the PROBLEM; the search tree is the ALGORITHM'S WORK.
4.5 Classic Problems — State Space Analysis
4.5.1 The 8-Puzzle
● States 9 tiles in a 3×3 grid (one blank) — 362,880 total but only 181,440 reachable
● Actions Move blank: UP, DOWN, LEFT, RIGHT
● Goal Tiles in specified ordered configuration
● Optimal heuristic Manhattan distance — sum of tile distances from goal

8-Puzzle State Diagram

Start State: Goal State:
┌───┬───┬───┐ ┌───┬───┬───┐
│2│8│3│ │1│2│3│
├───┼───┼───┤ → ├───┼───┼───┤
│1│6│4│ │4│5│6│
├───┼───┼───┤ ├───┼───┼───┤
│7│ │5│ │7│8│ │
└───┴───┴───┘ └───┴───┴───┘

Available moves from blank position (center-bottom):

← Move 5 right | → Move 7 left | ↑ Move 6 down

4.5.2 Traveling Salesperson Problem (TSP)

● States Set of cities visited, current city
● Actions Travel to any unvisited city
● Goal Visit all cities, return home, minimize total distance
● Complexity (n-1)!/2 routes — NP-hard — requires heuristics for large n

4.5.3 Missionaries and Cannibals

● States (m, c, b) — missionaries and cannibals on starting bank, plus boat position
● Constraint Cannibals must never outnumber missionaries on either bank
● Goal All missionaries and cannibals safely on the other side
● State space Small and manageable with BFS

MODULE 5: EXHAUSTIVE SEARCH STRATEGIES

Exhaustive (blind/uninformed) search strategies explore the state space systematically without using
any domain knowledge about how close a state is to the goal. They are guaranteed to find a solution (if
one exists) but may be impractical for large state spaces.
5.1 Generate-and-Test Strategy

📖 DEFINITION: Generate-and-Test
The simplest possible search strategy:
1. GENERATE a possible solution (candidate state or path)
2. TEST whether it satisfies the goal
3. If YES → return solution
4. If NO → generate next candidate and repeat

This is essentially exhaustive enumeration of the search space.

function generate_and_test(problem):
for each possible solution s in GENERATE(problem):
if TEST(s, [Link]):
return s # solution found
return FAIL # all candidates exhausted

The key design decisions in Generate-and-Test:

● Generator quality — Should produce legal, non-redundant candidates
● Test efficiency — Should quickly reject invalid candidates
● Completeness — Generator must be systematic to guarantee finding a solution

📌 EXAMPLE: Generate-and-Test: N-Queens

Problem: Place 8 queens on a chessboard with no conflicts

NAIVE Generator: Generate all 64C8 = 4.4 billion board arrangements

Test: Check if any two queens attack each other

SMART Generator: Generate one queen per column (satisfies column constraint)
Test: Check row and diagonal conflicts only
→ Reduces to 8^8 = 16 million candidates to test

SMARTER Generator: Only generate non-attacking column positions

→ Only 2,057 candidates actually tested (6 orders of magnitude improvement!)

Lesson: The generator quality determines the practical feasibility.

5.2 The British Museum Algorithm

📖 DEFINITION: British Museum Algorithm

A metaphorical name for completely random or unsystematic exhaustive search.
Named after the idea that a monkey randomly typing at a typewriter would
eventually produce all the books in the British Museum (given infinite time).
 Properties:
→ Generates solutions randomly without any systematic ordering
→ Theoretically complete (will find solution eventually)
→ Practically useless for all but trivial problems
→ Serves as a baseline to compare other algorithms against

Also called: Random Search, Blind Search

📌 EXAMPLE: British Museum Algorithm Illustration

Problem: Solve an 8-puzzle (181,440 reachable states)

British Museum approach: Randomly pick any move at each step

→ Expected moves to find solution: hundreds of millions
→ BFS approach: At most 181,440 states examined

British Museum approach is useful only to understand why we NEED

better strategies — it establishes the worst-case baseline.

5.3 Breadth-First Search (BFS)

BFS systematically explores all states at depth d before exploring depth d+1. It uses a FIFO queue,
guaranteeing it finds the shallowest solution.

function breadth_first_search(problem):
open := [start_state] # FIFO queue
closed := []
while open ≠ []:
X := remove_leftmost(open) # DEQUEUE
if IS-GOAL(X): return path_to(X)
generate children of X
put X on closed
discard children already on open or closed # loop check
add remaining children to RIGHT of open # BFS ordering
return FAIL

BFS Trace: Graph A→U (Goal=U)

1. open=[A]; closed=[]
2. open=[B,C,D]; closed=[A]
3. open=[C,D,E,F]; closed=[B,A]
4. open=[D,E,F,G,H]; closed=[C,B,A]
5. open=[E,F,G,H,I,J]; closed=[D,C,B,A]
...continues until U is found at the appropriate level

PROPERTY: Every node at depth d is visited BEFORE any node at depth d+1
RESULT: BFS always finds the SHORTEST PATH to the goal.
 ● Complete? ✅ Yes
● Optimal? ✅ Yes (uniform step costs)
● Time: O(bᵈ)
● Space: O(bᵈ) — stores ALL frontier nodes

5.4 Depth-First Search (DFS)

DFS explores one path as deeply as possible before backtracking. Uses a LIFO stack, making it very
memory-efficient.

function depth_first_search(problem):
open := [start_state] # LIFO stack
closed := []
while open ≠ []:
X := remove_leftmost(open) # POP from stack
if IS-GOAL(X): return path_to(X)
generate children of X
put X on closed
discard children already on open or closed
add remaining children to LEFT of open # DFS ordering
return FAIL

● Complete? ❌ No (may loop in infinite spaces without cycle detection)

● Optimal? ❌ No (first solution found may not be cheapest)
● Time: O(bᵐ)
● Space: O(b×m) — MUCH better than BFS

5.5 Backtracking Search

A refined version of DFS that generates ONE child at a time (not all children at once), making it even
more memory-efficient. When a dead-end is reached, it backtracks and tries the next unexplored
option.

Backtrack Algorithm — Key Lists

SL (Solution List): States on the current solution path (from start to CS)
NSL (New State List): States generated but not yet explored
DE (Dead Ends): States that led to failure
CS (Current State): The state currently being explored

When CS has no unvisited children: remove CS from SL (backtrack)

When a goal is found: SL contains the solution path

📌 EXAMPLE: Backtrack Trace

Graph: A→{B,C,D}, B→{E,F}, E→{H,I}, F→{J}, C→{G}
 Goal: G

Initialize: SL=[A]; NSL=[A]; DE=[]

Iter 1: CS=A → expand → children B,C,D; SL=[B,A]
Iter 2: CS=B → expand → children E,F; SL=[E,B,A]
Iter 3: CS=E → expand → children H,I; SL=[H,E,B,A]
Iter 4: CS=H → no children → DE=[H]; backtrack → SL=[E,B,A]
Iter 5: CS=I → no children → DE=[I,H]; backtrack → SL=[B,A]
Iter 6: CS=F → CS=J → no children; backtrack → SL=[A]
Iter 7: CS=C → CS=G → IS-GOAL(G)=TRUE!
Solution path: SL = [G, C, A] → A→C→G ✓

5.6 Depth-Limited Search

DFS with a maximum depth limit ℓ. Avoids infinite loops in infinite state spaces by refusing to explore
beyond depth ℓ.

● Returns FAILURE when no solution found within limit

● Returns CUTOFF when depth limit was reached (may have solution deeper)
● Use case when approximate depth of solution is known

5.7 Uniform-Cost Search (Dijkstra's Algorithm)

Extends BFS for variable action costs. Always expands the node with the lowest cumulative path cost
g(n). Equivalent to Dijkstra's shortest-path algorithm.

function uniform_cost_search(problem):
frontier := priority_queue ordered by g(n)
[Link](start, g=0)
reached := {start: 0}
while frontier not empty:
node := [Link]() # lowest g(n) first
if IS-GOAL(node): return node
for child in EXPAND(node):
if child not in reached or child.g < reached[child]:
reached[child] = child.g
[Link](child)
return FAIL

● Complete? ✅ Yes
● Optimal? ✅ Yes — always finds cheapest path
● Time/Space: O(b^(1+⌊C*/ε⌋)) — can be worse than BFS for many cheap steps
5.8 Comparison of Exhaustive Search Algorithms
Algorithm Complete? Optimal? Time Space Queue Type
BFS ✅ Yes ✅ Yes* O(bᵈ) O(bᵈ) FIFO
DFS ❌ No† ❌ No O(bᵐ) O(b·m) LIFO/Stack
Backtracking ❌ No† ❌ No O(bᵐ) O(m) Stack+lists
Depth-Limited ❌ No‡ ❌ No O(bˡ) O(b·l) Stack
Uniform-Cost ✅ Yes ✅ Yes O(b^C*) O(b^C*) Priority Queue
Bidirectional ✅ Yes ✅ Yes O(b^(d/2)) O(b^(d/2)) Two queues

* Optimal when all step costs are equal. † Complete for finite acyclic spaces. ‡ Complete only if ℓ ≥ d

MODULE 6: HEURISTIC SEARCH TECHNIQUES

Heuristic search uses domain-specific knowledge to guide the search toward the goal more efficiently
than exhaustive strategies. A heuristic is an estimate — an informed guess — of how close a state is to
the goal.

📖 DEFINITION: Heuristic Function h(n)

h(n) = estimated cost from node n to the nearest goal state

A GOOD heuristic:
→ Is fast to compute
→ Never overestimates the true cost (admissible)
→ Guides search quickly toward the goal
→ Reduces the number of states explored

6.1 Why Heuristics are Needed

Two main reasons why exact algorithms fail and heuristics become necessary (Luger):

● No exact solution — Some problems (medical diagnosis, vision) have no exact answer.
Heuristics find the most likely or most useful answer.
● Combinatorial explosion — State spaces grow exponentially. Chess has 10¹²⁰ states;
exhaustive search requires heuristic pruning to be feasible.

Impact of Heuristics on Tic-Tac-Toe

EXHAUSTIVE SEARCH: 9! = 362,880 paths

SYMMETRY REDUCTION: Only 3 first moves (corner, center, side edge)

→ Reduces to ~12 × 7! paths
 HEURISTIC ('take state with most winning opportunities'):
→ X always takes center on first move
→ Only a handful of states evaluated per turn
→ Reduction of FOUR ORDERS OF MAGNITUDE over exhaustive search

Lesson: A simple heuristic can make an intractable problem trivially easy.

6.2 Hill Climbing

📖 DEFINITION: Hill Climbing

The simplest heuristic search strategy. Like climbing a hill — always move
in the direction that improves the heuristic value most steeply.

Algorithm: At each step, evaluate ALL children of current state.

Move to the child with the BEST heuristic value.
Retain NO history — cannot backtrack.

Named for the strategy of a blind mountaineer: always go uphill.

function hill_climbing(problem):
current := start_state
while True:
children := generate_children(current)
best := argmax(h(child) for child in children)
if h(best) <= h(current): # no improvement
return current # local maximum
current := best

6.2.1 Problems with Simple Hill Climbing

Problem Description Example Solution
Local Maximum State better than all 8-puzzle plateau Random restart
neighbors but not global
best
Plateau Flat area where all Many h-value ties Sideways moves
neighbors have equal
value
Ridge Long gentle slope, difficult Diagonal maze Backtracking
to traverse
No backtracking Cannot recover from bad Any dead end Simulated annealing
choices

6.2.2 Variants of Hill Climbing

Simple Hill Climbing
Move to the FIRST child that is better than the current state (not necessarily the best child). Faster per
step, but may miss better options.

Steepest Ascent (Gradient Ascent) Hill Climbing

Evaluate ALL children, move to the BEST child. More thorough per step, more expensive.

Stochastic Hill Climbing

Choose randomly from children that are better than the current state. Balances exploration with
improvement.

Random-Restart Hill Climbing

When stuck at a local maximum, restart from a randomly chosen state. With enough restarts, finds the
global maximum with high probability.

📌 EXAMPLE: Hill Climbing on the 8-Puzzle

Heuristic: h(n) = number of tiles out of place (lower is better)

Start state h=5 → evaluate children:

Child A: h=4 (better) ← move here
Child B: h=6 (worse) skip
Child C: h=5 (same) skip

From h=4 → children: h=3 (move) → h=2 (move) → h=0 (GOAL!) ✓

BUT sometimes: h=4 → all children have h≥4 → LOCAL MAXIMUM!

Solution: Random restart from a new initial state.

6.3 Simulated Annealing

📖 DEFINITION: Simulated Annealing

Inspired by the annealing process in metallurgy — heating then slowly cooling
metals to reduce defects. In AI, it allows occasional uphill moves to escape
local maxima, with the probability of uphill moves decreasing over time.

Temperature T controls the probability of accepting worse states:

P(accept worse state) = e^(-ΔE/T)
High T → accept many worse states (exploration)
Low T → rarely accept worse states (exploitation)

As T → 0, simulated annealing converges to simple hill climbing.

function simulated_annealing(problem, schedule):

current := start_state
 for t = 1 to ∞:
T := schedule(t) # decreasing temperature
if T == 0: return current
next := random_child(current)
ΔE := h(next) - h(current) # change in heuristic value
if ΔE > 0: # next is better
current := next
else: # next is worse
current := next with probability e^(ΔE/T)

● Complete? ✅ Yes (probabilistically, given enough time)

● Optimal? ✅ Yes (with slow enough cooling schedule)
● Use case → Chip design, scheduling, combinatorial optimization

6.4 Beam Search

📖 DEFINITION: Beam Search

A memory-bounded version of BFS that keeps only the k BEST states at
each level of the search (the 'beam width' = k).

At each level: generate all children of all k states.

Select only the k BEST children (by heuristic value).
Discard all others.

Beam width k controls the space-quality tradeoff:

k=1 → Greedy hill climbing
k=∞ → Full BFS

● Complete? ❌ No — may prune the correct path

● Optimal? ❌ No — may miss better solutions
● Space: O(k×b) — very efficient
● Practical use → Machine translation, speech recognition, neural decoding

📌 EXAMPLE: Beam Search with k=2

Level 0: [A(h=10)]
Level 1: Expand A → [B(h=8), C(h=6), D(h=9)]
Keep best 2: [B(h=8), C(h=6)] ← discard D
Level 2: Expand B → [E(h=5), F(h=7)]
Expand C → [G(h=3), H(h=4)]
All children: [E(5), F(7), G(3), H(4)]
Keep best 2: [G(h=3), E(h=5)] ← discard F and H
Level 3: Expand G and E ... continues

Beam search focuses resources on the most promising paths.

6.5 Best-First Search

📖 DEFINITION: Best-First Search

A generalization of BFS/DFS that uses a PRIORITY QUEUE to always expand
the node with the best heuristic value, regardless of depth.

Unlike Hill Climbing: maintains open and closed lists → can backtrack
Unlike BFS: uses heuristic to order the frontier

Algorithm A: f(n) = g(n) + h(n) (AIMA terminology for best-first with A*)
Greedy Best-First: f(n) = h(n) only (ignores cost so far)

function best_first_search(problem):
open := priority_queue ordered by h(n)
closed := []
[Link](start_state)
while open ≠ []:
X := open.remove_best() # lowest h(n) first
if IS-GOAL(X): return X
for child in generate_children(X):
if child not on open or closed:
assign heuristic h(child)
[Link](child)
elif child on open with longer path:
update child with shorter path
elif child on closed with longer path:
move child back to open
[Link](X)
sort open by heuristic merit (best first)
return FAIL

● Complete? ✅ Yes (with cycle detection)

● Optimal? ✅ Yes with admissible h(n) (→ this gives A*)

6.6 A* Search — The Gold Standard

A* (pronounced 'A star') is the most widely used informed search algorithm. It combines the actual cost
so far (g(n)) with the heuristic estimate (h(n)) to evaluate nodes.

A* Evaluation Function
f(n) = g(n) + h(n)

f(n): Estimated total cost of best solution through node n

g(n): Actual cost from start state to node n
h(n): Heuristic estimate of cost from n to goal

A* expands nodes in order of increasing f(n) using a PRIORITY QUEUE.

6.6.1 Admissibility — Key to Optimality

📖 DEFINITION: Admissible Heuristic

h(n) is ADMISSIBLE if: h(n) ≤ h*(n) for all nodes n
where h*(n) is the TRUE optimal cost from n to goal.

An admissible heuristic NEVER OVERESTIMATES — it is OPTIMISTIC.

THEOREM: If h(n) is admissible, A* is COST-OPTIMAL.

A* with admissible h always finds the least-cost solution.

📌 EXAMPLE: Admissible Heuristics for 8-Puzzle

h₁: Number of MISPLACED TILES
→ Admissible because each misplaced tile needs AT LEAST 1 move
→ Never overestimates

h₂: MANHATTAN DISTANCE (sum of distances each tile is from goal position)
→ h₂ = |row_current - row_goal| + |col_current - col_goal| for each tile
→ Admissible because each tile needs at least Manhattan distance moves
→ h₂ DOMINATES h₁: h₂(n) ≥ h₁(n) for all n
→ More informed → explores fewer states → more efficient

hSLD for Romania: Straight-line distance to Bucharest

→ Admissible because actual road distance ≥ straight-line distance

6.6.2 Consistency (Monotonicity)

📖 DEFINITION: Consistent Heuristic

h(n) is CONSISTENT if for every node n and successor n' via action a:
h(n) ≤ c(n, a, n') + h(n')

This is the TRIANGLE INEQUALITY:

The direct estimate can never exceed the step cost + successor estimate.

If h is consistent → h is admissible (but not vice versa)

If h is consistent → A* with graph search is optimal
If h is consistent → f(n) is non-decreasing along any path

📌 EXAMPLE: A* Trace: Romania Arad → Bucharest

f(n) = g(n) + h(n), h = straight-line distance to Bucharest

(a) Expand Arad(f=0+366=366):

Frontier: Sibiu(f=140+253=393), Timisoara(f=118+329=447), Zerind(f=75+374=449)

(b) Expand Sibiu(f=393) — lowest f:

Add: Rimnicu Vilcea(f=220+193=413), Fagaras(f=239+176=415), Oradea(f=671)
 (c) Expand Rimnicu Vilcea(f=413):
Add: Pitesti(f=317+100=417)

(d) Expand Fagaras(f=415):

Add: Bucharest(f=450+0=450)

(e) Expand Pitesti(f=417):

Add: Bucharest(f=418+0=418) — BETTER PATH! Updates frontier.

(f) Expand Bucharest(f=418) — GOAL! ✅

Optimal Path: Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest = 418 km

Property A* with Admissible h Greedy Best-First Hill Climbing

Complete? ✅ Yes ❌ No ❌ No
Optimal? ✅ Yes ❌ No ❌ No
Time O(bᵈ) worst O(b^m) O(depth)
Space O(bᵈ) all nodes O(b^m) O(1)
Explores Optimal subspace May miss goal Single path

MODULE 7: ITERATIVE DEEPENING SEARCH

Iterative Deepening is a family of algorithms that combine the completeness and optimality of BFS with
the space efficiency of DFS. It is the preferred uninformed strategy when the solution depth is unknown.

7.1 Iterative Deepening Depth-First Search (IDDFS)

📖 DEFINITION: IDDFS
Performs depth-first search with progressively increasing depth limits:
Depth limit 1 → if not found → Depth limit 2 → if not found → ...

At each depth limit, a complete DFS is performed.

Nodes at depth d are regenerated d times in total.
Despite re-expansion, the total overhead is modest.

function iterative_deepening_search(problem):
for depth = 0 to ∞:
result := depth_limited_search(problem, depth)
if result ≠ CUTOFF:
return result # success or failure
 function depth_limited_search(problem, limit):
frontier := [NODE([Link])] # LIFO stack
result := FAILURE
while frontier not empty:
node := [Link]()
if IS-GOAL(node): return node
if DEPTH(node) > limit:
result := CUTOFF
elif not IS-CYCLE(node):
for child in EXPAND(node):
[Link](child)
return result

7.2 Why Re-expansion is Acceptable

IDDFS seems wasteful because nodes at depth d are re-expanded in each iteration. But the overhead
is actually quite small:

IDDFS Overhead Analysis

In a tree with branching factor b=10 and solution depth d:
Nodes at depth d: 10ᵈ (the vast majority)
Nodes regenerated: 10ᵈ⁻¹ + 10ᵈ⁻² + ... ≈ 10ᵈ/(b-1)
Total overhead: ≈ b/(b-1) = 10/9 ≈ 11% extra work

For b=2: Total overhead = 2/(2-1) = 2× — significant but acceptable

For b=10: Total overhead = 10/9 ≈ 11% — negligible

IDDFS time complexity: O(bᵈ)

IDDFS space complexity: O(b×d) — same as DFS!

IDDFS is the BEST UNINFORMED algorithm when depth is unknown.

7.3 Properties Comparison

Property BFS DFS IDDFS
Complete? ✅ Yes ❌ No ✅ Yes
Optimal? ✅ Yes ❌ No ✅ Yes
Time O(bᵈ) O(bᵐ) O(bᵈ)
Space O(bᵈ) O(b·m) O(b·d)
Preferred when Shallow solution Memory tight Unknown depth

7.4 Depth-First Iterative Deepening for Heuristic Search: IDA*

📖 DEFINITION: IDA* (Iterative Deepening A*)

 Combines IDDFS with A* heuristic to get:
→ A*'s optimality with admissible heuristic
→ IDDFS's space efficiency O(b×d) instead of O(bᵈ)

Instead of limiting by DEPTH, IDA* limits by f-VALUE threshold:

→ Start with threshold = h(start)
→ DFS: expand all nodes with f(n) ≤ threshold
→ If goal not found: new threshold = min f(n) that exceeded old threshold
→ Repeat until goal found

function IDA_star(problem):
threshold := h([Link])
path := [[Link]]
while True:
result := dfs_f_limited(path, 0, threshold, problem)
if IS-GOAL(result): return path
if result == ∞: return FAILURE
threshold := result # new threshold = min exceeded value

function dfs_f_limited(path, g, threshold, problem):

node := [Link]()
f := g + h(node)
if f > threshold: return f # exceeded — return for new threshold
if IS-GOAL(node): return FOUND
min_exceeded := ∞
for child in EXPAND(node):
if child not in path: # avoid cycles
[Link](child)
result := dfs_f_limited(path, g + cost(node,child), threshold, problem)
if result == FOUND: return FOUND
min_exceeded := min(min_exceeded, result)
[Link]()
return min_exceeded

● Complete? ✅ Yes
● Optimal? ✅ Yes with admissible h
● Space: O(b×d) — huge advantage over A*'s O(bᵈ)
● Preferred when A* runs out of memory

7.5 Depth-First Iterative Deepening for 8-Puzzle

📌 EXAMPLE: IDDFS on the 8-Puzzle

Branching factor: 2.67 average (2 from corners, 3 from edges, 4 from center)
Average solution depth: ~26 moves

IDA* with Manhattan Distance heuristic:

→ Threshold 0: Only start state examined
→ Threshold 4: States with f≤4 examined
→ Threshold 6: States with f≤6 examined
 → ... continues until goal found

IDA* solves random 8-puzzles examining only ~100-1000 states

BFS would require examining up to 181,440 states
Memory: IDA* uses O(d) = 26 states; A* could need thousands

MODULE 8: CONSTRAINT SATISFACTION PROBLEMS

(CSP)

Constraint Satisfaction Problems (CSPs) use a factored state representation — states are described by
a set of variables with values. A solution assigns values to all variables while satisfying all constraints.
CSPs exploit problem structure to prune huge swathes of the search space.

📖 DEFINITION: CSP — Three Components (Russell & Norvig)

X — Set of VARIABLES {X₁, X₂, ..., Xₙ}
D — Set of DOMAINS {D₁, D₂, ..., Dₙ} — allowable values for each variable
C — Set of CONSTRAINTS — allowable combinations of values

SOLUTION: A complete assignment of values to all variables that satisfies

ALL constraints simultaneously.

CONSISTENT ASSIGNMENT: Does not violate any constraint.

COMPLETE ASSIGNMENT: Every variable has been assigned a value.

8.1 Classic CSP Examples

8.1.1 Map Coloring — Australia
Assign colors to Australian states such that no two adjacent states share the same color.

● Variables X = {WA, NT, Q, NSW, V, SA, T}

● Domains D = {red, green, blue} for each variable
● Constraints SA≠WA, SA≠NT, SA≠Q, SA≠NSW, SA≠V, WA≠NT, NT≠Q, Q≠NSW, NSW≠V

📌 EXAMPLE: Map Coloring Solution

One valid solution:
WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red

Constraint graph: Each region = node; each border = edge

Key insight: SA touches FIVE other regions — highest degree node.
 The Degree Heuristic suggests assigning SA FIRST to maximize pruning.

Once SA=blue is assigned, all 5 neighbors cannot be blue.

→ 5 variables each lose 1 value from domain immediately.
CSP structure allows this bulk pruning — atomic search cannot.

8.1.2 Sudoku as CSP

● Variables 81 squares (A1–I9)
● Domains {1,2,3,4,5,6,7,8,9} for empty squares; singleton for given squares
● Constraints 27 Alldiff constraints — one per row, column, and 3×3 box

Arc consistency (AC-3) can solve many Sudoku puzzles without any search, just by propagating
constraints to eliminate values.

8.1.3 N-Queens as CSP

● Variables Q₁, Q₂, ..., Q₈ — one queen per column
● Domains {1,2,3,4,5,6,7,8} — row positions
● Constraints No two queens in same row or diagonal: Qᵢ ≠ Qⱼ and |Qᵢ-Qⱼ| ≠ |i-j|

8.2 Types of Constraints

Type Description Example
Unary Involves one variable SA ≠ green
Binary Involves two variables SA ≠ WA
Ternary Involves three variables Between(X,Y,Z): X<Y<Z
Global/N-ary Involves n variables Alldiff(Q₁,...,Q₈)
Hard Must be satisfied No two queens attack each other
Soft/Preference Preferred but not required Prof. R prefers morning

8.3 Constraint Propagation — Inference

Before and during search, constraint propagation eliminates values from variable domains by enforcing
consistency. This can dramatically reduce the search space or even solve the problem entirely.

8.3.1 Node Consistency

Node Consistent Every value in the domain satisfies all unary constraints

Simple to achieve: just remove values that violate unary constraints from each domain before search
begins.
8.3.2 Arc Consistency (AC-3 Algorithm)

📖 DEFINITION: Arc Consistency

Variable Xᵢ is arc-consistent with Xⱼ if for every value in Dᵢ,
there exists some value in Dⱼ that satisfies the constraint between them.

AC-3 Algorithm:
→ Initialize queue with all arcs (Xᵢ, Xⱼ)
→ For each arc: remove values from Dᵢ that have no support in Dⱼ
→ If Dᵢ is revised, re-add all arcs (Xₖ, Xᵢ) to queue
→ Return FAILURE if any domain becomes empty
→ Complexity: O(cd³) where c = constraints, d = domain size

function AC-3(csp):
queue := all arcs in csp
while queue not empty:
(Xi, Xj) := [Link]()
if REVISE(csp, Xi, Xj):
if |Di| == 0: return FAILURE
for Xk in [Link] - {Xj}:
[Link]((Xk, Xi))
return True

function REVISE(csp, Xi, Xj):

revised := False
for x in Di:
if no y in Dj satisfies constraint(Xi=x, Xj=y):
remove x from Di
revised := True
return revised

📌 EXAMPLE: AC-3 on Map Coloring

Variables: WA, SA, NT (all connected)
Domains: all = {red, green, blue}
Constraints: WA≠SA, WA≠NT, SA≠NT

AC-3 does not reduce domains here (binary constraints, 3 colors, enough room)

But after partial assignment WA=red, NT=green:

→ SA's domain becomes {blue} (only 1 value satisfies all constraints!)
→ AC-3 reveals SA must be blue — no search needed for SA.

Forward checking (simpler than AC-3) would also detect this.

8.3.3 Forward Checking

📖 DEFINITION: Forward Checking

 When a variable X is assigned a value:
For each unassigned variable Y connected to X:
Delete from Y's domain any value inconsistent with X's assignment

Simpler than full arc consistency but catches most conflicts early.
Immediately detects dead ends — empty domain means backtrack now.

📌 EXAMPLE: Forward Checking on Australia Map

Assign WA=red:
→ NT domain: {red,green,blue} → {green,blue} (remove red)
→ SA domain: {red,green,blue} → {green,blue} (remove red)

Assign Q=green:
→ NT domain: {green,blue} → {blue} (remove green)
→ SA domain: {green,blue} → {blue} (remove green)
→ NSW domain: {red,green,blue} → {red,blue} (remove green)

Assign V=blue:
→ SA domain: {blue} → {} EMPTY! (remove blue)
→ Backtrack immediately! V=blue is incompatible with all constraints.

Forward checking saved exploring NT, SA, NSW branches unnecessarily.

8.4 Backtracking Search for CSPs

📖 DEFINITION: CSP Backtracking

A systematic search that assigns one variable at a time,
checking consistency after each assignment.

Key principle: Only assign values consistent with current assignment.

→ This reduces the search space from dⁿ (naive) to much smaller.

function BACKTRACKING-SEARCH(csp):
return BACKTRACK(csp, {})

function BACKTRACK(csp, assignment):

if assignment is complete: return assignment
var := SELECT-UNASSIGNED-VARIABLE(csp, assignment)
for value in ORDER-DOMAIN-VALUES(csp, var, assignment):
if value is consistent with assignment:
add {var=value} to assignment
inferences := INFERENCE(csp, var, assignment) # forward check
if inferences ≠ FAILURE:
add inferences to csp
result := BACKTRACK(csp, assignment)
if result ≠ FAILURE: return result
 remove inferences and {var=value} from assignment
return FAILURE

8.5 Heuristics for CSP Search

8.5.1 Variable Ordering — Which Variable to Assign Next?
Minimum Remaining Values (MRV) — Fail-First
Choose the variable with the FEWEST legal values remaining in its domain. This detects failures early,
pruning the search tree.

● Intuition → If SA has only 1 legal value, assign it now to detect conflicts immediately
● Also called → 'Most Constrained Variable' or 'Fail-First' heuristic

Degree Heuristic
Among variables with equal MRV count, choose the one involved in the MOST constraints with
unassigned variables. Maximizes future pruning.

● Example → SA touches 5 other Australian regions — highest degree, assign first

8.5.2 Value Ordering — Which Value to Try First?

Least Constraining Value (LCV)
Assign the value that RULES OUT the fewest choices for neighboring unassigned variables. Maximizes
flexibility for remaining variables.

● Intuition → We want to assign a value that keeps the most options open
● Fail-last → For VALUES, we try the most promising first (opposite of fail-first for variables)

MRV + LCV Combined Strategy

For VARIABLES: Fail-First (MRV) — assign most constrained variable first
→ Every variable MUST be assigned — might as well detect failures early

For VALUES: Fail-Last (LCV) — try most promising value first

→ We only need ONE solution — try the value most likely to succeed

This combination is the most effective general CSP strategy.

8.6 Intelligent Backtracking — Backjumping

Standard backtracking (chronological backtracking) backs up to the immediately preceding variable
when failure occurs. This can be inefficient if the conflict involves a much earlier variable.
 📖 DEFINITION: Conflict-Directed Backjumping
Maintains a CONFLICT SET for each variable:
= the set of preceding variables that caused the failure

When failure occurs: jump back to the MOST RECENT variable in conflict set
→ Skip over variables that couldn't have caused the failure

Example: Variables assigned in order Q, NSW, V, T, SA

SA fails (conflicts with Q, NSW, V but NOT T)
Standard backtracking: back up to T → pointless
Backjumping: back up to V (most recent in conflict set) → efficient

8.7 Local Search for CSPs — Min-Conflicts

📖 DEFINITION: Min-Conflicts Heuristic

A local search algorithm for CSPs:
1. Start with a complete assignment (possibly inconsistent)
2. While there are violated constraints:
a. Randomly pick a CONFLICTED variable
b. Reassign it to the value that MINIMIZES conflicts with other variables
3. Return assignment when all constraints satisfied

Amazingly effective for large CSPs!

Solves 1-million queens problem in ~50 steps on average.

📌 EXAMPLE: Min-Conflicts on 8-Queens

Start: Place queens randomly (many conflicts)
Conflicts: [2,2,1,2,3,1,2,3] for 8 columns

Step 1: Pick conflicted queen in column 8 (3 conflicts)

Options for row: row 3 has min-conflicts = 1
→ Move queen to row 3

Step 2: Pick conflicted queen in column 6 (1 conflict)

Option: row 8 has 0 conflicts
→ Move queen to row 8

Step 3: No more conflicted queens → SOLUTION FOUND!

Min-conflicts is fast because it repairs existing assignments

rather than building solutions from scratch.
8.8 CSP Summary — Complete Strategy Table
Challenge Strategy Algorithm
Large domain pruning Constraint propagation AC-3
Early failure detection Forward checking Forward Checking
Variable selection Most constrained first MRV Heuristic
Tie-breaking variables Most constraints first Degree Heuristic
Value selection Least constraining first LCV Heuristic
Intelligent backtrack Jump to conflict source Backjumping
Large-scale CSPs Local search repair Min-Conflicts
Structured problems Decompose subproblems Tree decomposition

🔍 CASE STUDY: Sudoku Solving: CSP Approach in Practice

PROBLEM: Fill 9×9 grid with digits 1-9; no repeats in any row, column, or box

CSP FORMULATION:
Variables: 81 squares
Domains: {1-9} for empty, singleton for given
Constraints: 27 Alldiff constraints (9 rows + 9 columns + 9 boxes)

SOLVING STRATEGY:
Step 1: AC-3 propagation — eliminate values violating arc consistency
→ Often solves easy puzzles completely!
Step 2: For harder puzzles, apply MRV to choose next variable
→ Pick the square with fewest remaining legal digits
Step 3: LCV for value ordering — try digit that eliminates fewest options
Step 4: Backtrack if contradiction found

RESULT: Even the hardest Sudoku puzzles solved in milliseconds.

CSP solvers process thousands of Sudoku puzzles per second.
A CSP solver can solve ANY Sudoku — the same code, same algorithm,
just different input. This is the power of the CSP formalism.

MODULE 9: COMPLETE SUMMARY & EXAM

PREPARATION

9.1 Syllabus Topic — Key Points

Introduction to AI
★ AI = study and engineering of rational agents that sense, reason, and act optimally.
★ Four approaches: Acting Humanly (Turing Test), Thinking Humanly (cognitive models), Thinking
Rationally (logic), Acting Rationally (rational agents — dominant paradigm).
 ★ PEAS framework: Performance, Environment, Actuators, Sensors — used to specify any AI
agent.

General Problem Solving

★ GPS (Newell & Simon, 1957) separated problem-solving strategy from domain knowledge.
★ Means-Ends Analysis: compare current state to goal, find difference, apply operator to reduce
difference, set subgoals for unsatisfied preconditions.
★ Problem Reduction: decompose into AND/OR sub-problems; AO* searches AND-OR trees.
★ Forward chaining (data-driven) vs Backward chaining (goal-driven) — choice depends on
problem structure.

Characteristics of Problems
★ Decomposable → use problem reduction. Non-decomposable → unified search.
★ Ignorable steps → backtracking freely. Recoverable → careful search. Irrecoverable → planning
required.
★ Goal type (single/multiple/property/path) determines the goal test and solution criteria.
★ Branching factor b, depth d, max depth m determine complexity: O(bᵈ) for most algorithms.

Exhaustive Search Strategies

★ Generate-and-Test: Generate candidates systematically, test each. Quality of generator
determines efficiency.
★ British Museum Algorithm: random/unguided search — serves as worst-case baseline.
★ BFS: Complete, optimal (uniform costs), time O(bᵈ), space O(bᵈ) — memory intensive.
★ DFS: Incomplete, not optimal, time O(bᵐ), space O(b·m) — memory efficient.
★ UCS: Complete, optimal, uses priority queue ordered by g(n).

Heuristic Search Techniques

★ Hill Climbing: move to best child, no history, fast but gets stuck at local maxima.
★ Simulated Annealing: accepts worse states with probability e^(-ΔE/T), escapes local maxima.
★ Beam Search: keep only k best states per level — space O(k·b), not complete.
★ A*: f(n)=g(n)+h(n), complete and optimal with admissible h(n).
★ Admissible h: h(n) ≤ h*(n). Consistent h: h(n) ≤ c(n,a,n') + h(n'). Consistent → Admissible.

Iterative Deepening
★ IDDFS = BFS optimality/completeness + DFS space efficiency. Best uninformed strategy.
★ Overhead is minimal: only 11% extra work for b=10. Time O(bᵈ), Space O(b·d).
★ IDA* = IDDFS + A* heuristic. f-value threshold increases each iteration. Space O(b·d).
Constraint Satisfaction
★ CSP: variables, domains, constraints. Solution = complete consistent assignment.
★ AC-3: arc consistency algorithm. O(cd³). Can solve some problems completely without search.
★ Forward Checking: when X assigned, remove inconsistent values from neighbors' domains.
★ MRV (Fail-First): assign most constrained variable first. Degree heuristic for tie-breaking.
★ LCV (Fail-Last): try least constraining value first. Maximizes remaining flexibility.
★ Min-Conflicts: local search — reassign conflicted variables to minimize conflicts.

9.2 Formula Reference Card

Algorithm f(n) Queue Complete? Optimal?
BFS Depth (d) FIFO ✅ ✅ (uniform costs)
DFS Depth (descending) LIFO Stack ❌ ❌
UCS / Dijkstra g(n) Priority by g(n) ✅ ✅
Greedy Best-First h(n) Priority by h(n) ❌ ❌
A* g(n)+h(n) Priority by f(n) ✅ ✅ (admissible h)
IDA* g(n)+h(n)≤T Stack (IDDFS) ✅ ✅ (admissible h)
Beam Search h(n) Priority, keep k ❌ ❌

9.3 Algorithm Selection Guide

Situation Best Algorithm Reason
No heuristic, equal costs, small BFS Complete + optimal
space
No heuristic, unknown depth IDDFS BFS quality + DFS memory
Variable costs, no heuristic UCS Optimal for any cost
Good heuristic available A* Optimal + efficient
Memory limited with heuristic IDA* A* quality + DFS memory
Many goals, large space Greedy Best-First Fast (not optimal)
Quick approximation needed Hill Climbing or Beam Fast, memory efficient
CSP with structured constraints AC-3 + Backtracking + MRV Domain reduction
Large-scale CSP Min-Conflicts Local search, very fast
Two-player game Minimax + Alpha-Beta Adversarial optimality

9.4 Important Definitions to Remember

Admissibility h(n) ≤ h*(n) — heuristic never overestimates true cost

Consistency h(n) ≤ c(n,a,n') + h(n') — triangle inequality holds

 Completeness Algorithm guaranteed to find solution if one exists

Optimality Algorithm finds solution with minimum cost

Branching Factor Average number of children per node (b)

Means-Ends Analysis Problem solving by reducing differences between current and goal state

CSP Solution Complete + consistent assignment of values to all variables

Arc Consistency Every value in Dᵢ has at least one compatible value in Dⱼ

Forward Checking Propagate constraints after each variable assignment

9.5 Practice Problems

● 1. Trace BFS and DFS on the Romania map from Arad to Bucharest
● 2. Apply A* with Manhattan Distance heuristic to the 8-puzzle
● 3. Given h={A:4, B:2, C:6, D:0}, is this admissible? consistent? Explain.
● 4. Formulate the Missionaries & Cannibals problem as a state space [N,A,S,GD]
● 5. Classify a given problem by: decomposability, recoverability, goal type, solution type
● 6. Trace backtracking search on a map coloring CSP with MRV and forward checking
● 7. Compare IDDFS and BFS complexity for b=3, d=6. Calculate overhead.
● 8. Apply min-conflicts to solve a 4-queens problem from a conflicted initial state
● 9. Explain why consistent heuristic implies admissible but not vice versa
● 10. Write pseudocode for hill climbing and explain with the 8-puzzle example

— End of Lecture Notes — Unit I — Complete Syllabus Coverage —

Sources: Artificial Intelligence: A Modern Approach (Russell & Norvig, 4th Ed.)
Artificial Intelligence: Structures and Strategies for Complex Problem Solving (Luger, 6th Ed.)
 INFORMED & UNINFORMED SEARCH
Strategies in Artificial Intelligence

With Worked Case Studies for Every Subtype

Prepared for Undergraduate Students

PART A: OVERVIEW — TWO FAMILIES OF SEARCH

When an AI agent needs to find a path from a start state to a goal state, it uses a search algorithm. All
search algorithms fall into two broad families, depending on whether they use extra knowledge about
the problem (a heuristic) to guide their choices.

Aspect Uninformed (Blind) Search Informed (Heuristic) Search

Knowledge used None — only problem definition Uses h(n): estimate of distance to
goal
Also called Blind search, exhaustive search Heuristic search
How it picks next node Fixed rule (FIFO/LIFO/cost) Guided by 'how promising' a node
looks
Efficiency Explores many irrelevant states Focuses on promising states —
much faster
Examples BFS, DFS, UCS, IDDFS Greedy Best-First, A*
When to use No domain knowledge available Domain knowledge available as h(n)

📖 Key Idea to Remember

UNINFORMED search treats every unexplored node the same — it has no sense of
direction toward the goal. It is like exploring a maze with your eyes closed,
feeling your way along a fixed strategy (e.g., always go right).

INFORMED search uses a heuristic function h(n) — an estimate of how far a node
is from the goal — to choose the most promising direction first. It is like
exploring the same maze with a rough compass pointing toward the exit.
PART B: UNINFORMED (BLIND) SEARCH STRATEGIES

Uninformed search algorithms have access only to the problem definition: the initial state, the actions
available, and a test for whether a state is the goal. They do NOT know how close any state is to the
goal — they simply follow a systematic rule for exploring the state space.

We cover four major subtypes: Breadth-First Search (BFS), Depth-First Search (DFS), Uniform-Cost
Search (UCS), and Iterative Deepening DFS (IDDFS).

B1. Breadth-First Search (BFS)

BFS explores the state space level by level. It expands all nodes at depth 1, then all nodes at depth 2,
and so on, until the goal is found. It uses a FIFO (First-In-First-Out) queue.

📖 How BFS Works

1. Put the start node in a queue (open list)
2. Remove the FRONT node from the queue
3. If it is the goal → STOP, return the path
4. Otherwise, generate its children and add them to the BACK of the queue
5. Repeat from step 2

Because it always explores the shallowest unexpanded node first, BFS is

GUARANTEED to find the SHORTEST path (fewest edges) to the goal.

function BFS(start, goal):

queue := [start] # FIFO
visited := {start}
while queue is not empty:
node := queue.pop_front()
if node == goal: return path_to(node)
for child in neighbors(node):
if child not in visited:
[Link](child)
queue.push_back(child)
return FAILURE

🧩 CASE STUDY: Find the Shortest Route in a Small Town Map

A delivery robot is at the WAREHOUSE (S) and must reach the CUSTOMER (G).
The town's road map (undirected, unweighted) is:

S—A
S—B
A—C
A—D
 B—D
B—E
D—G
E—G

QUESTION: Using BFS, find the shortest path (in number of road segments)
from S to G, and show the order in which nodes are visited.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Build the adjacency list:
S: [A, B]
A: [S, C, D]
B: [S, D, E]
C: [A]
D: [A, B, G]
E: [B, G]
G: [D, E]

STEP 2 — Run BFS from S (goal = G):

Queue=[S] Visited={S}
Pop S → not goal → add A,B → Queue=[A,B] Visited={S,A,B}
Pop A → not goal → add C,D → Queue=[B,C,D] Visited={S,A,B,C,D}
Pop B → not goal → add E (D already visited) → Queue=[C,D,E]
Pop C → not goal → no new children → Queue=[D,E]
Pop D → not goal → add G → Queue=[E,G] Visited={...,G}
Pop E → not goal → G already visited → Queue=[G]
Pop G → GOAL FOUND! ✅

STEP 3 — Trace back the path using parent pointers:

G's parent = D, D's parent = A, A's parent = S

FINAL ANSWER:
Shortest Path: S → A → D → G
Path Length: 3 road segments
Visit Order: S, A, B, C, D, E, G

Property BFS
Complete? ✅ Yes
Optimal? ✅ Yes (when all edges have equal cost)
Time Complexity O(bᵈ)
Space Complexity O(bᵈ) — stores all frontier nodes

B2. Depth-First Search (DFS)

DFS explores as deep as possible along one branch before backtracking. It uses a LIFO (Last-In-First-
Out) stack — either explicitly, or implicitly via recursion.
📖 How DFS Works
1. Put the start node on a stack (open list)
2. Remove the TOP node from the stack
3. If it is the goal → STOP, return the path
4. Otherwise, push its children onto the stack
5. Repeat from step 2 — this naturally goes DEEP before going WIDE

DFS does NOT guarantee the shortest path — it returns the FIRST solution
path it stumbles upon, which may be longer than necessary.

function DFS(start, goal):

stack := [start] # LIFO
visited := {start}
while stack is not empty:
node := [Link]() # remove from TOP
if node == goal: return path_to(node)
for child in neighbors(node):
if child not in visited:
[Link](child)
[Link](child)
return FAILURE

🧩 CASE STUDY: Maze Escape — Single Path Exploration

A mouse starts at room S in a maze and must reach the cheese at room G.
Room connections (graph):

S—A
S—B
A—C
A—D
B—E
D—G
E—G

QUESTION: Using DFS (always explore the FIRST listed neighbor first, and
backtrack only when stuck), find a path from S to G. Show the visit order.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Adjacency list (children listed in exploration order):
S: [A, B]
A: [C, D] (S already visited, so skip going back)
B: [E]
C: [] (dead end — no unvisited neighbors)
D: [G]
E: [G]

STEP 2 — Run DFS from S (goal = G), exploring first neighbor each time:
 Stack=[S] Visited={S}
Pop S → not goal → push A,B → Stack=[A,B] (A on top)
Pop A → not goal → push C,D → Stack=[B,C,D] (D on top)
Pop D → not goal → push G → Stack=[B,C,G] (G on top)
Pop G → GOAL FOUND! ✅

STEP 3 — Trace back the path:

G's parent = D, D's parent = A, A's parent = S

FINAL ANSWER:
Path Found: S → A → D → G
Path Length: 3 road segments
Visit Order: S, A, D, G (C and B never had to be explored further!)

NOTE: DFS got lucky here — it found a short path by chance, because D
happened to be pushed last (explored first). If the adjacency order were
different, DFS might explore S→B→E→G first instead, missing the shorter
route via A — DFS does NOT guarantee the shortest path.

Property DFS
Complete? ❌ No (can loop forever in infinite/cyclic spaces without
visited-check)
Optimal? ❌ No (first path found, not necessarily shortest)
Time Complexity O(bᵐ) where m = maximum depth
Space Complexity O(b·m) — only stores the current path — very memory
efficient

B3. Uniform-Cost Search (UCS)

UCS is used when edges have different costs (e.g., distance, time, money) and we want the
CHEAPEST path, not just the shortest in terms of number of steps. UCS always expands the node with
the lowest cumulative cost g(n) so far, using a priority queue.

📖 How UCS Works

1. Put the start node in a priority queue, with cost g(start) = 0
2. Remove the node with the SMALLEST g(n) from the queue
3. If it is the goal → STOP, return the path (guaranteed cheapest)
4. Otherwise, for each neighbor, calculate new cost = g(node) + edge_cost
→ If this is cheaper than any previously found cost to that neighbor,
update it and add/re-insert into the priority queue
5. Repeat from step 2

function UCS(start, goal):

pqueue := priority_queue ordered by g(n)
[Link](start, g=0)
 visited := {}
while pqueue is not empty:
node, cost := pqueue.pop_min()
if node == goal: return path_to(node), cost
if node in visited: continue
[Link](node)
for (child, edge_cost) in neighbors(node):
new_cost := cost + edge_cost
[Link](child, new_cost)
return FAILURE

🧩 CASE STUDY: Cheapest Flight Route Between Cities

A travel agent must find the CHEAPEST flight route from CHENNAI (S) to
DELHI (G). Available direct flights and fares (in ₹thousands):

Chennai → Bengaluru : 2
Chennai → Hyderabad : 5
Bengaluru → Hyderabad : 1
Bengaluru → Mumbai :6
Hyderabad → Delhi :4
Mumbai → Delhi :2

QUESTION: Using UCS, find the cheapest total fare and the route from
Chennai to Delhi.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Represent as a weighted graph:
Chennai(S) -2-> Bengaluru, -5-> Hyderabad
Bengaluru -1-> Hyderabad, -6-> Mumbai
Hyderabad -4-> Delhi
Mumbai -2-> Delhi

STEP 2 — Run UCS, always expanding the LOWEST cumulative cost node:

PQueue=[Chennai(0)]
Pop Chennai(0) → not goal → expand:
Bengaluru: g=0+2=2
Hyderabad: g=0+5=5
PQueue=[Bengaluru(2), Hyderabad(5)]

Pop Bengaluru(2) → not goal → expand:

Hyderabad: g=2+1=3 ← CHEAPER than existing 5! Update.
Mumbai: g=2+6=8
PQueue=[Hyderabad(3), Mumbai(8), Hyderabad(5)-stale]

Pop Hyderabad(3) → not goal → expand:

Delhi: g=3+4=7
PQueue=[Delhi(7), Mumbai(8), Hyderabad(5)-stale]
 Pop Delhi(7) → GOAL FOUND! ✅ (ignore the stale Hyderabad(5) entry)

STEP 3 — Trace back the path:

Delhi's parent = Hyderabad (via the 3-cost path)
Hyderabad's parent = Bengaluru
Bengaluru's parent = Chennai

FINAL ANSWER:
Cheapest Route: Chennai → Bengaluru → Hyderabad → Delhi
Total Fare: ₹7,000 (2 + 1 + 4)

NOTE: The direct Chennai→Hyderabad flight (₹5,000) seemed cheaper at

first glance, but routing through Bengaluru (₹2,000 + ₹1,000 = ₹3,000)
and then to Delhi (₹4,000) totals only ₹7,000 — UCS correctly finds this
by comparing ALL cumulative costs, not just direct distances.

Property UCS
Complete? ✅ Yes (if all edge costs > 0)
Optimal? ✅ Yes — always finds the cheapest path
Time Complexity O(b^(1+⌊C*/ε⌋)) where C* = optimal cost, ε = min edge
cost
Space Complexity Same as time — stores all generated nodes

B4. Iterative Deepening Depth-First Search (IDDFS)

IDDFS combines the best of both worlds: it gets the completeness and optimality of BFS while keeping
DFS's low memory usage. It performs DFS repeatedly with an increasing depth limit: first allow depth 0,
then depth 1, then depth 2, and so on — until the goal is found.

📖 How IDDFS Works

1. Set depth limit L = 0
2. Perform a DEPTH-LIMITED DFS — explore nodes only up to depth L
3. If the goal is found within this limit → STOP, return the path
4. Otherwise, increase L by 1, and repeat the depth-limited DFS from scratch
5. Continue until the goal is found

Although nodes get re-explored at each iteration, the total extra work
is small (around 10-25% overhead) — well worth the massive memory savings.

function IDDFS(start, goal):

for L = 0 to infinity:
result := Depth_Limited_DFS(start, goal, L)
if result != CUTOFF:
return result

function Depth_Limited_DFS(node, goal, limit, depth=0):

 if node == goal: return path_to(node)
if depth == limit: return CUTOFF
for child in neighbors(node):
result := Depth_Limited_DFS(child, goal, limit, depth+1)
if result != CUTOFF: return result
return CUTOFF

🧩 CASE STUDY: Locating a File in an Unknown-Depth Folder Tree

A search tool needs to find a file named '[Link]' somewhere inside
a folder structure, but it does NOT know how many folders deep the file
is. The folder tree (S = root, G = [Link]) is:

S
/ \
A B
/\ \
C D E
\
G

QUESTION: Using IDDFS, show how the search progresses through

increasing depth limits to find G, and state at which depth it is found.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Note the depths of each node:
Depth 0: S
Depth 1: A, B
Depth 2: C, D, E
Depth 3: G

STEP 2 — Run IDDFS, increasing the depth limit L from 0:

ITERATION L=0: Depth-limited DFS allows only S.

Visit: S → not goal → depth limit reached → CUTOFF

ITERATION L=1: Allows depth 0 and 1.

Visit: S → A → not goal (depth 1, limit reached)
→ B → not goal (depth 1, limit reached)
→ CUTOFF (G not found)

ITERATION L=2: Allows depth 0, 1, and 2.

Visit: S → A → C → not goal (limit reached)
→ D → not goal (limit reached)
→ B → E → not goal (limit reached)
→ CUTOFF (G not found, it's even deeper)

ITERATION L=3: Allows depth 0, 1, 2, and 3.

Visit: S → A → C → (no children, dead end)
→ D → (no children, dead end)
 → B → E → G → GOAL FOUND! ✅ (at depth 3)

STEP 3 — Trace back the path:

G's parent = E, E's parent = B, B's parent = S

FINAL ANSWER:
Path Found: S → B → E → G
Depth of Goal: 3
Total Iterations Run: 4 (L = 0, 1, 2, 3)

NOTE: Although S, A, B were each visited multiple times across

iterations, this is the cost we pay for using only O(depth) memory —
compare this to BFS, which would need to store ALL nodes at every
level simultaneously in memory.

Property IDDFS
Complete? ✅ Yes
Optimal? ✅ Yes (when all edges have equal cost)
Time Complexity O(bᵈ) — modest re-expansion overhead (~10-25%)
Space Complexity O(b·d) — same as DFS, far better than BFS's O(bᵈ)

PART C: INFORMED (HEURISTIC) SEARCH

STRATEGIES

Informed search algorithms use a heuristic function h(n) — an estimate of the cost from node n to the
nearest goal — to decide which node to explore next. This extra knowledge lets these algorithms ignore
unpromising directions and reach the goal much faster than blind search.

We cover three major subtypes: Greedy Best-First Search, A* Search, and Hill Climbing.

C1. Greedy Best-First Search

Greedy Best-First Search always expands the node that LOOKS closest to the goal, based purely on
the heuristic h(n). It completely ignores the cost already spent to reach that node — hence the name
'greedy.'

📖 How Greedy Best-First Works

1. Put the start node in a priority queue, ordered by h(n) only
2. Remove the node with the SMALLEST h(n)
3. If it is the goal → STOP, return the path
4. Otherwise, add its children to the priority queue (ordered by their h values)
5. Repeat from step 2

Evaluation function: f(n) = h(n) ← cost-so-far g(n) is IGNORED

WARNING: Greedy search is FAST but NOT optimal — it can be led astray
by a misleading heuristic and miss the actual shortest/cheapest path.

function Greedy_Best_First(start, goal):

pqueue := priority_queue ordered by h(n)
[Link](start)
visited := {}
while pqueue is not empty:
node := pqueue.pop_min_h()
if node == goal: return path_to(node)
[Link](node)
for child in neighbors(node):
if child not in visited:
[Link](child) # ordered by h(child)
return FAILURE

🧩 CASE STUDY: Robot Navigating Toward a Charging Station

A robot at point S must reach the charging station at G as quickly as
possible. Straight-line distance heuristic h(n) to G is given for each
room (lower = closer to goal):

Room h(n) to G Connections

S 10 S-A, S-B
A 6 A-D
B 8 B-D, B-E
D 3 D-G
E 1 E-G
G 0 (goal)

QUESTION: Using Greedy Best-First Search, find the path the robot takes
from S to G.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Note the heuristic values (estimated distance to goal):
h(S)=10, h(A)=6, h(B)=8, h(D)=3, h(E)=1, h(G)=0

STEP 2 — Run Greedy Best-First, always picking the LOWEST h(n):

PQueue=[S(h=10)]
Pop S → not goal → expand children A(h=6), B(h=8)
PQueue=[A(h=6), B(h=8)] ← A picked next since h=6 < h=8

Pop A(h=6) → not goal → expand child D(h=3)

 PQueue=[D(h=3), B(h=8)] ← D picked next since h=3 is lowest

Pop D(h=3) → not goal → expand child G(h=0)

PQueue=[G(h=0), B(h=8)] ← G picked next since h=0 is lowest

Pop G(h=0) → GOAL FOUND! ✅

STEP 3 — Trace back the path:

G's parent = D, D's parent = A, A's parent = S

FINAL ANSWER:
Path Found: S → A → D → G
Nodes Expanded: S, A, D, G (only 4 nodes — B and E never explored!)

NOTE: Greedy search never even looked at B or E, because A and D

always looked more promising (lower h). This makes it very fast, but
if the true shortest path had actually gone through B (with a heuristic
that temporarily looked worse), Greedy search would have missed it —
this is the key WEAKNESS of greedy search: it can be short-sighted.

Property Greedy Best-First Search

Complete? ❌ No (can get stuck in loops without cycle-checking)
Optimal? ❌ No (ignores path cost g(n), can find a suboptimal
path)
Time Complexity O(bᵐ) worst case, often much faster with a good
heuristic
Space Complexity O(bᵐ) — stores all generated nodes

C2. A* Search
A* (pronounced 'A-star') is the most widely used informed search algorithm. It combines the strengths
of UCS (which uses the actual cost-so-far g(n)) and Greedy search (which uses the estimated cost-to-
go h(n)).

📖 How A* Works
Evaluation function: f(n) = g(n) + h(n)
g(n) = actual cost from start to node n
h(n) = estimated cost from node n to the goal
f(n) = estimated TOTAL cost of the cheapest solution through n

1. Put the start node in a priority queue, ordered by f(n)

2. Remove the node with the SMALLEST f(n)
3. If it is the goal → STOP, return the path (guaranteed optimal!)
4. Otherwise, for each child: calculate g and f, add/update in queue
5. Repeat from step 2

REQUIREMENT: h(n) must be ADMISSIBLE (never overestimate the true cost)

for A* to guarantee the optimal (cheapest) solution.

function A_star(start, goal):

pqueue := priority_queue ordered by f(n) = g(n)+h(n)
[Link](start, g=0)
best_g := {start: 0}
while pqueue is not empty:
node, g := pqueue.pop_min_f()
if node == goal: return path_to(node), g
for (child, edge_cost) in neighbors(node):
new_g := g + edge_cost
if child not in best_g or new_g < best_g[child]:
best_g[child] := new_g
f := new_g + h(child)
[Link](child, f)
return FAILURE

🧩 CASE STUDY: Ambulance Routing to a Hospital

An ambulance at point S must reach the HOSPITAL at G via the shortest
possible total road distance. Road segments (with actual distance in km)
and straight-line heuristic distance h(n) to the hospital are given:

Road segments (actual cost):

S — A : 4 km A — D : 3 km
S — B : 2 km B — D : 5 km
B — E : 4 km D — G : 4 km
E — G : 2 km

Heuristic h(n) — straight-line distance to G:

h(S)=7, h(A)=5, h(B)=6, h(D)=2, h(E)=2, h(G)=0

QUESTION: Using A* Search, find the optimal (shortest distance) route

from S to G.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Note f(n) = g(n) + h(n) is computed fresh at each step.

STEP 2 — Run A* Search:

PQueue=[S(g=0,h=7,f=7)]
Pop S(f=7) → not goal → expand:
A: g=0+4=4, f=4+5=9
B: g=0+2=2, f=2+6=8
PQueue=[B(f=8), A(f=9)]

Pop B(f=8) → not goal → expand:

D: g=2+5=7, f=7+2=9
E: g=2+4=6, f=6+2=8
 PQueue=[E(f=8), A(f=9), D(f=9)]

Pop E(f=8) → not goal → expand:

G: g=6+2=8, f=8+0=8
PQueue=[G(f=8), A(f=9), D(f=9)]

Pop G(f=8) → GOAL FOUND! ✅

(G's f=8 is the lowest in queue — guaranteed optimal, no need
to check A or D further since they cannot produce a cheaper path)

STEP 3 — Trace back the path:

G's parent = E, E's parent = B, B's parent = S

FINAL ANSWER:
Optimal Path: S → B → E → G
Total Distance: 8 km (2 + 4 + 2)

VERIFY: Compare with the alternative route S→A→D→G = 4+3+4 = 11 km.

Indeed, 8 km < 11 km, confirming A* found the TRUE shortest path —
something Greedy search is not guaranteed to do.

Property A* Search
Complete? ✅ Yes
Optimal? ✅ Yes — guaranteed, IF h(n) is admissible (never
overestimates)
Time Complexity O(bᵈ) worst case, but typically much better with a good
h(n)
Space Complexity O(bᵈ) — stores all generated nodes (main drawback)

C3. Hill Climbing

Hill Climbing is the simplest informed search technique. At each step, it looks at the immediate
neighbors of the current state and moves to whichever neighbor has the BEST heuristic value — like a
climber always moving uphill. It keeps no memory of past states, so it cannot backtrack.

📖 How Hill Climbing Works

1. Start at the initial state; treat it as the 'current' state
2. Generate all neighbors (children) of the current state
3. Evaluate each neighbor using h(n)
4. If the BEST neighbor is better than the current state →
move to that neighbor (this becomes the new current state)
5. If NO neighbor is better than the current state → STOP
(we are at a peak — possibly only a LOCAL maximum, not the true goal)
6. Repeat from step 2

WARNING: Hill Climbing can get stuck at a LOCAL MAXIMUM — a state

that looks best among its neighbors but is not the actual best solution.
function Hill_Climbing(start):
current := start
while True:
neighbors := generate_neighbors(current)
best := neighbor in neighbors with maximum value(neighbor)
if value(best) <= value(current):
return current # local maximum reached — stop
current := best

🧩 CASE STUDY: Maximizing Signal Strength for a Drone Antenna

A drone must position itself at the grid cell with the STRONGEST WiFi
signal. It starts at cell C and can only move to directly adjacent
cells (up/down/left/right). The signal strength (heuristic value —
higher is better) at each cell is:

col1 col2 col3 col4

row1: 2 4 5 3
row2: 3 6 8 4 ← drone starts here (row2,col3=8)
row3: 1 5 7 2

Drone starts at (row2, col3) = signal strength 8.

QUESTION: Using Hill Climbing, trace the drone's movement to find the
strongest signal it settles on, and identify if it is a true (global)
maximum or a local maximum.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Current position: (row2,col3), strength = 8
Its 4 neighbors:
Up (row1,col3) = 5
Down (row3,col3) = 7
Left (row2,col2) = 6
Right (row2,col4) = 4

STEP 2 — Compare neighbors to current value (8):

Best neighbor value = 7 (Down)
Is 7 > 8? NO — none of the neighbors beat the current value!

STEP 3 — STOP. Hill Climbing terminates immediately.

Final position: (row2, col3), Signal Strength = 8

STEP 4 — Check: is this the TRUE best (global maximum) in the grid?
Scanning the entire grid, the maximum value present is also 8,
at (row2, col3) — the very cell the drone started at and stayed on.

FINAL ANSWER:
Drone settles at: (row2, col3)
Final Signal Strength: 8
 This IS the GLOBAL maximum for this particular grid — Hill Climbing
succeeded here because it started at a favorable position.

IMPORTANT LESSON: If the drone had instead started at (row1,col1)=2,

it would climb to (row1,col2)=4, then (row1,col3)=5, then check
neighbors of 5: Up=none, Down=8(row2,col3), Left=4, Right=3 → moves to 8,
then is stuck again with strength 8 (its neighbors are 5,7,6,4 — none
higher). Even from a different start, it reaches the same global peak
here — but in general, a DIFFERENT grid could trap Hill Climbing at a
LOCAL maximum like 7 (row3,col3) if its neighbors were all ≤7, even
though a higher peak of 8 existed elsewhere unreachable from there.

Property Hill Climbing

Complete? ❌ No (can get stuck at a local maximum or plateau)
Optimal? ❌ No (returns the first peak found, not necessarily the
global best)
Time Complexity Very fast — O(depth to nearest peak)
Space Complexity O(1) — only stores the current state (extremely memory
efficient)

PART D: SUMMARY TABLE — ALL SUBTYPES AT A

GLANCE

D.1 Uninformed Search — Quick Comparison

Algorithm Strategy Case Study Used Complete? Optimal?
BFS Explore level by Delivery robot — ✅ ✅ (equal costs)
level (FIFO) shortest route
DFS Explore deep first Mouse in a maze ❌ ❌
(LIFO)
UCS Explore lowest cost Cheapest flight route ✅ ✅ (any cost)
so far
IDDFS Repeated DFS with Finding a file at ✅ ✅ (equal costs)
growing depth limit unknown depth

D.2 Informed Search — Quick Comparison

Algorithm Strategy Case Study Used Complete? Optimal?
Greedy Best-First Pick lowest h(n) only Robot to charging ❌ ❌
station
A* Search Pick lowest g(n) Ambulance routing ✅ ✅ (admissible h)
 +h(n)
Hill Climbing Always move to best Drone signal ❌ ❌
neighbor maximization

D.3 Choosing the Right Algorithm

● Need shortest path, no edge costs, no heuristic → Use BFS
● Memory is very limited, any solution acceptable → Use DFS
● Edges have different costs, need cheapest path, no heuristic → Use UCS
● Unknown solution depth, need shortest path, limited memory → Use IDDFS
● Have a heuristic, speed matters more than optimality → Use Greedy Best-First
● Have an admissible heuristic, need the guaranteed best solution → Use A*
● Need a fast local improvement, large search space, memory-constrained → Use Hill
Climbing

— End of Notes: Informed & Uninformed Search with Worked Examples —

 BACKTRACKING SEARCH
A Memory-Efficient Search Strategy in Artificial Intelligence

With Worked Case Studies for Every Major Variant

Prepared for Undergraduate Students

PART A: WHAT IS BACKTRACKING SEARCH?

Backtracking is a refined, highly memory-efficient form of Depth-First Search. Instead of generating ALL
children of a node at once (as plain DFS does), backtracking generates ONE child at a time, explores it
fully, and only generates the next child if the current path fails. When a dead-end is reached, the
algorithm 'backtracks' — undoes the last decision — and tries a different option.

📖 Key Idea
Backtracking builds a solution incrementally, one choice at a time.
At each step it checks: 'Is this partial solution still valid?'
→ If YES, continue building (go deeper)
→ If NO, abandon this path immediately and try the next option
(this is called PRUNING — it avoids wasting time on hopeless paths)

This 'check-as-you-go' approach is what makes backtracking far more

efficient than blindly generating every possible complete solution
and checking it only at the end.

Aspect Plain DFS Backtracking Search

Children generation All children generated at once Only ONE child generated at a time
Validity check Usually only at the goal After EVERY partial assignment
(pruning)
Memory usage O(b·m) O(m) — even lower, just the current
path
Typical use General graph/tree search Constraint problems: N-Queens,
Sudoku, coloring
Key data structure Stack (open list) Solution path (SL) + remaining
choices (NSL)
 📖 Backtracking Maintains Three Lists (Luger's Formulation)
SL (Solution List) — the sequence of states from start to the current state
(this is the partial solution being built)
NSL (New State List) — states generated but not yet tried
DE (Dead Ends) — states that led to failure (so we don't retry them)
CS (Current State) — always the most recent state in SL

When CS has no more valid (untried) children → POP it off SL → backtrack

to the previous state and try its NEXT untried child.

PART B: THE GENERIC BACKTRACKING ALGORITHM

function BACKTRACK(assignment, problem):

if assignment is COMPLETE:
return assignment # solution found!

var := SELECT-UNASSIGNED-VARIABLE(problem, assignment)

for value in ORDER-DOMAIN-VALUES(var, assignment, problem):

if value is CONSISTENT with assignment: # check constraints
add {var = value} to assignment # MAKE the choice
result := BACKTRACK(assignment, problem) # recurse (go deeper)
if result != FAILURE:
return result
remove {var = value} from assignment # UNDO the choice (backtrack!)

return FAILURE # no value worked — signal failure to caller

📖 Three Essential Steps in Every Backtracking Solution

1. CHOOSE — pick a value for the next variable/decision
2. CONSTRAIN — check if this choice is still valid given prior choices
3. EXPLORE/UNDO — if valid, recurse deeper; if a dead end is hit
anywhere below, UNDO this choice and try the next option

This pattern (Choose → Constrain → Explore → Undo) applies to EVERY

backtracking problem, whether it's N-Queens, Sudoku, maze-solving, or
graph coloring.

C1. Simple Backtracking — Path Finding in a Graph

The most basic form of backtracking explores a graph or tree one path at a time, abandoning
(backtracking from) any path that hits a dead end, until it finds the goal.
📖 How It Works
1. Start at the initial node; add it to the Solution List (SL)
2. From the Current State (CS = last node in SL), pick the FIRST
untried neighbor and move there (push onto SL)
3. If CS = goal → STOP, SL is the solution path
4. If CS has no untried neighbors (dead end) → mark CS as a Dead End,
remove it from SL (POP), and go back to step 2 from the new CS
5. Repeat until goal is found or all options are exhausted

function Backtrack_Graph(start, goal):

SL := [start] # solution path so far
DE := {} # dead ends
while SL is not empty:
CS := [Link]()
if CS == goal: return SL # success!
next_child := first_unvisited_neighbor(CS, SL, DE)
if next_child exists:
[Link](next_child) # go deeper
else:
[Link](CS) # mark dead end
[Link]() # BACKTRACK
return FAILURE

🧩 CASE STUDY: Robot Exploring a Cave Network

An exploration robot starts at the cave entrance E and must reach the
treasure chamber T. The cave network (children listed in the order the
robot tries them) is:

E: [A, B]
A: [C, D]
C: [] (dead end — collapsed tunnel)
D: [] (dead end — collapsed tunnel)
B: [F]
F: [T]
T: [] (treasure chamber — GOAL)

QUESTION: Using Backtracking Search, trace the robot's exploration

(including any backtracks) to find the path from E to T.

✅ STEP-BY-STEP SOLUTION
STEP 1 — Initialize: SL=[E], DE={}

STEP 2 — CS = E. Not goal. First untried neighbor = A.

SL=[E, A]

STEP 3 — CS = A. Not goal. First untried neighbor = C.

SL=[E, A, C]
STEP 4 — CS = C. Not goal. NO neighbors (dead end)!
→ Mark C as dead end: DE={C}
→ BACKTRACK: remove C from SL → SL=[E, A]

STEP 5 — CS = A again. C already tried/dead. Next untried neighbor = D.

SL=[E, A, D]

STEP 6 — CS = D. Not goal. NO neighbors (dead end)!

→ Mark D as dead end: DE={C, D}
→ BACKTRACK: remove D from SL → SL=[E, A]

STEP 7 — CS = A again. Both C and D are dead ends — NO untried

neighbors left for A either!
→ Mark A as dead end: DE={C, D, A}
→ BACKTRACK: remove A from SL → SL=[E]

STEP 8 — CS = E again. A is now a dead end. Next untried neighbor = B.

SL=[E, B]

STEP 9 — CS = B. Not goal. First untried neighbor = F.

SL=[E, B, F]

STEP 10 — CS = F. Not goal. First untried neighbor = T.

SL=[E, B, F, T]

STEP 11 — CS = T. GOAL REACHED! ✅

FINAL ANSWER:
Path Found: E→B→F→T
Dead Ends Hit: C, D, A (entire A-branch was abandoned)
Total Backtracks: 3

NOTE: The robot wasted moves exploring A→C and A→D before giving up
on the entire A-branch — this is the cost of backtracking. But notice
it never had to remember the ENTIRE cave map in memory simultaneously,
just the current path (SL) and the dead-end list — extremely memory
efficient, even though some exploration is wasted.

Property Simple Backtracking

Complete? ✅ Yes (for finite graphs with dead-end/cycle tracking)
Optimal? ❌ No (returns the first solution found, not necessarily
shortest)
Time Complexity O(bᵐ) — same worst case as DFS
Space Complexity O(m) — only the current path + dead-end list — best
possible
C2. Backtracking with Constraint Checking — N-Queens
This variant adds a CONSISTENCY CHECK at every step: before committing to a choice, we verify it
doesn't violate any constraint with PREVIOUSLY made choices. This is the classic form used for
puzzles like N-Queens, Sudoku, and map coloring.

📖 How It Works
1. Process one variable at a time (e.g., one column of the chessboard)
2. For the current variable, try each possible value in turn
3. CHECK: does this value conflict with any EARLIER assignment?
→ If conflict → reject this value, try the next one
→ If no conflict → assign it and recurse to the NEXT variable
4. If ALL values for a variable fail → backtrack to the PREVIOUS
variable and try its next value
5. If all variables are successfully assigned → SOLUTION FOUND

function NQueens_Backtrack(board, col, N):

if col == N:
return board # all N queens placed successfully!
for row = 0 to N-1:
if is_safe(board, row, col): # check constraints
board[col] := row # CHOOSE
result := NQueens_Backtrack(board, col+1, N) # EXPLORE
if result != FAILURE:
return result
board[col] := EMPTY # UNDO (backtrack)
return FAILURE

function is_safe(board, row, col):

for c = 0 to col-1:
r := board[c]
if r == row: return False # same row
if abs(r-row) == abs(c-col): return False # same diagonal
return True

🧩 CASE STUDY: The 4-Queens Problem

Place 4 queens on a 4×4 chessboard such that NO two queens attack each
other (no two in the same row, column, or diagonal).

We place one queen per COLUMN (columns 0,1,2,3) and decide which ROW
(0,1,2,3) to place it in for each column.

QUESTION: Using Backtracking Search, find a valid placement of all 4

queens, showing every rejection and backtrack.

✅ STEP-BY-STEP SOLUTION
NOTATION: (col, row) — we try rows 0,1,2,3 in order for each column.
COLUMN 0: Try row 0 → no prior queens → SAFE ✅
Place Q0 at (0,0)

COLUMN 1: Try row 0 → same row as Q0 → CONFLICT ❌

Try row 1 → diagonal with Q0 (|0-1|=|0-1|) → CONFLICT ❌
Try row 2 → no conflict with Q0 → SAFE ✅
Place Q1 at (1,2)

COLUMN 2: Try row 0 → diagonal with Q1? |2-0|=2,|1-2|=1 → OK;

same row as Q0? row 0 = Q0's row → CONFLICT ❌
Try row 1 → diagonal with Q0? |0-1|=1,|0-2|=2 → OK;
diagonal with Q1? |2-1|=1,|1-2|=1 → CONFLICT ❌
Try row 2 → same row as Q1 → CONFLICT ❌
Try row 3 → check Q0: |0-3|=3,|0-2|=2 → OK;
check Q1: |2-3|=1,|1-2|=1 → CONFLICT ❌
ALL 4 rows fail for column 2! → BACKTRACK to column 1.

COLUMN 1 (retry): Try row 3 (next untried row after row 2) → check Q0:
|0-3|=3, |0-1|=1 → OK (not equal) → SAFE ✅
Replace Q1 at (1,3)

COLUMN 2: Try row 0 → check Q0(row0): same row → CONFLICT ❌

Try row 1 → check Q0: |0-1|=1,|0-2|=2→OK; check Q1: |3-1|=2,
|1-2|=1 → OK → SAFE ✅
Place Q2 at (2,1)

COLUMN 3: Try row 0 → check Q0: same row → CONFLICT ❌

Try row 1 → check Q2: same row → CONFLICT ❌
Try row 2 → check Q1: diagonal |3-2|=1,|1-2|=1 → CONFLICT ❌
Try row 3 → check Q0: |0-3|=3,|0-3|=3 → diagonal CONFLICT ❌
ALL 4 rows fail! → BACKTRACK to column 2.

COLUMN 2 (retry): No more untried rows for column 2 (0,1 tried; 2,3
also fail similarly) → BACKTRACK further to column 1.
COLUMN 1: No more untried rows (0,1,2,3 all tried) → BACKTRACK to col 0.
COLUMN 0 (retry): Try row 1 → SAFE ✅. Place Q0 at (0,1).

[Continuing the same systematic process...]

COLUMN 1: row 3 → SAFE → Q1 at (1,3)
COLUMN 2: row 0 → SAFE → Q2 at (2,0)
COLUMN 3: row 2 → check Q0:|1-2|=1,|0-3|=3 OK; Q1:|3-2|=1,|1-3|=2 OK;
Q2:|0-2|=2,|2-3|=1 OK → SAFE ✅ → Q3 at (3,2)

ALL 4 QUEENS PLACED SUCCESSFULLY! ✅

FINAL ANSWER:
Solution: Q0=(0,1), Q1=(1,3), Q2=(2,0), Q3=(3,2)
Board (row,col), '♛'=queen, '.'=empty:
col: 0 1 2 3
row0: . . ♛ .
row1: ♛ . . .
row2: . . . ♛
 row3: . ♛ . .

💡 Why This is True Backtracking (Not Plain DFS)

Notice that we did NOT generate all 4×4×4×4 = 256 possible boards and
test each one. Instead, we checked constraints AFTER EACH SINGLE
PLACEMENT and immediately rejected invalid partial boards — for
example, we never even considered placing Q2 once we knew certain
rows conflicted with Q0 or Q1. This PRUNING is what makes backtracking
dramatically faster than naive Generate-and-Test.

Property Constraint-Checking Backtracking

Complete? ✅ Yes (will find a solution if one exists)
Optimal? N/A (typically just need ANY valid solution, not a 'best'
one)
Time Complexity Much better than brute force due to early pruning
Space Complexity O(N) — only current partial assignment is stored

C3. Backtracking with Forward Checking — Map Coloring

This advanced variant looks AHEAD after every assignment: it eliminates now-invalid values from the
domains of FUTURE (unassigned) variables immediately. This catches failures even earlier than basic
constraint checking, often avoiding deep backtracks entirely.

📖 How Forward Checking Works

1. Maintain a DOMAIN (list of legal remaining values) for every variable
2. When a variable X is assigned a value:
→ For every UNASSIGNED variable Y connected to X by a constraint,
REMOVE from Y's domain any value that conflicts with X's assignment
3. If any variable's domain becomes EMPTY → immediate failure →
backtrack right away (don't even bother trying to assign further)
4. Otherwise, move on to the next variable

Forward checking turns 'discover the conflict later' into 'discover

the conflict the moment it becomes inevitable' — saving wasted work.

function Backtrack_ForwardCheck(assignment, domains, problem):

if assignment is complete: return assignment
var := SELECT-UNASSIGNED-VARIABLE(problem, assignment)
for value in domains[var]:
if value is consistent with assignment:
assign var = value
saved_domains := COPY(domains) # for undo later
ok := True
for neighbor in CONSTRAINT-NEIGHBORS(var):
 if neighbor is unassigned:
remove inconsistent values from domains[neighbor]
if domains[neighbor] is EMPTY:
ok := False # forward check FAILS
if ok:
result := Backtrack_ForwardCheck(assignment, domains, problem)
if result != FAILURE: return result
domains := saved_domains # UNDO domain changes
unassign var
return FAILURE

🧩 CASE STUDY: Coloring a Map of Four Neighboring Districts

Four districts — P, Q, R, S — must each be colored RED, GREEN, or BLUE
such that no two ADJACENT districts share the same color. The
adjacency (constraint) relationships are:

P—Q (P and Q are adjacent)

P—R (P and R are adjacent)
Q—R (Q and R are adjacent)
Q—S (Q and S are adjacent)
R—S (R and S are adjacent)

Initial domain for every district: {Red, Green, Blue}

Assignment order: P, Q, R, S

QUESTION: Using Backtracking with Forward Checking, find a valid

coloring, showing how each assignment shrinks the domains of
unassigned neighbors.

✅ STEP-BY-STEP SOLUTION
STEP 0 — Initial domains:
P:{R,G,B} Q:{R,G,B} R:{R,G,B} S:{R,G,B}

STEP 1 — Assign P = Red (first value in domain)

Forward check neighbors of P (which are Q and R):
Q loses Red → Q:{G,B}
R loses Red → R:{G,B}
Domains now: P=Red(fixed) Q:{G,B} R:{G,B} S:{R,G,B}
No empty domains → continue ✅

STEP 2 — Assign Q = Green (first value in Q's domain)

Forward check neighbors of Q (which are P✓already assigned, R, S):
R loses Green → R:{B} (R had {G,B}, now just {B})
S loses Green → S:{R,B}
Domains now: P=Red Q=Green R:{B} S:{R,B}
No empty domains → continue ✅

STEP 3 — Assign R: domain is now just {B} → must assign R = Blue

Forward check neighbors of R (P✓, Q✓ already assigned, and S):
S loses Blue → S:{R,B} minus {B} → S:{R}
 Domains now: P=Red Q=Green R=Blue S:{R}
No empty domains → continue ✅

STEP 4 — Assign S: domain is now just {R} → must assign S = Red

Check: is S=Red consistent? S is adjacent to Q(Green) and R(Blue)
only — no conflict with Red → SAFE ✅
All variables assigned → SOLUTION FOUND! ✅

FINAL ANSWER:
P = Red, Q = Green, R = Blue, S = Red

VERIFY constraints: P≠Q (Red≠Green)✓ P≠R (Red≠Blue)✓

Q≠R (Green≠Blue) ✓ Q≠S (Green≠Red) ✓
R≠S (Blue≠Red)✓ — ALL constraints satisfied!

💡 Why Forward Checking Helped Here

Notice that by STEP 3, R's domain had already shrunk to a SINGLE
value {B} purely from the ripple effects of P and Q's assignments —
we didn't even need to 'try and fail' on R=Red or R=Green; forward
checking had ALREADY eliminated them. Likewise S was forced down to
{R} before we even looked at it. This is far more efficient than
plain backtracking, which would only discover these conflicts when
it actually attempted (and failed at) each invalid value.

Property Backtracking with Forward Checking

Complete? ✅ Yes
Optimal? N/A (finds any valid solution satisfying all constraints)
Time Complexity Better than plain backtracking — detects failure earlier
Space Complexity O(N·D) — stores current domains for all N variables, D
= domain size

PART F: SUMMARY — BACKTRACKING VARIANTS AT

A GLANCE

Variant Strategy Case Study Used Key Strength

Simple Backtracking Try paths one at a time; Robot exploring a cave Lowest memory usage —
backtrack on dead end network O(path length)
With Constraint Checking Reject invalid choices the 4-Queens problem Prunes invalid branches
instant they're made immediately
With Forward Checking Propagate effects to future 4-district map coloring Detects failure even
variables' domains before it happens
F.1 Backtracking vs. Other Search Strategies
Aspect Plain DFS Backtracking Backtracking +
Forward Check
Validity Check Timing Only at goal After each assignment Predictively, before
assignment
Memory O(b·m) O(m) O(N·D)
Best Used For Generic graphs Constraint problems (N- Large CSPs with many
Queens, Sudoku) constraints
Failure Detection Late (at goal check) Immediate (local check) Earliest (propagated
check)

F.2 When to Use Backtracking

● Problem can be built incrementally, one decision/variable at a time
● Each partial decision can be checked for validity before continuing
● Memory is limited and storing the full search tree is infeasible
● The problem is a classic CSP (e.g., N-Queens, Sudoku, graph coloring, scheduling)
● You want correctness guarantees (backtracking with proper dead-end tracking is complete)

— End of Notes: Backtracking Search with Worked Examples —