Complete Notes with Clear Explanations + Working Python Code Examples
UNIT II — Problem Solving Methods in AI
Complete Notes with Clear Explanations + Working Python Code Examples
1. Problem Solving as Search
Every AI problem can be formulated as finding a path in a state space from an initial state to a goal state.
Problem Formulation Components:
- Initial state
- Actions / Operators (successor function)
- Goal test
- Path cost (for optimal solutions)
2. Search Strategies
A. Uninformed (Blind) Search
No additional information about the goal distance → only uses path cost.
| Strategy | Order of Expansion | Complete? | Optimal? | Time Complexity | Space Complexity | When to Use |
|---|---|---|---|---|---|---|
| Breadth-First Search (BFS) | Level by level | Yes | Yes (uniform cost) | O(b^d) | O(b^d) | Small depth |
| Uniform Cost Search (UCS) | Lowest path cost first | Yes | Yes | O(b^{C*/ε}) | O(b^{C*/ε}) | Different edge costs |
| Depth-First Search (DFS) | Deepest node first | No (infinite paths) | No | O(b^m) | O(bm) | Large/infinite space |
| Iterative Deepening DFS (IDDFS) | DFS with increasing depth | Yes | Yes | O(b^d) | O(bd) | Best uninformed in practice |
Python Example: BFS for 8-Puzzle
from collections import deque
def bfs_8puzzle(start, goal):
# state as tuple: (1,2,3,4,5,6,7,8,0) where 0 is blank
start = tuple(start)
goal = tuple(goal)
queue = deque([(start, 0, None)]) # state, cost, parent
visited = {start}
parent = {start: None}
moves = {start: 0}
while queue:
state, cost, _ = queue.popleft()
if state == goal:
# reconstruct path
path = []
while state != start:
path.append(state)
state = parent[state]
path.append(start)
path.reverse()
return path, cost
# find blank position
pos = state.index(0)
row, col = pos // 3, pos % 3
directions = [(-1,0), (1,0), (0,-1), (0,1)] # up, down, left, right
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < 3 and 0 <= nc < 3:
new_pos = nr * 3 + nc
new_state = list(state)
new_state[pos], new_state[new_pos] = new_state[new_pos], new_state[pos]
new_state = tuple(new_state)
if new_state not in visited:
visited.add(new_state)
parent[new_state] = state
queue.append((new_state, cost + 1, state))
return None, -1
# Example
start = [1, 2, 3, 0, 4, 6, 7, 5, 8]
goal = [1, 2, 3, 7, 8, 4, 0, 6, 5]
path, steps = bfs_8puzzle(start, goal)
print(f"Solved in {steps} moves!")
B. Informed Search (Heuristic Search)
Uses heuristic function h(n) → estimate of cost from n to goal.
| Strategy | Evaluation Function | Optimal? | Complete? | Notes |
|---|---|---|---|---|
| Greedy Best-First | f(n) = h(n) | No | No | Fast but suboptimal |
| A* | f(n) = g(n) + h(n) | Yes* | Yes | Best informed search |
| Weighted A* | f(n) = g(n) + w × h(n) | No | Yes | Faster, w>1 |
*Yes if h(n) is admissible (never overestimates)
Popular Heuristics
- Manhattan Distance (admissible for 4-way)
- Euclidean Distance
- Tiles out of place (for 8-puzzle)
A Python Code (Grid Pathfinding with Obstacles)* → Already given in previous response
3. Local Search Algorithms & Optimization
When path doesn't matter, only final state → e.g., 8-Queens, traveling salesman.
| Algorithm | Idea | Escapes Local Optima? |
|---|---|---|
| Hill Climbing | Always take best neighbor | No |
| Simulated Annealing | Allow bad moves with probability e^(-ΔE/T) | Yes |
| Genetic Algorithm | Evolution-inspired population search | Yes |
Simulated Annealing for 8-Queens (Python)
import random
import math
def conflicts(board):
n = len(board)
conflicts = 0
for i in range(n):
for j in range(i+1, n):
if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
conflicts += 1
return conflicts
def simulated_annealing_8queens():
board = list(range(8))
random.shuffle(board)
temp = 10000
cooling_rate = 0.995
while temp > 0.1:
if conflicts(board) == 0:
return board
i = random.randint(0, 7)
j = random.randint(0, 7)
board[i], board[j] = board[j], board[i]
delta_E = conflicts(board) - conflicts(list(reversed(board))) # wait, better way:
current_E = conflicts(board)
board[i], board[j] = board[j], board[i] # revert
new_E = conflicts(board)
delta_E = new_E - current_E
if delta_E < 0 or random.random() < math.exp(-delta_E / temp):
board[i], board[j] = board[j], board[i] # accept move
# else reject → board stays same
temp *= cooling_rate
return board if conflicts(board)==0 else None
solution = simulated_annealing_8queens()
print("Solution:", solution)
4. Constraint Satisfaction Problems (CSP)
Variables + Domains + Constraints
Examples: Map coloring, Sudoku, Scheduling, 8-Queens
Techniques:
- Backtracking
- Forward Checking
- Arc Consistency (AC-3)
Python: Sudoku Solver using Backtracking + Forward Checking
def is_valid(board, row, col, num):
# Check row, col, 3x3 box
for x in range(9):
if board[row][x] == num or board[x][col] == num:
return False
start_row, start_col = row // 3 * 3, col // 3 * 3
for i in range(3):
for j in range(3):
if board[i + start_row][j + start_col] == num:
return False
return True
def solve_sudoku(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0 # backtrack
return False
return True # solved
# Example puzzle
puzzle = [
[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]
]
solve_sudoku(puzzle)
for row in puzzle:
print(row)
5. Game Playing (Adversarial Search)
Minimax Algorithm
MAX player tries to maximize score, MIN tries to minimize.
Alpha-Beta Pruning → Cuts branches that won't affect final decision.
Python: Tic-Tac-Toe with Alpha-Beta Pruning
def evaluate(board):
# Check rows, cols, diagonals for win
win_states = [
[board[0][0], board[0][1], board[0][2]],
[board[1][0], board[1][1], board[1][2]],
[board[2][0], board[2][1], board[2][2]],
[board[0][0], board[1][0], board[2][0]],
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]],
[board[0][2], board[1][1], board[2][0]],
]
if [1,1,1] in win_states: return 10
if [-1,-1,-1] in win_states: return -10
return 0
def game_over(board):
return evaluate(board) != 0 or all(cell != 0 for row in board for cell in row)
def minimax(board, depth, alpha, beta, maximizing_player):
if game_over(board) or depth == 0:
return evaluate(board)
if maximizing_player:
max_eval = -float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == 0:
board[i][j] = 1
eval = minimax(board, depth-1, alpha, beta, False)
board[i][j] = 0
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
return max_eval
return max_eval
else:
min_eval = float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == 0:
board[i][j] = -1
eval = minimax(board, depth-1, alpha, beta, True)
board[i][j] = 0
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
return min_eval
return min_eval
Summary Table
| Topic | Best Algorithm | Use Case Example |
|---|---|---|
| Shortest path (known map) | A* | GPS, Robotics |
| Puzzle solving | BFS / A* | 8-Puzzle, 15-Puzzle |
| Optimization (no path needed) | Simulated Annealing / GA | 8-Queens, TSP |
| Scheduling / Coloring | Backtracking + Arc Consistency | Sudoku, Map Coloring |
| Two-player perfect info games | Minimax + Alpha-Beta | Chess, Tic-Tac-Toe |
Now you're fully equipped with theory + working code for Unit II!
Practice these codes — they cover 90% of AI programming assignments. Good luck! 🚀