Published: 18 Apr 2025 | Reading Time: 12 min read
Visualize yourself at a crossroads in a maze with several routes ahead, and your job is to eliminate all the dead ends. After selecting one and taking a few steps, you discover it's a dead end. You turn around, go back, and attempt a different route again. This goes on until you eliminate all the wrong routes. Backtracking in DAA (Design and Analysis of Algorithms) is based on a similar principle. A backtracking algorithm solves problems by trying out different options one by one, and if any option doesn't work, it "backtracks" and tries the next one.
It's similar to having a superpower that enables you to look into every potential solution to an issue, whether you're solving a Sudoku puzzle, placing queens on a chessboard, or cracking a complex optimisation problem. Backtracking is a powerful algorithm for solving such complex problems in computer science and mathematics.
This blog will help you understand backtracking algorithms and how they are used in solving problems. Here, you will discover how they function, why they are so successful, and their applications. We will break down the concepts using clear explanations, pseudocode, and real-world examples. By the end, you will not only understand backtracking but also recognize its efficiency and assistance.
Backtracking is an algorithmic method for finding answers that examines every option and eliminates those that don't meet the requirements. Recursive algorithms frequently use it to generate solutions while removing incorrect ones.
For example, if a number placement leads to an invalid state in a Sudoku puzzle, we backtrack by undoing the last move and trying another number.
Recursion is a basic concept that plays a significant role in backtracking. In simple words, recursion means a function calling itself to break down a problem into smaller parts. In backtracking, recursion helps in exploring all the possible paths step by step.
Each recursive call represents a decision point. The algorithm keeps making choices and diving deeper until it finds a valid solution or hits a dead end. When it hits a dead end, it returns to the previous step (this is the backtracking part) and tries a new option.
For example, while solving a puzzle like Sudoku, recursion helps us fill each empty cell one by one. If placing a number causes a conflict, we use recursion to go back to the previous step and try a different number.
Thus, recursion provides the structure that allows backtracking to explore and undo choices efficiently.
Backtracking is a systematic way of exploring all possible solutions which follows a Depth-First Search (DFS) approach, where we make a choice, explore further, and if we hit a dead-end, we undo (backtrack) and try a different path.
Here is a step-by-step process of how the backtracking works:
1. Start from an Initial State
We begin with an empty or partially completed solution and define constraints that must be followed.
2. Exploration: Make a Choice and Move Forward
At each step, we choose an option from a set of possible choices and add it to our current solution.
3. Check if the Current Choice Leads to a Solution
If the current choice completes the solution (i.e., meets all constraints), we return it as a valid solution.
4. Backtracking: If the Choice Leads to an Invalid State, Backtrack
If we find that the choice violates the constraints, we undo (remove) that choice and go back to the previous step to try another option.
5. Repeat Until All Possibilities are Explored
This process continues recursively, exploring all possible paths until we find all valid solutions or confirm that no solution exists.
Imagine a rat trying to find its way out of a maze. The rat can move left, right, up, or down, but cannot pass through walls.
This trial-and-error process is exactly how backtracking works in algorithmic problem-solving.
Backtracking algorithms consist of several essential components that help in efficiently exploring possible solutions while eliminating invalid ones. The key components include:
Backtracking relies on recursive function calls to explore different possibilities. Each call represents a decision point in the solution path.
Solutions are constructed one step at a time, checking for validity at each stage. This ensures that only correct paths are explored further.
If a chosen path leads to an invalid solution, the algorithm undoes the last step. It then tries the next possible option, moving backward to move forward.
Backtracking skips over paths that are guaranteed to fail early on. This reduces time complexity by avoiding useless exploration.
It works well for problems with strict rules, like puzzles or optimization tasks. Backtracking checks constraints at every step to ensure correctness.
Backtracking is a systematic process for resolving computing issues by considering every possible solution. It gradually develops potential solutions and drops a candidate ("backtracks") as soon as it concludes that the candidate is not likely to result in a workable solution. There are two primary techniques for implementing backtracking algorithms: recursive and non-recursive.
In recursive backtracking, the algorithm calls itself with modified parameters to explore potential solutions. This self-referential approach utilizes the system's call stack to manage the sequence of choices and states.
The N-Queens problem requires placing N queens on an N×N chessboard so that no two queens threaten each other. A recursive backtracking solution places a queen in a row and recursively attempts to place queens in subsequent rows, backtracking upon encountering conflicts.
Non-recursive backtracking manages the exploration process explicitly using data structures like stacks or queues, avoiding the use of the system's call stack.
In solving a maze, a non-recursive backtracking algorithm uses a stack to track the current position and path. At each step, it explores unvisited neighboring cells, pushes the current state onto the stack, and moves to the next cell. Upon reaching a dead-end, it backtracks by popping the previous state from the stack and trying a different path.
Here's a comparison table outlining key differences between recursive and non-recursive (iterative) approaches:
| Factor | Recursive Approach | Non-Recursive (Iterative) Approach |
|---|---|---|
| Code Readability | Generally more concise and elegant | Typically more verbose but straightforward |
| Memory Usage | Uses stack memory (risk of stack overflow) | Uses constant memory (no stack overhead) |
| Performance | Slower due to function call overhead | Faster with no function call overhead |
| Problem Suitability | Best for naturally recursive problems (e.g., tree traversals) | Better for simple looping tasks |
| Debugging | Harder to debug due to nested calls | Easier to debug with linear execution |
| Implementation | Requires base case and recursive case | Uses loops (for/while) with explicit state |
Backtracking is a method of problem-solving that gradually advances candidates to solutions and drops a candidate ("backtracks") as soon as it concludes that the candidate is not likely to be finished with a workable solution. This approach is particularly effective for solving combinatorial problems where a sequence of choices leads to a solution. Below are detailed explanations of several classic problems that utilize backtracking:
Place 4 queens on a 4×4 chessboard so that no two queens occupy the same row, column, or diagonal.
The N-Queens problem is a classic example of combinatorial optimization and backtracking algorithms. The goal is to place N queens on an N×N chessboard without any two queens attacking each other by ensuring they are not in the same row, column, or diagonal. For N=4, the challenge is to position 4 queens on a 4×4 board under these constraints.
We can solve this problem using a backtracking algorithm, which involves placing queens in one row at a time and backtracking whenever a conflict arises.
The backtracking algorithm can be implemented as follows:
1. Start in the Leftmost Column
2. Place Queens Column by Column
3. Check for Conflicts
4. Recursive Exploration
5. Backtrack When Necessary
6. Repeat Until Solution is Found
This method systematically explores all possible placements and backtracks whenever a conflict is detected, ensuring that all potential solutions are examined.
The 4-Queens problem illustrates the power of backtracking algorithms in solving combinatorial challenges. By exploring possible configurations and backtracking upon encountering conflicts, we can find all valid arrangements for placing queens on the board.
Here's a visual representation of the solution:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | Q | |||
| 2 | Q | |||
| 3 | Q | |||
| 4 | Q |
In this arrangement:
This configuration ensures that no two queens share the same row, column, or diagonal.
Function SolveNQueens(N):
Create a board of size N x N and initialize all cells to 0
Call PlaceQueen(board, column = 0)
Function PlaceQueen(board, column):
If column ≥ N:
Print the board as a valid solution
Return
For each row from 0 to N - 1:
If placing a queen at (row, column) is safe:
Place queen at (row, column)
Recursively call PlaceQueen(board, column + 1)
Remove the queen from (row, column) [Backtrack]
Function IsSafe(board, row, column):
Check the row on the left side
Check the upper diagonal on the left side
Check the lower diagonal on the left side
If no threats found:
Return True
Else:
Return False
#include <iostream>
using namespace std;
#define N 4
// Function to print the board configuration
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
cout << endl;
}
// Function to check if placing a queen at board[row][col] is safe
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check left side of the current row
for (i = 0; i < col; i++)
if (board[row][i])
return false;
// Check upper diagonal on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
// Check lower diagonal on left side
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
// Recursive function to solve N-Queens problem
bool solveNQUtil(int board[N][N], int col) {
// If all queens are placed, return true
if (col >= N) {
printSolution(board);
return true;
}
bool res = false;
// Try placing queen in each row of the current column
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
// Place the queen
board[i][col] = 1;
// Recur to place the rest of the queens
res = solveNQUtil(board, col + 1) || res;
// Backtrack: Remove queen from board[i][col]
board[i][col] = 0;
}
}
return res;
}
// Function to solve N-Queens problem
void solveNQ() {
int board[N][N] = {0};
if (!solveNQUtil(board, 0)) {
cout << "Solution does not exist" << endl;
return;
}
}
int main() {
solveNQ();
return 0;
}
printSolution() Function:
isSafe() Function:
solveNQUtil() Function:
solveNQ() Function:
main() Function:
The program prints all possible solutions for N = 4:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Sudoku is a 9×9 grid puzzle where the goal is to fill the grid so that each row, column, and each of the nine 3×3 subgrids contain all digits from 1 to 9 without repetition.
Backtracking Approach: The solver fills empty cells one by one, trying digits from 1 to 9. After placing a digit, it moves to the next empty cell. If placing a particular digit violates Sudoku rules, the algorithm backtracks to the previous cell and tries the next possible digit. This process repeats until the puzzle is solved.
function solveSudoku(board):
if no empty cell:
return true
for digit = 1 to 9:
if placing digit is valid:
place digit
if solveSudoku(board) == true:
return true
remove digit (backtrack)
return false
In a graph, a Hamiltonian Path makes exactly one visit to every vertex. A Hamiltonian Cycle is a Hamiltonian Path that starts and ends at the same vertex, forming a cycle.
Backtracking Approach: The algorithm starts at a vertex and explores all adjacent vertices. It recursively continues the process, marking vertices as visited. If it reaches a point where no unvisited adjacent vertices are available, and not all vertices are visited, it backtracks to the previous vertex and tries a different path. This continues until a Hamiltonian Path or Cycle is found or all possibilities are exhausted.
function hamiltonianPath(graph, path, vertex):
if all vertices are visited:
return true
for each adjacent vertex:
if vertex is not visited:
add vertex to path
if hamiltonianPath(graph, path, next vertex) == true:
return true
remove vertex from path (backtrack)
return false
The objective is to figure out whether a word exists in a 2D grid of letters. Letters from the following cells can be united to create the word; "adjacent" cells belong to those that are horizontally or vertically adjacent to one another.
Backtracking Approach: The algorithm starts from each cell and explores all possible directions (up, down, left, right) to find the first letter of the word. Upon finding the first letter, it recursively searches for the next letters in adjacent cells. If a path does not lead to the complete word, it backtracks and tries a different path. This process continues until the word is found or all starting points are exhausted.
function wordSearch(board, word, i, j, index):
if index == length of word:
return true
if i < 0 or j < 0 or i >= board size or j >= board size:
return false
if board[i][j] != word[index]:
return false
mark board[i][j] as visited
for each direction (up, down, left, right):
if wordSearch(board, word, new_i, new_j, index + 1):
return true
unmark board[i][j] (backtrack)
return false
Graph coloring assigns colors to each vertex of a graph such that no two adjacent vertices share the same color. The goal is to use the minimum number of colors while satisfying this constraint. It has real-world applications in tasks like exam scheduling, map coloring, and resource allocation.
The algorithm tries to assign a color to each vertex, one at a time, ensuring that adjacent vertices do not share the same color. It starts with the first vertex and recursively attempts to color the remaining vertices. If at any point no valid color is available for a vertex, it backtracks to the previous vertex and tries a different color.
Function GraphColoring(graph, colors, vertex, totalVertices):
If vertex equals totalVertices:
Return True // All vertices are successfully colored
For each color from 1 to number of available colors:
If IsSafe(graph, colors, vertex, color) is True:
Assign 'color' to current 'vertex'
If GraphColoring(graph, colors, vertex + 1, totalVertices) is True:
Return True // Proceed with next vertex
Remove color assignment (backtrack)
Return False // No valid color found for this vertex
Function IsSafe(graph, colors, vertex, color):
For each vertex adjacent to the current vertex:
If that adjacent vertex already has the same 'color':
Return False // Not safe to use this color
Return True // Safe to use the color
The TSP seeks to identify the quickest path that makes precisely one stop in each city before returning to the starting location. It's a classic optimization problem with applications in logistics, route planning, and DNA sequencing.
The algorithm generates all permutations of the cities, calculating the path length of each. If at any point the current path's cost exceeds the minimum found so far, the algorithm prunes that path and backtracks to explore a different route. Though this guarantees finding the optimal solution, it's computationally expensive for large input sizes.
FUNCTION TSP(currentCity, visitedCities, currentCost):
IF all cities are visited AND there's a path back to the starting city:
UPDATE minimumCost if currentCost is less than minimumCost
RETURN
FOR each unvisited city i:
IF there's a path from currentCity to city i:
MARK city i as visited
CALL TSP(city i, visitedCities, currentCost + cost[currentCity][i])
UNMARK city i as visited (Backtrack)
CSPs are mathematical problems defined by a set of objects whose state must satisfy several constraints or conditions. Examples include map coloring, job scheduling, and N-Queens.
The algorithm assigns values to variables one by one. After each assignment, it checks whether the constraints are still satisfied. If not, it backtracks to the previous variable and tries a different value. This ensures an exhaustive yet efficient search of the solution space, especially when integrated with forward-checking or constraint propagation techniques.
Backtracking can be implemented in different ways depending on the complexity and efficiency needed. Below are three approaches:
This method works by trying out every possible way to arrange a set of elements. It goes step by step, checking all possible orders without worrying about whether they make sense or are the best choice. Because it looks at every single possibility, it can take a long time if there are many elements to arrange.
1. Input: A collection of distinct elements.
2. Base Case: If the collection is empty, return an empty permutation.
3. Recursive Case: For each element in the collection:
4. Output: All possible permutations of the input collection.
FUNCTION generatePermutations(nums, start):
IF start == size of nums - 1 THEN:
PRINT nums
RETURN
FOR i FROM start TO size of nums - 1 DO:
SWAP nums[start] WITH nums[i]
CALL generatePermutations(nums, start + 1)
SWAP nums[start] WITH nums[i] // BACKTRACK
FUNCTION main():
INITIALIZE nums = [1, 2, 3]
CALL generatePermutations(nums, 0)
#include <iostream>
#include <vector>
#include <algorithm>
void generatePermutations(std::vector<int>& nums, int start) {
if (start == nums.size() - 1) {
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return;
}
for (int i = start; i < nums.size(); ++i) {
std::swap(nums[start], nums[i]);
generatePermutations(nums, start + 1);
std::swap(nums[start], nums[i]); // Backtrack
}
}
int main() {
std::vector<int> nums = {1, 2, 3};
generatePermutations(nums, 0);
return 0;
}
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Backtracking with pruning enhances the basic backtracking approach by eliminating paths that cannot lead to a valid solution, thereby reducing the search space and improving efficiency. Pruning involves adding constraints to avoid exploring unnecessary branches in the solution space.
1. Input: A problem with a defined solution space and constraints.
2. Recursive Exploration: Explore possible decisions at each step.
3. Base Case: If a valid solution is found, record or output it.
4. Backtrack: Undo the last decision and explore alternative paths.
5. Output: All valid solutions that satisfy the problem's constraints.
FUNCTION isValid(solution):
// Check if the current solution satisfies the problem constraints
RETURN true // Placeholder, replace with actual validation logic
FUNCTION backtrackWithPruning(solution, step, n):
IF step == n THEN:
IF isValid(solution) THEN:
PRINT solution
RETURN
FOR i FROM 1 TO n DO:
solution[step] = i
IF isValid(solution) THEN:
CALL backtrackWithPruning(solution, step + 1, n)
FUNCTION main():
INITIALIZE n = 3 // Example problem size
INITIALIZE solution as an array of size n
CALL backtrackWithPruning(solution, 0, n)
#include <iostream>
#include <vector>
bool isValid(const std::vector<int>& solution) {
// Implement constraint checks specific to the problem
return true; // Placeholder: Replace with actual validation logic
}
void backtrackWithPruning(std::vector<int>& solution, int step, int n) {
if (step == n) {
if (isValid(solution)) {
for (int num : solution) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return;
}
for (int i = 1; i <= n; ++i) {
solution[step] = i;
if (isValid(solution)) {
backtrackWithPruning(solution, step + 1, n);
}
// No need to undo the assignment; it will be overwritten in the next iteration
}
}
int main() {
int n = 3; // Example problem size
std::vector<int> solution(n);
backtrackWithPruning(solution, 0, n);
return 0;
}
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
Bit-masking is a technique that utilizes the binary representation of numbers to manipulate individual bits efficiently. In backtracking, bit-masking can be employed to represent the state of elements (e.g., whether an element is included in a subset or has been visited) using bits of an integer. This approach is particularly useful when dealing with problems involving sets or combinations, as it allows for efficient state representation and manipulation.
FUNCTION generateSubsets(set):
n ← size of set
totalSubsets ← 2^n // Total number of subsets
FOR mask FROM 0 TO totalSubsets - 1 DO:
subset ← empty list
FOR i FROM 0 TO n - 1 DO:
IF (mask AND (1 << i)) is TRUE THEN:
ADD set[i] to subset
PRINT subset
FUNCTION main():
set ← [1, 2, 3] // Example set
CALL generateSubsets(set)
#include <iostream>
#include <vector>
void generateSubsets(const std::vector<int>& set) {
int n = set.size();
int totalSubsets = 1 << n; // 2^n subsets
for (int mask = 0; mask < totalSubsets; ++mask) {
std::vector<int> subset;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
subset.push_back(set[i]);
}
}
// Output the current subset
std::cout << "{ ";
for (int num : subset) {
std::cout << num << " ";
}
std::cout << "}" << std::endl;
}
}
int main() {
std::vector<int> set = {1, 2, 3};
generateSubsets(set);
return 0;
}
The generateSubsets() function prints all possible subsets of a set using bit manipulation. It calculates the total number of subsets using 1 << n, where n is the number of elements. For each number from 0 to 2^n - 1, it checks the binary representation to decide which elements to include in the current subset. If a bit at position i is set, it adds the corresponding element to the subset and prints it using a simple loop. The main function runs this logic for the input set {1, 2, 3}.
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
This output represents all possible subsets of the set {1, 2, 3}, including the empty set.
By applying bit-masking in backtracking, we achieve an efficient and concise method for generating subsets or combinations, which is especially beneficial when dealing with problems involving a relatively small number of elements due to the exponential growth of possible subsets.
Backtracking is a specialized form of recursion, but it differs in how it explores and solves problems. Here's a comparison:
| Feature | Recursion | Backtracking |
|---|---|---|
| Definition | A method where a function calls itself to solve a problem. | A specialized form of recursion used to explore all possible solutions and revert when a path is invalid. |
| Approach | Solves problems by breaking them into smaller subproblems. | Tries out all possible solutions and backtracks when a solution fails. |
| Exploration | Explores all paths without necessarily reversing steps. | Explores one path at a time and reverses (backtracks) if needed. |
| Usage | Used for problems like factorial, Fibonacci, and tree traversals. | Used for solving constraint-based problems like Sudoku, N-Queens, and maze solving. |
| Efficiency | It may be inefficient if it explores unnecessary branches. | More efficient as it prunes branches that don't lead to a solution. |
| Backtracking Mechanism | Does not necessarily undo previous steps. | Explicitly undoes previous choices when a solution path fails. |
| Example Problem | Computing Fibonacci numbers using recursion. | Solving a Sudoku puzzle by trying numbers and backtracking when needed. |
Here are the advantages and disadvantages of backtracking in DAA:
Here are the advantages of Backtracking in DAA:
Below are the disadvantages of backtracking:
The time complexity of backtracking algorithms varies:
| Problem | Time Complexity (O(b^d)) | Space Complexity |
|---|---|---|
| N-Queens Problem | O(N!) (Factorial growth) | O(N) (for recursion stack) |
| Sudoku Solver | O(9^k) | O(k) (for recursion stack) |
| Graph Coloring Problem | O(m^N) | O(N) (for recursion stack) |
| Subset Sum Problem | O(2^N) (Exponential) | O(N) (for recursion stack) |
| Word Search Puzzle | O(4^L) | O(L) (for recursion stack) |
| Maze Solving | O(2^N) | O(N) (for recursion stack) |
Backtracking in DAA is a fundamental technique that allows us to solve complex problems by exploring all possible solutions. Its recursive nature and ability to prune invalid paths make it a powerful tool for solving puzzles, optimization problems, and more. By understanding the backtracking algorithm, you can tackle a wide range of challenges in computer science and beyond.
Backtracking is a problem-solving technique used in programming where we try to build a solution step by step. If at any point we realize that the current path won't lead to a valid solution, we go back (backtrack) and try a different approach. This method is commonly used in solving puzzles, pathfinding, and optimization problems.
While both are algorithmic techniques used to solve problems, backtracking involves exploring all potential solutions and backtracking upon reaching invalid states. In contrast, dynamic programming solves problems by breaking them down into simpler subproblems and storing the results to avoid redundant computations.
Backtracking is commonly used in solving constraint satisfaction problems such as puzzles (e.g., Sudoku), combinatorial problems (e.g., generating permutations), and pathfinding problems (e.g., maze solving).
Yes, backtracking is a common approach to solve the N-Queens problem by placing queens on a chessboard one by one and backtracking whenever a conflict arises.
The efficiency of backtracking algorithms can be improved by implementing strategies such as constraint propagation, forward checking, and using heuristics to decide the order of variable assignments.
The two main types of backtracking are:
The 4 Queens problem is a variation of the N-Queens problem where four queens must be placed on a 4×4 chessboard so that no two queens attack each other. It is solved using backtracking by placing queens individually and undoing incorrect placements.
It is called backtracking because the algorithm "tracks back" by undoing previous steps when it reaches an invalid state, allowing it to explore alternative solutions systematically.
Backtracking follows the Depth-First Search (DFS) approach, as it deeply explores one branch of the solution space before backtracking and trying another branch.
A common example of backtracking is solving a Sudoku puzzle, where numbers are placed step by step, and incorrect placements are undone when an invalid state is reached.
Use backtracking when:
Source: NxtWave - CCBP Blog
Original URL: https://www.ccbp.in/blog/articles/backtracking-in-daa