Backtracking
Introduction
Backtracking is an algorithm design technique used to solve constraint satisfaction and combinatorial optimization problems. It builds a solution step by step and checks whether the current partial solution is valid. If the current solution cannot lead to a valid final solution, the algorithm abandons that path and returns to the previous step to try another possibility. This process is called Backtracking.
Unlike Dynamic Programming, Backtracking does not store intermediate solutions. Instead, it explores the search space systematically and eliminates invalid choices as early as possible.
Why Do We Need Backtracking?
Many computational problems require exploring multiple possible solutions. Trying every possible combination is often inefficient. Backtracking improves efficiency by abandoning choices that cannot produce a valid solution.
| Without Backtracking | With Backtracking |
|---|---|
| Explores every possible solution. | Rejects invalid solutions early. |
| Higher execution time. | Reduces unnecessary computations. |
| No pruning of search space. | Prunes invalid branches. |
| Consumes more processing time. | Produces solutions more efficiently. |
Real-Life Example
Suppose you are solving a maze. At every junction, you choose one path. If the chosen path leads to a dead end, you return to the previous junction and try another path. This process continues until the destination is reached. This is exactly how Backtracking works.
Working Principle
Backtracking builds the solution one step at a time. After every step, it checks whether the partial solution satisfies the required constraints. If it does, the algorithm proceeds further. Otherwise, it returns to the previous step and tries another alternative.
State Space Tree
Backtracking problems are usually represented using a State Space Tree. Each node represents a partial solution, while each branch represents a possible decision. Invalid branches are abandoned immediately.
Characteristics of Backtracking
| Characteristic | Description |
|---|---|
| Recursive | Uses recursive function calls. |
| State Space Tree | Represents all possible solutions. |
| Constraint Checking | Rejects invalid solutions immediately. |
| Depth First Search | Explores one branch completely before moving to another. |
| Pruning | Eliminates unnecessary branches. |
Applications
| Problem | Description |
|---|---|
| N-Queen Problem | Place queens safely on a chessboard. |
| Graph Coloring | Assign colours without conflicts. |
| Hamiltonian Cycle | Find a cycle visiting every vertex exactly once. |
| Sudoku Solver | Fill all cells while satisfying constraints. |
| Maze Solving | Find a valid path through a maze. |
| Sum of Subsets | Find subsets having a required sum. |
Backtracking Algorithm
Backtracking(State)
Step 1 : If the current state is a solution,
Display the solution and return.
Step 2 : Generate all possible choices.
Step 3 : For each choice
Check whether the choice is valid.
Step 4 : If valid,
Select the choice.
Recursively solve the remaining problem.
Step 5 : If the solution is not obtained,
Undo the choice (Backtrack).
Step 6 : Try the next possible choice.
Solved Example
Suppose we want to find a path through a simple maze.
Step 1 : Start from the source node S.
Step 2 : Move to node A.
Step 3 : Try node B. Since it is a dead end, no valid solution exists.
Step 4 : Return (Backtrack) to node A.
Step 5 : Select another path through node C.
Step 6 : Reach node D and finally the Goal.
This example demonstrates how Backtracking avoids exploring invalid paths permanently by returning to the previous decision point.
Complexity Analysis
| Parameter | Complexity | Remarks |
|---|---|---|
| Best Case | O(n) | Solution is found quickly. |
| Average Case | Problem Dependent | Depends upon pruning. |
| Worst Case | O(2n) or higher | May explore every possible solution. |
| Space Complexity | O(n) | Recursive call stack. |
Advantages of Backtracking
- Produces exact solutions.
- Rejects invalid solutions early.
- Suitable for constraint satisfaction problems.
- Easy to implement recursively.
- Reduces unnecessary exploration through pruning.
Limitations of Backtracking
- Worst-case execution time may be exponential.
- Recursive implementation may consume more memory.
- Performance depends upon effective pruning.
- Not suitable for extremely large search spaces.
Backtracking vs Dynamic Programming
| Backtracking | Dynamic Programming |
|---|---|
| Searches for feasible solutions. | Optimizes solutions. |
| Uses State Space Tree. | Uses DP Table. |
| Does not store previous solutions. | Stores intermediate results. |
| Uses pruning. | Uses Memoization or Tabulation. |
| Suitable for constraint satisfaction problems. | Suitable for optimization problems. |
Backtracking vs Greedy Method
| Backtracking | Greedy Method |
|---|---|
| Explores multiple possibilities. | Selects the locally best choice. |
| Can undo decisions. | Never revisits previous choices. |
| Guarantees a valid solution if one exists. | May not always produce the optimal solution. |
| Uses recursion. | Generally iterative. |
Summary
Backtracking is a powerful algorithm design technique used for solving constraint satisfaction and combinatorial problems. It constructs a solution incrementally, verifies every intermediate step and abandons invalid choices through backtracking. Although its worst-case time complexity is generally exponential, pruning makes it practical for solving problems such as the N-Queen Problem, Graph Coloring, Hamiltonian Cycle, Sudoku and the Sum of Subsets Problem.