Design and Analysis of Algorithms

(DAA)
Topic : Backtracking

Krishnendu Jana
SC2131
May 13, 2026
Introduction to Backtracking
What is Backtracking?

Definition: Backtracking is an algorithmic technique for solving problems recursively

by trying to build a solution incrementally. It uses exhaustive search to find all
possible solutions.

2/92
What is Backtracking?

Definition: Backtracking is an algorithmic technique for solving problems recursively

by trying to build a solution incrementally. It uses exhaustive search to find all
possible solutions.
Core Idea:

• Backtracking = Systematic search + Undo choices

• Typically employs Depth-First Search (DFS) to traverse the solution space.
• Relies on Pruning to avoid meaningless search paths.

2/92
Figure 1: Preorder Traversal to Find Nodes

3/92
Example 1: Basic Search (No Explicit Backtrack)

Problem: Search and record all nodes with value 7 in a binary tree.

This is a standard Pre-order Traversal.

Python Implementation: Observation:

• State is implicit (call stack).
def pre_order(root):
if root is None: • No "undo" operation is
return required because we are not
if [Link] == 7: maintaining a mutable path
# Record solution state.
[Link](root)
pre_order([Link])
pre_order([Link])

4/92
Example 2: Adding “Attempt” and “Backtrack”

Problem: Find nodes with value 7, and record the path from the root.
Path Recording: Key Operations:
• Attempt: Add node to path.
def pre_order(root):
if root is None: • Backtrack: Remove node
return from path to restore previous
[Link](root) # Attempt: make a choice state before returning.
if [Link] == 7:
[Link](list(path)) # Record solution
pre_order([Link])
pre_order([Link])
[Link]() # Backtrack: undo the choice

5/92
Trace: Example 2

6/92
Trace: Example 2

7/92
Trace: Example 2

8/92
Trace: Example 2

9/92
Trace: Example 2

10/92
Trace: Example 2

11/92
Trace: Example 2

12/92
Trace: Example 2

13/92
Trace: Example 2

14/92
Trace: Example 2

15/92
Trace: Example 2

16/92
Example 3: Adding “Pruning” (Constraints)

Problem: Find paths to 7, but paths cannot contain nodes with value 3.
Pruning Implementation: What is Pruning?
• A vivid term for cutting off
def pre_order(root):
search branches that violate
# Pruning: check constraint
constraints.
if root is None or [Link] == 3:
return • Avoids exploring subtrees
# Attempt rooted at nodes with value 3.
[Link](root) • Significantly improves
if [Link] == 7: efficiency.
[Link](list(path))
pre_order([Link])
pre_order([Link])
# Backtrack
[Link]() 17/92
Example 3

Figure 2: Adding and Pruning (Constraints)

18/92
Algorithm Framework
General Backtracking Framework

We can abstract the logic into a generic framework based on State and Choices.

Algorithm 1 Backtracking Algorithm Template

1: procedure Backtrack(state, choices, res)
2: if isSolution(state) then
3: recordSolution(state, res)
4: return ▷ Stop or continue based on problem
5: end if
6: for choice ∈ choices do
7: if isValid(state, choice) then ▷ Pruning check
8: makeChoice(state, choice) ▷ Attempt
9: Backtrack(state, choices, res)
10: undoChoice(state, choice) ▷ Backtrack
11: end if
12: end for
19/92
13: end procedure
Terminology and Complexity
Common Terminology (Context: Example 3)

Term Definition Example Context

Solution An answer satisfying problem condi- Paths to nodes with value 7.

tions.
Constraint Conditions limiting feasibility (used Paths cannot contain 3.
for pruning).
State The current situation (choices made The current path list.
so far).
Attempt Exploring by making a choice and up- Appending node to path.
dating state.
Backtrack Undoing choice to return to previous Popping node from path.
state.

20/92
Advantages and Limitations

Advantages Limitations
• Finds all possible solutions. • Time: Can be exponential O(2n ) or
• With proper pruning, highly efficient factorial O(n!) without pruning.
for constraint satisfaction. • Space: High memory usage for
• Conceptually clear (DFS based). recursive call stack O(n).

Optimization Strategies:

1. Pruning: Skip paths guaranteed not to yield solutions.

2. Heuristic Search: Prioritize paths most likely to succeed.

