Lilly Tech Systems
Intermediate
Grid & Matrix Backtracking
Grid backtracking problems explore 2D spaces by moving in four (or eight) directions, marking cells as visited, and undoing the mark when backtracking. These problems are the foundation of pathfinding in robotics, game AI, and constraint satisfaction solvers used in ML pipeline scheduling.
Grid Backtracking Template: Mark the current cell as visited, explore all valid neighbors recursively, then unmark (backtrack). Use boundary checks and constraint validation before recursing.
Problem 1: Word Search (LC 79)
Problem: Given an m×n grid of characters and a word, determine if the word exists in the grid by moving horizontally or vertically to adjacent cells. Each cell may be used at most once.
Example: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" → True
Brute Force: Check All Paths from Every Cell
def exist_brute(board: list[list[str]], word: str) -> bool:
"""Try every cell as a starting point, explore all paths.
No pruning: explores all 4 directions even when characters
do not match. Creates a new visited set for every path.
Time: O(m * n * 4^L) where L = word length
Space: O(L) recursion depth
"""
rows, cols = len(board), len(board[0])
def dfs(r, c, idx, visited):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
(r, c) in visited or board[r][c] != word[idx]):
return False
visited.add((r, c))
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if dfs(r + dr, c + dc, idx + 1, visited):
return True
visited.remove((r, c))
return False
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0, set()):
return True
return FalseOptimal: In-Place Marking + Early Termination
def exist(board: list[list[str]], word: str) -> bool:
"""Word search with in-place backtracking.
Optimizations over brute force:
1. Mark visited cells by modifying the board in-place
(replace with '#'), avoiding set overhead
2. Check character match BEFORE recursing (prune immediately)
3. Return True as soon as any path succeeds
Time: O(m * n * 3^L) - 3 not 4 because we never revisit
Space: O(L) recursion depth, O(1) extra space
"""
rows, cols = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[idx]):
return False
# CHOOSE: mark as visited
temp = board[r][c]
board[r][c] = '#'
# EXPLORE: try all 4 directions
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if backtrack(r + dr, c + dc, idx + 1):
board[r][c] = temp # restore before returning
return True
# UN-CHOOSE: backtrack
board[r][c] = temp
return False
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
# exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")
# -> TrueProblem 2: N-Queens (LC 51)
Problem: Place n queens on an n×n chessboard so that no two queens threaten each other. Return all distinct solutions.
Example: n = 4 → [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Brute Force: Place Queens in All Positions, Validate
def solve_n_queens_brute(n: int) -> list[list[str]]:
"""Try all n^n placements, validate each board.
Place one queen per row, try all n columns for each row.
After placing all queens, check if any two attack each other.
Time: O(n^n * n^2) - n^n placements, n^2 validation each
Space: O(n^2)
"""
def is_valid(queens):
for i in range(len(queens)):
for j in range(i + 1, len(queens)):
if queens[i] == queens[j]: # same column
return False
if abs(queens[i] - queens[j]) == abs(i - j): # diagonal
return False
return True
def generate(row, queens):
if row == n:
if is_valid(queens):
board = []
for q in queens:
board.append('.' * q + 'Q' + '.' * (n - q - 1))
results.append(board)
return
for col in range(n):
generate(row + 1, queens + [col])
results = []
generate(0, [])
return resultsOptimal: Backtracking with Column/Diagonal Sets
def solve_n_queens(n: int) -> list[list[str]]:
"""N-Queens via backtracking with O(1) conflict checking.
Track occupied columns and diagonals using sets.
- cols: set of occupied columns
- diag1: set of (row - col) values (main diagonal)
- diag2: set of (row + col) values (anti-diagonal)
At each row, try each column. Skip if column or either
diagonal is already occupied. This prunes the search tree
from O(n^n) to approximately O(n!).
Time: O(n!), Space: O(n)
"""
results = []
queens = [] # queens[i] = column of queen in row i
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row):
if row == n:
board = []
for q in queens:
board.append('.' * q + 'Q' + '.' * (n - q - 1))
results.append(board)
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# CHOOSE
queens.append(col)
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# EXPLORE
backtrack(row + 1)
# UN-CHOOSE
queens.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return results
# len(solve_n_queens(8)) -> 92 solutionsML Context: N-Queens is a classic Constraint Satisfaction Problem (CSP). The same backtracking + constraint propagation approach powers scheduling in ML pipelines, resource allocation in distributed training, and placement optimization in hardware-aware neural architecture search.
Problem 3: Sudoku Solver (LC 37)
Problem: Fill a 9×9 Sudoku board so that each row, column, and 3×3 box contains digits 1–9 exactly once.
Optimal: Backtracking with Constraint Sets
def solve_sudoku(board: list[list[str]]) -> None:
"""Solve Sudoku in-place via backtracking.
Maintain sets for each row, column, and 3x3 box to
check validity in O(1). Find the next empty cell, try
digits 1-9, and backtrack on conflict.
Time: O(9^m) where m = number of empty cells (with pruning much less)
Space: O(m) recursion depth + O(81) for constraint sets
"""
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Initialize constraint sets from existing board
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
rows[r].add(num)
cols[c].add(num)
boxes[(r // 3) * 3 + c // 3].add(num)
def backtrack(pos):
# Find next empty cell
while pos < 81:
r, c = pos // 9, pos % 9
if board[r][c] == '.':
break
pos += 1
else:
return True # all cells filled
r, c = pos // 9, pos % 9
box_idx = (r // 3) * 3 + c // 3
for num in '123456789':
if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
continue
# CHOOSE
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[box_idx].add(num)
# EXPLORE
if backtrack(pos + 1):
return True
# UN-CHOOSE
board[r][c] = '.'
rows[r].remove(num)
cols[c].remove(num)
boxes[box_idx].remove(num)
return False
backtrack(0)Problem 4: Rat in a Maze
Problem: Given an n×n binary matrix where 1 means open and 0 means blocked, find all paths from top-left (0,0) to bottom-right (n-1,n-1). You can move up, down, left, or right.
Example: maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]] → paths exist via (0,0)→(1,0)→(1,1)→(2,1)→(3,1)→(3,2)→(3,3)
Brute Force: DFS Without Pruning
def rat_in_maze_brute(maze: list[list[int]]) -> list[list[tuple]]:
"""Find all paths using DFS, storing full path copies.
Creates a new visited set copy at each step.
Time: O(4^(n^2)), Space: O(n^2) per path
"""
n = len(maze)
result = []
def dfs(r, c, path, visited):
if r == n - 1 and c == n - 1:
result.append(path[:])
return
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if (0 <= nr < n and 0 <= nc < n and
maze[nr][nc] == 1 and (nr, nc) not in visited):
visited.add((nr, nc))
path.append((nr, nc))
dfs(nr, nc, path, visited)
path.pop()
visited.remove((nr, nc))
if maze[0][0] == 1:
dfs(0, 0, [(0, 0)], {(0, 0)})
return resultOptimal: Backtracking with Direction Strings
def rat_in_maze(maze: list[list[int]]) -> list[str]:
"""Find all paths as direction strings (D/L/R/U).
Uses in-place marking to avoid visited set overhead.
Returns paths as strings like "DRDDRR" for readability.
Time: O(3^(n^2)) - 3 not 4 because we do not revisit
Space: O(n^2) recursion depth
"""
n = len(maze)
result = []
directions = [(1, 0, 'D'), (-1, 0, 'U'), (0, 1, 'R'), (0, -1, 'L')]
def backtrack(r, c, path):
if r == n - 1 and c == n - 1:
result.append("".join(path))
return
# Mark visited
maze[r][c] = 0
for dr, dc, direction in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
path.append(direction)
backtrack(nr, nc, path)
path.pop()
# Unmark (backtrack)
maze[r][c] = 1
if maze[0][0] == 1:
backtrack(0, 0, [])
return result
# rat_in_maze([[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]])
# -> ["DDRDRR"]Problem 5: Unique Paths with Obstacles (LC 63 - Backtracking Variant)
Problem: Count the number of unique paths from top-left to bottom-right in a grid with obstacles. You can only move right or down. Obstacles are marked as 1.
Example: grid = [[0,0,0],[0,1,0],[0,0,0]] → 2
Brute Force: Pure Backtracking
def unique_paths_brute(grid: list[list[int]]) -> int:
"""Count paths using pure recursion (no memoization).
At each cell, try moving right and down.
Skip obstacle cells. Count paths that reach bottom-right.
Time: O(2^(m+n)), Space: O(m + n) recursion depth
Very slow for large grids due to overlapping subproblems.
"""
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r >= m or c >= n or grid[r][c] == 1:
return 0
if r == m - 1 and c == n - 1:
return 1
return dfs(r + 1, c) + dfs(r, c + 1)
return dfs(0, 0)Optimal: Memoized Recursion (Top-Down DP)
def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
"""Count unique paths with memoization.
Same recursive structure, but cache results for each (r, c).
This converts exponential to polynomial time.
Time: O(m * n), Space: O(m * n)
"""
from functools import lru_cache
m, n = len(grid), len(grid[0])
if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
return 0
@lru_cache(maxsize=None)
def dfs(r, c):
if r >= m or c >= n or grid[r][c] == 1:
return 0
if r == m - 1 and c == n - 1:
return 1
return dfs(r + 1, c) + dfs(r, c + 1)
return dfs(0, 0)
# unique_paths_with_obstacles([[0,0,0],[0,1,0],[0,0,0]]) -> 2Complexity Summary
| Problem | Brute Force | Optimal | Key Optimization |
|---|---|---|---|
| Word Search | O(m×n×4L) | O(m×n×3L) | In-place marking, no revisit |
| N-Queens | O(nn) | O(n!) | Column/diagonal constraint sets |
| Sudoku | O(981) | O(9m) pruned | Row/col/box constraint sets |
| Rat in Maze | O(4n²) | O(3n²) | In-place marking |
| Unique Paths | O(2m+n) | O(m×n) | Memoization (top-down DP) |