Backtracking with Constraints
More complex backtracking problems involve navigating grids, satisfying constraints, or making strategic placements.
Problem 1: Word Search
Problem: Find if a word exists in a 2D board.
def exist(board, word):
"""
board = [['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']]
word = "ABCCED" → True
"""
rows, cols = len(board), len(board[0])
def backtrack(r, c, index):
# Base case: found all letters
if index == len(word):
return True
# Out of bounds or wrong letter
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
# Save and mark current cell as visited
temp = board[r][c]
board[r][c] = '#'
# Explore all 4 directions
found = (backtrack(r+1, c, index+1) or
backtrack(r-1, c, index+1) or
backtrack(r, c+1, index+1) or
backtrack(r, c-1, index+1))
# Restore cell (backtrack)
board[r][c] = temp
return found
# Try starting from each cell
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
Key Pattern: Mark cell as visited, explore neighbors, restore.
Problem 2: N-Queens
Problem: Place n queens on n×n board so no two attack each other.
def solve_n_queens(n):
"""
Input: n=4
Output: [[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
"""
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
# Track attacked columns and diagonals
cols = set()
diag1 = set() # r - c
diag2 = set() # r + c
def backtrack(row):
# Base case: placed all queens
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
# Check if position is safe
if (col in cols or
(row - col) in diag1 or
(row + col) in diag2):
continue
# Place queen
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# Recurse to next row
backtrack(row + 1)
# Remove queen
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
print(solve_n_queens(4))
Key Insight: Track columns and both diagonals for efficient checking.
Problem 3: Sudoku Solver
Problem: Fill a 9×9 Sudoku board.
def solve_sudoku(board):
"""
board = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
...
Modify board in place.
"""
def is_valid(row, col, num):
# Check row
if num in board[row]:
return False
# Check column
if any(board[r][col] == num for r in range(9)):
return False
# Check 3x3 box
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == num:
return False
return True
def backtrack():
# Find next empty cell
for r in range(9):
for c in range(9):
if board[r][c] == '.':
# Try each number
for num in '123456789':
if is_valid(r, c, num):
board[r][c] = num
if backtrack():
return True
board[r][c] = '.'
return False # No valid number found
return True # Board complete
backtrack()
Optimization: Track available numbers for each cell.
def solve_sudoku_optimized(board):
# Precompute possible values for each cell
rows = [set('123456789') for _ in range(9)]
cols = [set('123456789') for _ in range(9)]
boxes = [set('123456789') for _ in range(9)]
# Remove already placed numbers
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
box = (r // 3) * 3 + c // 3
rows[r].discard(num)
cols[c].discard(num)
boxes[box].discard(num)
def backtrack(pos):
if pos == 81: # All cells filled
return True
r, c = pos // 9, pos % 9
if board[r][c] != '.':
return backtrack(pos + 1)
box = (r // 3) * 3 + c // 3
# Try only valid numbers
for num in rows[r] & cols[c] & boxes[box]:
board[r][c] = num
rows[r].discard(num)
cols[c].discard(num)
boxes[box].discard(num)
if backtrack(pos + 1):
return True
board[r][c] = '.'
rows[r].add(num)
cols[c].add(num)
boxes[box].add(num)
return False
backtrack(0)
Problem 4: Palindrome Partitioning
Problem: Partition string into substrings where each is a palindrome.
def partition(s):
"""
Input: "aab"
Output: [["a","a","b"], ["aa","b"]]
"""
result = []
current = []
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start):
# Base case: reached end
if start == len(s):
result.append(current[:])
return
# Try all possible partitions
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
# Only continue if current part is palindrome
if is_palindrome(substring):
current.append(substring)
backtrack(end)
current.pop()
backtrack(0)
return result
print(partition("aab"))
Optimization: Precompute palindrome checks with DP.
Problem 5: Restore IP Addresses
Problem: Generate all valid IP addresses from a string.
def restore_ip_addresses(s):
"""
Input: "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
"""
result = []
current = []
def is_valid(segment):
# Check if segment is valid IP part
if not segment or len(segment) > 3:
return False
if segment[0] == '0' and len(segment) > 1:
return False # Leading zeros
return 0 <= int(segment) <= 255
def backtrack(start):
# Base case: have 4 parts and used all digits
if len(current) == 4:
if start == len(s):
result.append('.'.join(current))
return
# Try segments of length 1-3
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start + length]
if is_valid(segment):
current.append(segment)
backtrack(start + length)
current.pop()
backtrack(0)
return result
print(restore_ip_addresses("25525511135"))
Problem 6: Rat in a Maze
Problem: Find all paths from top-left to bottom-right in a maze.
def find_paths(maze):
"""
maze = [[1,1,0,0],
[1,1,1,0],
[0,1,1,1],
[0,0,1,1]]
1 = open, 0 = blocked
Output: ["DDRR", "RRDD"]
"""
n = len(maze)
result = []
path = []
visited = [[False] * n for _ in range(n)]
def backtrack(r, c):
# Base case: reached bottom-right
if r == n-1 and c == n-1:
result.append(''.join(path))
return
# Mark visited
visited[r][c] = True
# Try all 4 directions
# Down
if r + 1 < n and maze[r+1][c] == 1 and not visited[r+1][c]:
path.append('D')
backtrack(r + 1, c)
path.pop()
# Left
if c - 1 >= 0 and maze[r][c-1] == 1 and not visited[r][c-1]:
path.append('L')
backtrack(r, c - 1)
path.pop()
# Right
if c + 1 < n and maze[r][c+1] == 1 and not visited[r][c+1]:
path.append('R')
backtrack(r, c + 1)
path.pop()
# Up
if r - 1 >= 0 and maze[r-1][c] == 1 and not visited[r-1][c]:
path.append('U')
backtrack(r - 1, c)
path.pop()
# Unmark visited (backtrack)
visited[r][c] = False
if maze[0][0] == 1:
backtrack(0, 0)
return result
Common Constraint Patterns
1. Grid Navigation
# Mark visited, explore, unmark
visited[r][c] = True
backtrack(r, c)
visited[r][c] = False
2. Attack Patterns (N-Queens)
# Track rows, columns, diagonals
if col in cols or (r-c) in diag1 or (r+c) in diag2:
return False
3. Valid Segments (IP, Palindrome)
# Check validity before recursing
if is_valid(segment):
backtrack(next_position)
4. Count-Based (Parentheses)
# Track resources used
if open_count < n:
backtrack(open_count + 1, close_count)
Performance Tips
- Prune early: Check validity before recursing
- Precompute: Calculate palindromes, valid positions upfront
- Choose wisely: Start from cell with fewest options
- Track state: Use sets/arrays for O(1) validity checks
- Limit search: Add constraints to reduce branches
Key Takeaway
Constraint-based backtracking is about managing state and checking validity efficiently. The pattern remains: make choice, check constraints, recurse, backtrack. The complexity comes from tracking multiple constraints simultaneously.