Algorithm
Backtracking builds a solution step by step and undoes choices that break a constraint, pruning the search for permutations, N-Queens, and Sudoku.
Backtracking fills in an answer one step at a time, exploring a state-space tree depth first, and as soon as the choices made so far violate a constraint it returns to the previous step and tries a different option. The code is a loop of three moves: choose a candidate, explore recursively, and unchoose it on the way back.
Unlike brute force, which builds every complete candidate before checking it, backtracking cuts off hopeless branches early and often solves the same problem with orders of magnitude fewer steps. It is the standard approach for enumerating permutations and combinations and for constraint satisfaction problems such as N-Queens, Sudoku, and graph coloring, and it powers regular expression engines and SAT solvers, so it appears in coding interviews and production code alike.
Start with enumeration problems that need no pruning, such as subsets and permutations, to learn the choose, explore, unchoose template. Then practice constraint checks and pruning on N-Queens and Sudoku. Finally, count visited nodes to see what pruning buys you, and compare the same problems with dynamic programming so you know which technique fits which question.
With the empty state as the root and each choice as an edge, every candidate becomes a path, and backtracking walks this tree depth first.
Add a candidate to the partial solution, recurse, then remove it on return, so a single list is shared by every branch.
When a partial solution cannot lead to an answer, the whole subtree below it is skipped, shrinking an exponential search space in practice.
Tracking used columns, diagonals, rows, or boxes in sets or arrays lets you test whether a new choice breaks a rule in constant time.
permutations blocks already chosen elements with a used array and builds every permutation through choose, explore, unchoose, storing each finished path as a copy with path[:]. n_queens tracks columns and both diagonals (row - c, row + c) in sets, skips attacked squares immediately, and counts the solutions. Running python backtracking.py prints the 6 permutations of [1, 2, 3] and 92, the number of 8-Queens solutions.
backtracking.py
def permutations(items):
result, path = [], []
used = [False] * len(items)
def backtrack():
if len(path) == len(items):
result.append(path[:]) # store a copy of the full path
return
for i, x in enumerate(items):
if used[i]:
continue
used[i] = True # choose
path.append(x)
backtrack() # explore
path.pop() # unchoose
used[i] = False
backtrack()
return result
def n_queens(n):
cols, diag, anti = set(), set(), set()
def place(row):
if row == n:
return 1
count = 0
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue # prune: square is attacked
cols.add(c); diag.add(row - c); anti.add(row + c)
count += place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
return count
return place(0)
print(permutations([1, 2, 3]))
print(n_queens(8)) # 92
python backtracking.pySix chapters that take you from installation to the core ideas of Backtracking.
Ask questions, share experience and trade opinions about Backtracking.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.