Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets
WHY does backtracking exist?
WHAT is the search space? A tree. Each node = a partial solution. Each edge = "make one more choice." Leaves = complete candidates.
HOW do we walk it? Recursive DFS with this universal skeleton:
The "un-choose" line is what makes backtracking different from plain recursion: the state is shared and mutated, so you must restore it before trying a sibling branch.
Pattern 1 — All Subsets (the simplest skeleton)
WHY ? Each element is independently in or out → .
HOW — at index i, branch on "take nums[i]" vs "skip it":
def subsets(nums):
res, path = [], []
def bt(i):
if i == len(nums):
res.append(path[:]) # copy! path keeps mutating
return
bt(i+1) # skip nums[i]
path.append(nums[i]) # choose
bt(i+1) # explore
path.pop() # un-choose
bt(0)
return resPattern 2 — All Permutations
WHY ? choices for first slot, for next, … .
HOW — track which elements are used:
def permute(nums):
res, path, used = [], [], [False]*len(nums)
def bt():
if len(path) == len(nums):
res.append(path[:]); return
for i in range(len(nums)):
if used[i]: continue # pruning: each element once
used[i] = True; path.append(nums[i]) # choose
bt() # explore
path.pop(); used[i] = False # un-choose
bt()
return resPattern 3 — N-Queens
HOW do we check a column/diagonal in ?
- Same column →
cols[c]seen before. - Same ↘ diagonal: cells where
row - colis constant. (Derive: moving down-right adds 1 to bothrandc, sor-cunchanged.) - Same ↗ anti-diagonal:
row + colis constant.
So we keep three sets: cols, diag (r-c), anti (r+c).
def solveNQueens(n):
res = []
cols, diag, anti = set(), set(), set()
board = [['.']*n for _ in range(n)]
def bt(r):
if r == n:
res.append([''.join(row) for row in board]); return
for c in range(n):
if c in cols or (r-c) in diag or (r+c) in anti:
continue # prune attacked square
cols.add(c); diag.add(r-c); anti.add(r+c) # choose
board[r][c] = 'Q'
bt(r+1) # explore
cols.remove(c); diag.remove(r-c); anti.remove(r+c) # un-choose
board[r][c] = '.'
bt(0)
return resPattern 4 — Sudoku Solver
HOW — find next empty cell, try digits 1–9, recurse, undo on failure:
def solveSudoku(board): # board: list of lists, '.' = empty
def ok(r, c, ch):
b = (r//3)*3 + c//3 # box index
for i in range(9):
if board[r][i]==ch: return False # row
if board[i][c]==ch: return False # col
if board[(b//3)*3 + i//3][(b%3)*3 + i%3]==ch: return False # box
return True
def bt():
for r in range(9):
for c in range(9):
if board[r][c]=='.':
for ch in '123456789':
if ok(r,c,ch):
board[r][c]=ch # choose
if bt(): return True # explore
board[r][c]='.' # un-choose
return False # no digit works → dead end
return True # no empty cell → solved
bt()Steel-manned mistakes
Recall Feynman: explain to a 12-year-old
Imagine solving a maze by hand. You walk forward making choices. If you hit a wall, you walk back to the last fork and try a different path — you don't restart the whole maze. Backtracking is that: try a step, if it's hopeless erase it and try another. For queens, you place chess queens one row at a time; if a new queen could be captured, you pick it up and slide it over. That "pick it up and put it back in the box" is the secret move.
Flashcards
Backtracking is which traversal over what structure?
The three universal steps of backtracking
Why copy path[:] when recording a solution?
path is mutated in place; storing a reference gives all answers the same (eventually empty) list.N-Queens: how to detect same ↘ diagonal in O(1)?
r - c; keep a set of r-c.N-Queens: key for the ↗ anti-diagonal?
r + c.Why place one queen per row in N-Queens?
Sudoku box index formula for cell (r,c)?
(r//3)*3 + c//3.Why does the Sudoku solver return a bool but N-Queens does not?
Time/branching for all subsets vs all permutations?
What is "pruning" in backtracking?
What goes wrong if you skip the un-choose step?
Connections
- Depth-First-Search — backtracking IS DFS with explicit undo.
- Recursion-and-the-call-stack — the implicit stack stores partial state.
- Branch-and-Bound — pruning + a numeric bound for optimization.
- Constraint-Satisfaction-Problems — Sudoku/N-Queens are CSPs.
- Dynamic-Programming — when subproblems overlap, memoize the search instead.
- Time-Complexity-of-Recursive-Algorithms — counting nodes in the search tree.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Backtracking ka core idea simple hai: tum apna answer ek-ek choice karke banate ho, aur jaise hi pata chale ki yeh partial choice kabhi valid solution tak nahi le ja sakti, tum usko undo karke (backtrack) agla option try karte ho. Isko soch lo jaise maze solve karna — galat raaste par jaake wall mile to pure maze ko restart nahi karte, bas pichhle fork tak wapas aate ho. Yahi DFS hai with "undo" — teen magic words: Choose → Explore → Un-choose.
Subsets aur permutations sabse aasaan patterns hain. Subsets me har element ko ya to lo ya chhodo, isliye total . Permutations me used[] array se track karo kaun sa element use ho chuka, total . Bahut important baat: jab answer store karo to path[:] (copy) store karo, warna saare answers same list ko point karenge aur sab empty ban jayenge — yeh sabse common bug hai.
N-Queens me trick yeh hai ki har row me ek hi queen rakho, isse row-conflict apne aap khatam. Column ke liye cols set, diagonal ke liye r-c constant hota hai (↘ line), aur anti-diagonal ke liye r+c constant (↗ line). Bas in teen sets se O(1) me check ho jata hai ki square attack me hai ya nahi. Sudoku me empty cell dhoondo, 1–9 try karo, valid ho to lagao aur recurse karo; agar fail to wapas '.' kar do. Yaad rakho: pruning recurse karne se pehle karo (validity check choose se pehle), tabhi speed milti hai — warna yeh sirf brute force ban jata hai.