21/92
Typical Applications
Typical Backtracking Problems

Search Problems Constraint Satisfaction Combinatorial

• Permutations • N-Queens Problem Optimization
• Subsets / Combinations • Sudoku Solver • 0-1 Knapsack1
• Subset Sum • Graph Coloring • Traveling Salesman
Problem (TSP)
• Maximum Clique (In
Graph Theory)

1
Note: For optimization problems, Dynamic Programming or Heuristics (Genetic Algorithms) are often
preferred over pure Backtracking.

22/92
Permutations Problem
What is the Permutations Problem?

Finding all possible arrangements of elements in a given collection.

Input Array All Permutations

[1] [1]
[1, 2] [1, 2], [2, 1]
[1, 2, 3] [1, 2, 3], [1, 3, 2], [2, 1, 3],
[2, 3, 1], [3, 1, 2], [3, 2, 1]

23/92
Case 1: Distinct Elements (Concept)

Problem: Given an integer array with no duplicate elements, return all possible
permutations.

Backtracking Perspective:

• Choices: All elements in the input array.

• State: Elements that have been chosen so far (must be unique).
• Process: Unfolded into a recursion tree. Each node represents the current state.
Reaching a leaf node (after n choices) means a permutation is complete.

24/92
Recursion tree of permutations

25/92
Case 1: Pruning Duplicate Choices

To ensure each element is chosen only once, we introduce a boolean array selected:

• After choosing choices[i]: Set selected[i] = True.

• During traversal (Pruning): Skip all nodes where selected[i] == True.

Impact on Search Space:

• Reduces the search space size from O(nn ) to O(n!).

26/92
Pruning Duplicate Choices

27/92
Case 1: Code Implementation

def backtrack(state, choices, selected, res):

"""Backtracking algorithm: Permutations I"""
# When state length equals elements, record solution
if len(state) == len(choices):
[Link](list(state))
return

# Traverse all choices

for i, choice in enumerate(choices):
# Pruning: do not allow repeated selection
if not selected[i]:
# Attempt: make choice, update state
selected[i] = True
[Link](choice)
28/92
Case 1: Code Implementation(Continue...)

backtrack(state, choices, selected, res)

# Backtrack: undo choice

selected[i] = False
[Link]()

def permutations_i(nums):
res = []
backtrack([], nums, [False] * len(nums), res)
return res

29/92
Case 2: Duplicate Elements (The Problem)

Problem: Given an array that may contain duplicates, return all unique permutations.

Example: Input [1, 1, 2] (denoting duplicates as 1 and 1̂)

• Choosing 1 in the first round vs choosing 1̂ in the first round is equivalent.

• The previous code will generate duplicate permutations (half of them are
redundant).

Inefficient Approach
Using a Hash Set to deduplicate the final results is not elegant. The branches
generating duplicates are unnecessary and should be pruned early.

30/92
Case with Duplicate Elements

31/92
Case 2: Pruning Equal Elements

Goal: Ensure multiple equal elements are chosen only once in a certain round of
choices.

Solution: Introduce a local Hash Set duplicated inside each round of choices (inside
the for loop of the backtrack function).

• Before making a choice, check if choice is already in duplicated.

• If it is, skip it (Prune).
• If not, add it to duplicated and proceed with the Attempt/Backtrack.

Note: The duplicated set is initialized per function call, whereas selected exists
throughout the entire search process.

32/92
Pruning Equal Elements

33/92
Case 2: Code Implementation

def backtrack(state, choices, selected, res):

"""Backtracking algorithm: Permutations II"""
if len(state) == len(choices):
[Link](list(state))
return

# Initialize hash set for this round of choices

duplicated = set()
for i, choice in enumerate(choices):
# Pruning: skip selected AND skip equal elements
if not selected[i] and choice not in duplicated:
# Record selected element value in this round
[Link](choice)

34/92
Case 2: Code Implementation(Continue...)

# Attempt
selected[i] = True
[Link](choice)

backtrack(state, choices, selected, res)

# Backtrack
selected[i] = False
[Link]()

def permutations_ii(nums):
res = []
backtrack([], nums, [False] * len(nums), res)
return res
35/92
Complexity Analysis

Assuming n distinct elements, there are n! permutations.

