Backtracking
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point in time.
Module Contents
Learning Resources
Introduction to Backtracking
Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. It's like a methodical trial and error approach, where we explore all possibilities and backtrack when we hit a dead end.
What is Backtracking?
Backtracking is a refined brute force approach that systematically searches for a solution to a problem among all available options. It incrementally builds candidates to the solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly lead to a valid solution.
When to Use Backtracking
Backtracking is suitable for problems where:
- You need to find all (or some) solutions to a problem
- The problem can be broken down into a sequence of decisions
- Each decision leads to a new subproblem
- The solution space is too large to explore exhaustively
Advantages and Limitations
Advantages:
- Can find all possible solutions
- Avoids exploring paths that cannot lead to a solution
- Works well for constraint satisfaction problems
Limitations:
- Exponential time complexity in the worst case
- May not be efficient for large problem instances
- Requires careful implementation to avoid stack overflow
Principles and Techniques
Understanding the key principles and techniques of backtracking is essential for implementing efficient solutions to complex problems.
1. The Backtracking Framework
A general framework for backtracking algorithms consists of the following components:
- Choice: At each step, make a choice from the available options
- Constraints: Check if the choice satisfies all constraints
- Goal: Determine if the current state represents a solution
- Backtrack: If the choice doesn't lead to a solution, undo it and try another option
Pseudocode Template:
function backtrack(state, choices):
if isGoal(state):
addToSolutions(state)
return
for choice in choices:
if isValid(state, choice):
makeChoice(state, choice)
backtrack(state, remainingChoices)
undoChoice(state, choice) // Backtrack2. Pruning the Search Space
Pruning is a technique to avoid exploring paths that cannot lead to a valid solution. It's crucial for improving the efficiency of backtracking algorithms.
Pruning Techniques:
- Early termination: Stop exploring a path as soon as it violates a constraint
- Forward checking: Check if future assignments are possible before making a choice
- Constraint propagation: Use constraints to reduce the domain of variables
- Heuristics: Use problem-specific knowledge to guide the search
3. State Space Tree
The state space tree is a conceptual representation of all possible states in a backtracking algorithm. Each node represents a state, and each edge represents a choice.
Properties:
- The root represents the initial state
- Leaf nodes represent either solutions or dead ends
- The path from the root to a leaf represents a sequence of choices
- Backtracking involves a depth-first traversal of this tree
4. Backtracking vs. Other Techniques
| Backtracking | Dynamic Programming | Greedy Algorithms |
|---|---|---|
| Explores all possible solutions | Builds optimal solution from optimal subproblems | Makes locally optimal choices |
| Can find all solutions | Finds one optimal solution | May not find optimal solution |
| Exponential time complexity | Polynomial time complexity | Linear or polynomial time complexity |
| Uses recursion with backtracking | Uses memoization or tabulation | Makes one-time decisions |
Classic Backtracking Problems
Several classic problems can be efficiently solved using backtracking. Understanding these problems helps in recognizing when a backtracking approach might be applicable.
1. N-Queens Problem
Place N queens on an N×N chessboard so that no two queens threaten each other. A solution requires that no two queens share the same row, column, or diagonal.
Backtracking Approach:
Place queens one by one in different columns, starting from the leftmost column. When placing a queen in a column, check if it clashes with already placed queens. If it does, backtrack and try other rows in the same column. If all rows are tried and nothing works, backtrack to the previous column and try a different row.
2. Sudoku Solver
Fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids contains all of the digits from 1 to 9.
Backtracking Approach:
Start with an empty cell and try filling it with a valid digit (1-9). After filling, move to the next empty cell. If at any point a digit cannot be placed in an empty cell without violating the rules, backtrack to the previous cell and try a different digit.
3. Permutations and Combinations
Generate all permutations or combinations of a given set of elements.
Backtracking Approach:
For permutations, start with an empty result and add elements one by one. For each position, try all available elements. For combinations, decide whether to include or exclude each element.
4. Subset Sum Problem
Given a set of non-negative integers and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.
Backtracking Approach:
For each element, there are two choices: either include it in the subset or exclude it. Recursively try both options and check if any leads to the desired sum.
5. Graph Coloring
Assign colors to the vertices of a graph such that no two adjacent vertices have the same color, using at most k colors.
Backtracking Approach:
Assign colors one by one to different vertices, starting from the first vertex. Before assigning a color, check if it's safe by examining all adjacent vertices. If a color assignment doesn't lead to a solution, backtrack and try a different color.
Implementation Examples
Let's look at some code examples of backtracking algorithms to better understand their implementation.
N-Queens Problem
public class NQueens {
public static List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
// Initialize the board with empty cells
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(board, 0, result);
return result;
}
private static void backtrack(char[][] board, int row, List<List<String>> result) {
// If we've placed queens in all rows, we have a valid solution
if (row == board.length) {
result.add(constructSolution(board));
return;
}
int n = board.length;
for (int col = 0; col < n; col++) {
// Check if it's safe to place a queen at board[row][col]
if (isSafe(board, row, col)) {
// Place the queen
board[row][col] = 'Q';
// Recur to place queens in the next row
backtrack(board, row + 1, result);
// Backtrack and remove the queen
board[row][col] = '.';
}
}
}
private static boolean isSafe(char[][] board, int row, int col) {
int n = board.length;
// Check column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check upper-left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check upper-right diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private static List<String> constructSolution(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(new String(row));
}
return solution;
}
public static void main(String[] args) {
int n = 4;
List<List<String>> solutions = solveNQueens(n);
System.out.println("Number of solutions: " + solutions.size());
for (List<String> solution : solutions) {
for (String row : solution) {
System.out.println(row);
}
System.out.println();
}
}
}Permutations
def permute(nums):
result = []
backtrack(nums, [], result)
return result
def backtrack(nums, path, result):
# If the path has the same length as nums, we have a complete permutation
if len(path) == len(nums):
result.append(path[:]) # Add a copy of the path to the result
return
for i in range(len(nums)):
# Skip if the number is already in the path
if nums[i] in path:
continue
# Make a choice
path.append(nums[i])
# Explore further
backtrack(nums, path, result)
# Backtrack (undo the choice)
path.pop()
# Example usage
nums = [1, 2, 3]
permutations = permute(nums)
print(permutations) # Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Sudoku Solver
public class SudokuSolver {
public static void solveSudoku(char[][] board) {
solve(board);
}
private static boolean solve(char[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// Find an empty cell
if (board[row][col] == '.') {
// Try placing digits 1-9
for (char digit = '1'; digit <= '9'; digit++) {
if (isValid(board, row, col, digit)) {
// Place the digit
board[row][col] = digit;
// Recur to fill the rest of the board
if (solve(board)) {
return true;
}
// If placing the digit doesn't lead to a solution, backtrack
board[row][col] = '.';
}
}
// If no digit can be placed, the current board configuration is invalid
return false;
}
}
}
// If we've filled all cells, we have a valid solution
return true;
}
private static boolean isValid(char[][] board, int row, int col, char digit) {
// Check row
for (int j = 0; j < 9; j++) {
if (board[row][j] == digit) {
return false;
}
}
// Check column
for (int i = 0; i < 9; i++) {
if (board[i][col] == digit) {
return false;
}
}
// Check 3x3 box
int boxRow = row - row % 3;
int boxCol = col - col % 3;
for (int i = boxRow; i < boxRow + 3; i++) {
for (int j = boxCol; j < boxCol + 3; j++) {
if (board[i][j] == digit) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
char[][] board = {
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'}
};
solveSudoku(board);
// Print the solved board
for (char[] row : board) {
System.out.println(new String(row));
}
}
}Practice Problems
Apply your knowledge of backtracking by solving these carefully selected problems:
1. Letter Combinations of a Phone Number
Given a string containing digits from 2-9, return all possible letter combinations that the number could represent (like on a telephone keypad).
2. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
3. Combination Sum
Given an array of distinct integers and a target sum, find all unique combinations where the candidates sum to the target. Each number may be used multiple times.
4. N-Queens
Place N queens on an N×N chessboard so that no two queens threaten each other.
5. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.