• Time Complexity: O(n! · n)

• Generating n! states.
• Copying a list of length n takes O(n) time when recording results.

• Space Complexity: O(n2 )

• Recursion depth max n → stack frame space O(n).
• selected array takes O(n) space.
• At most n duplicated sets exist simultaneously → O(n2 ) space.

36/92
Comparison of Two Pruning Methods

selected Array duplicated Set

Objective Prevent an element from ap- Ensure equal elements are cho-
pearing repeatedly in state. sen only once per round.

Scope Global throughout the entire Local to a single round of

search process. choices (single function call).

Action Prune branches of already se- Prune branches of identical val-

lected indices. ues in the current loop.

Key Takeaway: Every node in the recursion tree represents a choice. The path from
root to leaf forms a permutation. Both prunings act at different levels of this tree!
37/92
Comparison of Two Pruning Methods

Figure 3: Effective scope of two pruning conditions

38/92
Max Sub-array Sum
The maximum-subarray problem
• What is subarray?
• Application : Stocks

13-05-2026 Divide and Conquer 11

38/92
The maximum-subarray problem

The change in stock prices as a maximum-subarray problem.

Here, the subarray A : 11 , with sum 43, has the greatest sum of
any contiguous subarray of array A.

13-05-2026 Divide and Conquer 12

38/92
The maximum-subarray problem - Approach
1. Brute force : Using two loops (Time Complexity : 𝑂 𝑛2 ) ?
2. Using Divide and Conquer Technique (Time Complexity :
𝑂 𝑛 ⋅ log(𝑛)
3. Kadane’s Algorithm (Time Complexity : 𝑂 𝑛 )

13-05-2026 Divide and Conquer 13

38/92
The maximum-subarray problem – Divide and
Conquer

(a) Possible locations of subarrays of A[low : high] entirely in A[low : mid]

entirely in A[mid +1 : high], or crossing the midpoint mid.

(b) Any subarray of A[low : high], crossing the midpoint comprises two
subarrays A[i : : mid] and A[mid + 1 : j] where low <= i<= mid and mid <= j<=
high.

13-05-2026 Divide and Conquer 14

38/92
The maximum-subarray problem – Divide and
Conquer Algo

13-05-2026 Divide and Conquer 15

38/92
Dry Run

13-05-2026 Divide and Conquer 16

38/92
13-05-2026 Divide and Conquer 17
38/92
13-05-2026 Divide and Conquer 18
38/92
13-05-2026 Divide and Conquer 19
38/92
13-05-2026 Divide and Conquer 20
38/92
13-05-2026 Divide and Conquer 21
38/92
13-05-2026 Divide and Conquer 22
38/92
13-05-2026 Divide and Conquer 23
38/92
13-05-2026 Divide and Conquer 24
38/92
13-05-2026 Divide and Conquer 25
38/92
13-05-2026 Divide and Conquer 26
38/92
13-05-2026 Divide and Conquer 27
38/92
The maximum-subarray problem – Optimal
Solution (Kadane’s Algorithm) [O(n) Time]

13-05-2026 Divide and Conquer 28

38/92
N-Queens Problem
The N-Queens Problem

Problem Statement: Place N chess queens on an N × N chessboard so that no two

queens threaten each other.

Constraints:

• No two queens share the same Row.

• No two queens share the same Column.
• No two queens share the same Diagonal (both main and anti-diagonals).

Goal: Find all distinct solutions for a given N.

39/92
Visualization: A Solution for N = 4

State Representation:
We can represent the board state using a
1D array state of length N.

3 Q state[row] = col
2 Q Example Solution:
1 Q • Row 0 → Col 1
0 Q • Row 1 → Col 3
0 1 2 3 • Row 2 → Col 0
• Row 3 → Col 2

Array: [1, 3, 0, 2]

40/92
Strategy: Row-by-Row Backtracking

Approach: Since each row must contain exactly one queen, we can iterate through
rows 0 to N − 1.

1. State: Current row index and the placement of queens in previous rows.
2. Choices: Try placing a queen in columns 0 to N − 1 for the current row.
3. Pruning (Constraint Check): Before placing a queen at (row, col), check:
• Is the column col already occupied? (Check state)
• Is the diagonal attacked? (Check previously placed queens)
4. Base Case: If row == N, we have placed N queens successfully. Record solution.

41/92
Constraint Checking Logic

Checking Diagonals:
Given a new queen position (r , c) and an existing queen at (r ′ , c ′ ):

• Main Diagonal Conflict: The difference between row and column indices is
constant.
r − c = r′ − c′
• Anti-Diagonal Conflict: The sum of row and column indices is constant.

r + c = r′ + c′

Optimization Tip: Instead of iterating through previous queens every time, we can use
sets or boolean arrays to track occupied columns, diagonals, and anti-diagonals in O(1)
time.
42/92
Implementation: Python Code

def solve_n_queens(n):
solutions = []
state = [-1] * n # state[row] = col
def backtrack(row, state):
if row == n:
[Link](state[:]) # Record solution
return
for col in range(n):
if is_valid(row, col, state):
state[row] = col # Attempt
backtrack(row + 1, state)
state[row] = -1 # Backtrack (cleanup)
backtrack(0, state)
return solutions
43/92
Implementation: The Validation Function

def is_valid(row, col, state):

# Check all previous rows
for r in range(row):
c = state[r]
# 1. Check Column Conflict
if c == col: return False
# 2. Check Diagonal Conflict
# Main Diagonal: row - col == r - c
if (row - col) == (r - c): return False
# 3. Check Anti-Diagonal Conflict
# row + col == r + c
if (row + col) == (r + c): return False
return True

44/92
Complexity Analysis

Time Complexity:

• In the worst case, we explore a significant portion of the N N state space.

• Pruning significantly reduces this. For N-Queens, it is roughly O(N!).
• The validation function adds a factor of O(N) if not optimized with sets.
• Total: O(N! · N) or slightly better with optimized checks.

Space Complexity:

• Recursion Stack: Depth is N.

• State Array: Size N.
• Total: O(N) (excluding space for storing output solutions).

45/92
Rat in a Maze
The Rat in a Maze Problem

Problem Statement: A rat is placed at the starting position of a maze (usually

top-left, (0, 0)). It must find a path to the exit (usually bottom-right, (N − 1, N − 1)).

The Maze:

• Represented as an N × N binary matrix.

• 0: Wall or blocked cell (Red).
• 1: Open path (White/Green).

Movement Constraints: The rat can usually move in four directions: Up, Down,
Left, and Right. (Some variations restrict to only Right and Down).

46/92
Visualization: The Grid

Input Matrix:
Start
1 0 0 0
 
1 1 0 1
 
0 1 0 0
 

1 1 1 1

Output: The path coordinates.

Exit
(0,0) -> (1,0) -> ...

47/92
Backtracking Strategy

Algorithm Logic:

1. Base Case: If the current position is the destination (N − 1, N − 1), return True.
2. Check Validity: Is the current cell (x, y) within bounds and not a wall
(maze[x][y] == 1)?
3. Attempt: Mark current cell as part of the solution path.
4. Recurse: Recursively call the function for all 4 directions:
• Move Forward (Right)
• Move Down
• Move Backward (Left)
• Move Up
5. Backtrack: If none of the moves lead to a solution, unmark the current cell (set
to 0 or "visited") and return False.

48/92
Handling Visited Cells

Critical Issue: In a maze where movement is allowed in all 4 directions, the rat might
get stuck in an infinite loop (going back and forth between two cells).

Solutions:

1. Auxiliary Matrix: Maintain a separate visited[N][N] boolean matrix.

• Mark visited[x][y] = True when entering.
• Mark visited[x][y] = False when backtracking.

2. Mutating Input (In-Place): Temporarily set maze[x][y] = 0 to block re-entry.

• Restore it to 1 during the backtrack step.
• Useful if you want to save memory.

49/92
Implementation: Python Code

def solve_maze(maze):
n = len(maze)
# Solution matrix initialized to 0
sol = [[0 for _ in range(n)] for _ in range(n)]
if backtrack(maze, 0, 0, sol):
return sol
else:
return "No Solution Found"
def is_safe(maze, x, y):
n = len(maze)
# Check bounds and if cell is open (1)
return 0 <= x < n and 0 <= y < n and maze[x][y] == 1

50/92
Implementation: Recursive Function

def backtrack(maze, x, y, sol):

n = len(maze)
# Base Case: Reached destination?
if x == n-1 and y == n-1 and maze[x][y] == 1:
sol[x][y] = 1
return True
if is_safe(maze, x, y):
# Mark current cell as part of solution path
sol[x][y] = 1
# Move Right (x, y+1)
if backtrack(maze, x, y+1, sol): return True
# Move Down (x+1, y)
if backtrack(maze, x+1, y, sol): return True

51/92
Implementation: Backtracking Step

# Move Left (x, y-1)

if backtrack(maze, x, y-1, sol): return True
# Move Up (x-1, y)
if backtrack(maze, x-1, y, sol): return True

# BACKTRACK: Unmark (x, y)

sol[x][y] = 0
return False
return False

Note: The order of moves (Right, Down, Left, Up) affects the path found, but not the
solvability.

52/92
Complexity Analysis

2
Time Complexity: O(2N ) (Upper Bound)

• Theoretically, we need to try all possible paths.

2
• A loose upper bound is O(4N ) because each cell has 4 choices.
• However, backtracking prunes invalid paths early, making it faster in practice.

Space Complexity: O(N 2 )

• Output Matrix: O(N 2 ) to store the path.

• Recursion Stack: Depth can be up to N 2 in the worst case (snake-like path).

53/92
Variations of the Problem

1. Shortest Path:
• Backtracking finds a path, not necessarily the shortest.
• Use Breadth-First Search (BFS) to find the shortest path in an unweighted maze.

2. Weighted Mazes:
• If cells have costs, use Dijkstra’s Algorithm or A* Search.

3. Multiple Paths:
• Modify the code to continue searching after finding the first solution to count all
possible paths.

54/92
Graph Coloring Problem
The Graph Coloring Problem

Problem Statement: Given an undirected graph G = (V , E ) and an integer M,

determine if it is possible to assign one of M colors to each vertex such that no two
adjacent vertices share the same color.

Key Concepts:

• Valid Coloring: For every edge (u, v ) ∈ E , color [u] ̸= color [v ].

• Chromatic Number: The minimum number of colors needed to color a graph
(χ(G )).
• Decision Problem: Is the graph M-colorable?

55/92
Visualization: Example Graph

Uncolored Graph Valid Coloring (M = 3)

0 0

1 2 1 2

3 3

Solution Array: color = [0, 1, 2, 1] (Indices represent colors)

56/92
Backtracking Strategy

Approach: We assign colors to vertices one by one, starting from vertex 0.

1. State: The current assignment of colors to vertices 0 to v − 1.

2. Choices: For the current vertex v , try all colors from 0 to M − 1.
3. Pruning (Constraint Check): Before assigning color c to vertex v :
• Check all adjacent vertices of v .
• If any neighbor already has color c, skip this color.
4. Base Case: If all V vertices are colored, return True.
5. Backtrack: If no color can be assigned to vertex v safely, return False to trigger
backtracking to the previous vertex.

57/92
Implementation: Safety Check

Logic: Iterate through the adjacency matrix/list to check neighbors.

def is_safe(v, graph, color, c):

"""
Check if color ’c’ can be assigned to vertex ’v’.
graph: Adjacency matrix (list of lists).
color: Current list of assigned colors (-1 means uncolored).
"""
for i in range(len(graph)):
# Check if i is adjacent to v AND has the same color c
if graph[v][i] == 1 and color[i] == c:
return False
return True

58/92
Implementation: Recursive Function

def graph_coloring_util(graph, m, color, v):

n = len(graph)
# Base Case: All vertices colored
if v == n:
return True

# Try all colors from 0 to m-1

for c in range(m):
if is_safe(v, graph, color, c):
color[v] = c # Attempt

# Recurse for next vertex

if graph_coloring_util(graph, m, color, v + 1):
return True
59/92
Implementation: Driver Function

def graph_coloring(graph, m):

n = len(graph)
# Initialize all vertices as uncolored (-1)
color = [-1] * n

if not graph_coloring_util(graph, m, color, 0):

print("Solution does not exist")
return False

# Print solution
print("Solution found:")
for v in range(n):
print(f"Vertex {v} -> Color {color[v]}")
return True
60/92
Graph Coloring: Step-by-Step Trace

Graph: 4 Vertices (Diamond Shape). M = 3 Colors.

Adjacency List:

• 0: connected to {1, 2, 3}
• 1: connected to {0, 2}
• 2: connected to {0, 1, 3}
• 3: connected to {0, 2}

Color Palette:

• Color 0 (Blue)
• Color 1 (Green)
• Color 2 (Orange)

61/92
Trace Step 1: Coloring Vertex 0

Action:
• Current Vertex: v = 0
0 • Try Color 0.
• is_safe? No neighbors colored →
Safe.
1 2
State Array:

3 0 1 2 3
0 - - -

Recurse(1)

62/92
Trace Step 2: Coloring Vertex 1

Action:
• Current Vertex: v = 1

0 • Neighbors: {0}. Color of 0 is 0.

• Try Color 0? Conflict with 0.
• Try Color 1? Safe.
1 2
State Array:
3 0 1 2 3
0 1 - -

Recurse(2)

63/92
Trace Step 3: Coloring Vertex 2

Action:
• Current Vertex: v = 2
• Neighbors: {0, 1}. Colors: {0, 1}.
0 • Try Color 0? Conflict with 0.
• Try Color 1? Conflict with 1.
1 2 • Try Color 2? Safe.

State Array:
3
0 1 2 3
0 1 2 -

Recurse(3)

64/92
Trace Step 4: Coloring Vertex 3

Action:
• Current Vertex: v = 3
• Neighbors: {0, 2}. Colors: {0, 2}.
0
• Try Color 0? Conflict with 0.
• Try Color 1? Neighbor 0 is 0,
1 2 Neighbor 2 is 2. Safe.

State Array:
3
0 1 2 3
0 1 2 1

65/92
Trace Step 5: Solution Found

1 2

Success! All vertices colored. Base case v == 4 reached.

Final Coloring: [0, 1, 2, 1]

66/92
Complexity Analysis

Time Complexity: O(M V )

• There are V vertices.

• Each vertex has M choices of color.
• Branching factor is M, depth is V .
• Safety check adds a factor of V .
• Total: O(M V · V ).

Space Complexity: O(V )

• Color Array: O(V ) space to store assignments.

• Recursion Stack: Depth is V .

67/92
Applications of Graph Coloring

1. Scheduling Problems:
• Vertices represent exams/tasks.
• Edges represent conflicts (e.g., same student).
• Colors represent time slots.

2. Register Allocation:
• Vertices represent variables in code.
• Edges represent variables alive at the same time.
• Colors represent CPU registers.

3. Map Coloring:
• Coloring geographical maps such that no two adjacent regions share a color (e.g.,
The Four Color Theorem).

68/92
Adversarial Search - AI Algorithms
Introduction to Adversarial Search

Definition: Adversarial search is used in multi-agent environments where agents have

conflicting goals. It is the core of Game Playing AI.

Key Characteristics:

• Deterministic: The outcome of a move is certain (no dice).

• Perfect Information: Both players see the full board state (e.g., Chess,
Tic-Tac-Toe, Go).
• Zero-Sum: One player’s gain is exactly the other player’s loss.

Goal: Find the optimal move for a player assuming the opponent also plays optimally.

69/92
Minimax Algorithm
The Minimax Algorithm

Concept: A recursive algorithm to choose the best move for a player assuming the
opponent plays optimally.

MAX Player (Us) MIN Player (Opponent)

• Wants to maximize the score. • Wants to minimize the score.
• Chooses the move with the highest • Chooses the move with the lowest
value. value.

Strategy:

1. Generate the game tree down to a certain depth (or terminal state).
2. Evaluate leaf nodes using a heuristic function.
3. Propagate values up the tree: Min nodes take min, Max nodes take max.

70/92
Minimax: Implementation

def minimax(depth, nodeIndex, isMax, scores):

if depth == 0:
return scores[nodeIndex]
if isMax: # Max Player
best = -infinity
best = max(best,
minimax(depth-1, nodeIndex*2, False, scores),
minimax(depth-1, nodeIndex*2+1, False, scores))
return best
else: # Min Player
best = infinity
best = min(best,
minimax(depth-1, nodeIndex*2, True, scores),
minimax(depth-1, nodeIndex*2+1, True, scores))
return best 71/92
Trace Setup: The Game Tree

Goal: Determine the optimal move for the Root (MAX player).

MAX

MIN ? ? MIN

3 5 6 9

Rule: MIN Nodes choose the minimum of children.

MAX Nodes choose the maximum of children.
72/92
Trace Step 1: Evaluate Left Subtree

Processing Node B (MIN):

1. Look at children: {3, 5}.
? 2. Logic: min(3, 5).
3. Result: 3.
Value propagated up.
3 ?

3 5 6 9

73/92
Trace Step 2: Evaluate Right Subtree

Processing Node C (MIN):

1. Look at children: {6, 9}.
? 2. Logic: min(6, 9).
3. Result: 6.
Value propagated up.
3 6

3 5 6 9

74/92
Trace Step 3: Evaluate Root (MAX)

Processing Root (MAX):

1. Look at children: {3, 6}.
6 2. Logic: max(3, 6).
3. Result: 6.
Optimal value found!
3 6

3 5 6 9

75/92
Trace Summary: Final Decision

Final Outcome:
• The Root (MAX) chooses the branch
leading to value 6.
6 • This corresponds to choosing the
Right Move.
Path

3 6 Rational Play:
• MAX chooses 6.
3 5 6 9 • If MIN plays optimally, game value is 6.
• (If MIN made a mistake and picked 9,
MAX would still be happy, but we
cannot assume mistakes).

76/92
Complexity of Minimax

Let m be the maximum depth of the tree and b be the branching factor.

Time Complexity: O(b m )

• Every node in the tree is visited.

• Exponential growth makes it infeasible for complex games like Chess
(b ≈ 35, m ≈ 100).

Space Complexity: O(b · m) or O(m)

• Depends on implementation (DFS traversal usually takes linear space for stack).

77/92
Alpha-Beta Pruning
Alpha-Beta Pruning

Definition: An optimization technique for the Minimax algorithm. It reduces the

number of nodes evaluated by "pruning" branches that cannot possibly influence the
final decision.

Key Variables:
• α (Alpha): The best (highest) value that the MAX player can guarantee at that
level or above.
• β (Beta): The best (lowest) value that the MIN player can guarantee at that
level or above.

Pruning Condition:

If α ≥ β, prune the remaining children (stop exploring).

78/92
Alpha-Beta: Implementation

def alphabeta(depth, nodeIndex, isMax, scores, alpha, beta):

if depth == 0:
return scores[nodeIndex]
if isMax:
best = -infinity
for i in range(2): # 2 children
val = alphabeta(depth-1, nodeIndex*2+i, False,
scores, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha: break # Prune
return best

79/92
Alpha-Beta: Implementation (Continued)

else:
best = infinity
for i in range(2):
val = alphabeta(depth-1, nodeIndex*2+i, True,
scores, alpha, beta)

best = min(best, val)

beta = min(beta, best)
if beta <= alpha: break # Prune
return best

80/92
Alpha-Beta Pruning: Step-by-Step Trace

Initial State:

• Root (MAX): Starts with α = −∞, β = +∞.

• Goal: Find the value for the Root node.

α−∞
β+∞

α−∞ MAX α−∞

β+∞ β+∞

MIN MIN
3 5 2 ?

81/92
Step 1: Evaluate Left Branch

Process Node A (MIN):

1. Child 3: β = min(∞, 3) = 3.
α=3 2. Child 5: β = min(3, 5) = 3.
β+∞ 3. Returns 3.
returns 3 Update Root (MAX):
α−∞
... α = max(−∞, 3) = 3.
β=3

3 5 2 ?

82/92
Step 2: Explore Right Branch (Pruning!)

Process Node B (MIN):

1. Inherits α = 3 from Root.
2. Child 2: β = min(∞, 2) = 2.
Check Condition:
α=3
Is α(3) ≥ β(2)?
β+∞
YES! Prune remaining children.
returns 2
α=3 Why?
...
β=2 Root wants ≥ 3. Node B offers ≤ 2.
Root will never choose B.

3 5 2 X

83/92
Step 3: Final Decision

Val: 3

Optimal

3 ≤2

3 5 2 X

Result: The algorithm visited 4 nodes instead of 6.

The value ? (Node B’s sec-
ond child) was never calculated.

84/92
Effectiveness of Pruning

Complexity Analysis:

• Worst Case: O(b m )

• Moves are ordered such that no pruning occurs.

• Best Case: O(b m/2 )

• Perfect move ordering (best moves checked first).
• Effectively doubles the searchable depth!

Practical Note: In complex games like Chess, Alpha-Beta pruning is essential.

Without it, calculating 5-6 moves ahead would take too long. With it, modern engines
can look 10+ moves deep.

85/92
Coin Row Game using Minimax
Problem Statement: Coin Row Game

The Game: Two players play a game with a row of n coins of values v1 , v2 , . . . , vn .
Rules:

1. Players alternate turns.

2. In each turn, a player picks either the first or last coin from the row.
3. The picked coin is removed from the row.
4. The game ends when no coins are left.

Objective:

• Maximize the total value of coins collected.

• Assume the opponent plays optimally.

Instance: Coin values = [8, 15, 3, 7].

86/92
Modeling as a Minimax Problem

We model this as a Zero-Sum Game between two players:

Player 1 (MAX) Player 2 (MIN)
• Starts first. • Opponent.
• Goal: Maximize the total sum • Goal: Minimize Player 1’s score
collected. (equivalent to maximizing their own
score).
State Representation:
• Defined by indices (i, j) representing the subarray v [i . . . j].
• Terminal State: i > j (No coins left).
Recursive Utility Function F (i, j):
The maximum value the current player can collect from subarray v [i . . . j].
F (i, j) = max (v [i] + min(F (i + 2, j), F (i + 1, j − 1)), v [j] + min(F (i, j − 2), F (i + 1, j − 1)
87/92
Game Tree Construction

Pick 7
Pick 8

P1

8 7

P2 P2

15 7 8 3

P1 P1 P1 P1

3 7 15 3 15 3 8 15

3 7 15 3 15 3 8 15

Note: The tree shows choices. Minimax propagates values bottom-up.

88/92
Dry Run: The Calculation (Bottom-Up)

Instance: [8, 15, 3, 7].

Step 1: Evaluate Leaf Nodes (Player 1’s Choice at Depth 2)

Left Subtree (P1 picked 8): Right Subtree (P1 picked 7):
• Rem: [15, 3, 7]. • Rem: [8, 15, 3].
• If P2 picks 15: Rem [3, 7]. P1 picks • If P2 picks 8: Rem [15, 3]. P1 picks
7. P1 Total = 8 + 7 = 15. 15. P1 Total = 7 + 15 = 22.
• If P2 picks 7: Rem [15, 3]. P1 picks • If P2 picks 3: Rem [8, 15]. P1 picks
15. P1 Total = 8 + 15 = 23. 15. P1 Total = 7 + 15 = 22.

Step 2: Min Layer (Player 2’s Choice)

• Left Min Node: P2 chooses min(15, 23) → 15. (P2 picks 15 to minimize P1’s
gain).
• Right Min Node: P2 chooses min(22, 22) → 22. (Tie). 89/92
Dry Run: Final Decision

Step 3: Max Layer (Player 1’s Choice at Root)

Player 1 compares the propagated values from the Min layer:

• Option A (Pick 8): Yields a guaranteed value of 15.
• Option B (Pick 7): Yields a guaranteed value of 22.

Optimal Strategy Calculation

Best Value = max(15, 22) = 22

Conclusion: Player 1 should pick the coin with value 7 (Right end) first.

Why? Because picking 8 allows Player 2 to take 15, reducing P1’s total. Picking 7
forces the game into a state where P1 can eventually take 15.
90/92
Optimal Strategy Summary

Optimal Play Sequence (assuming P2 plays optimally):

1. P1 (Max): Picks 7. (Rem: [8, 15, 3])

2. P2 (Min): Can pick 8 or 3.
• If P2 picks 8 (Rem: [15, 3]), P1 picks 15. Total P1 = 7 + 15 = 22.
• If P2 picks 3 (Rem: [8, 15]), P1 picks 15. Total P1 = 7 + 15 = 22.

Final Scores:

• Player 1: 22
• Player 2: 11

Result: Player 1 wins.

91/92
Reference
Reference

Stuart J. Russell and Peter Norvig, Artificial

Intelligence: A Modern Approach, Fourth Edition,
Pearson, 2020.

92/92