Introduction to Backtracking
Backtracking is like trying different paths, and when you hit a dead end,
you backtrack to the last choice and try a different route. In this article,
we’ll explore the basics of backtracking, how it works, and how it can help
solve all sorts of challenging problems. It’s like a method for finding the
right way through a complex choices.
What is Backtracking?
Backtracking is a problem-solving algorithmic technique that involves
finding a solution incrementally by trying different options and undoing
them if they lead to a dead end. It is commonly used in situations where
you need to explore multiple possibilities to solve a problem, like
searching for a path in a maze or solving puzzles like Sudoku. When a
dead end is reached, the algorithm backtracks to the previous decision
point and explores a different path until a solution is found or all
possibilities have been exhausted.
Backtracking can be defined as a general algorithmic technique that
considers searching every possible combination in order to solve a
computational problem.
Basic Terminologies
Candidate: A candidate is a potential choice or element that can be
added to the current solution.
Solution: The solution is a valid and complete configuration that
satisfies all problem constraints.
Partial Solution: A partial solution is an intermediate or incomplete
configuration being constructed during the backtracking process.
Decision Space: The decision space is the set of all possible
candidates or choices at each decision point.
Decision Point: A decision point is a specific step in the algorithm
where a candidate is chosen and added to the partial solution.
Feasible Solution: A feasible solution is a partial or complete
solution that adheres to all constraints.
Dead End: A dead end occurs when a partial solution cannot be
extended without violating constraints.
Backtrack: Backtracking involves undoing previous decisions and
returning to a prior decision point.
Search Space: The search space includes all possible
combinations of candidates and choices.
Optimal Solution: In optimization problems, the optimal solution is
the best possible solution.
Types of Backtracking Problems
Problems associated with backtracking can be categorized into 3
categories:
Decision Problems: Here, we search for a feasible solution.
Optimization Problems: For this type, we search for the best
solution.
Enumeration Problems: We find set of all possible feasible
solutions to the problems of this type.
How does Backtracking works
As we know backtracking algorithm explores each and every possible
path in order to find a valid solution, this exploration of path can be easily
understood via given images:
As shown in the image, “IS” represents the Initial State where the
recursion call starts to find a valid solution.
C : it represents different Checkpoints for recursive calls
TN: it represents the Terminal Nodes where no further recursive calls
can be made, these nodes act as base case of recursion and we
determine whether the current solution is valid or not at this state.
At each Checkpoint, our program makes some decisions and move to
other checkpoints until it reaches a terminal Node, after determining
whether a solution is valid or not, the program starts to revert back to the
checkpoints and try to explore other paths. For example in the above
image TN1…TN5 are the terminal node where the solution is not
acceptable, while TN6 is the state where we found a valid solution.
The back arrows in the images shows backtracking in actions, where we
revert the changes made by some checkpoint.
Determining Backtracking Problems:
Generally every constraint satisfaction problem can be solved using
backtracking but, Is it optimal to use backtracking every time? Turns
out NO, there are a vast number of problem that can be solved
using Greedy or Dynamic programming in logarithmic or polynomial time
complexity which is far better than exponential complexity of Backtracking.
However many problems still exists that can only be solved using
Backtracking.
To understand whether a problem is backtracking based or not, let us take
a simple problem:
Problem: Imagine you have 3 closed boxes, among which 2 are empty
and 1 has a gold coin. Your task is to get the gold coin.
Why dynamic programming fails to solve this question:
Does opening or closing one box has any effect on the other box? Turns
out NO, each and every box is independent of each other and
opening/closing state of one box cannot determine the transition for other
boxes. Hence DP fails.
Why greedy fails to solve this question:
Greedy algorithm chooses a local maxima in order to get global maxima,
but in this problem each and every box has equal probability of having a
gold coin i.e 1/3 hence there is no criteria to make a greedy choice.
Why Backtracking works:
As discussed already, backtracking algorithm is simply brute forcing each
and every choice, hence we can one by one choose every box to find the
gold coin, If a box is found empty we can close it back which acts as a
Backtracking step.
Technically, for backtracking problems:
The algorithm builds a solution by exploring all possible paths
created by the choices in the problem, this solution begins with an
empty set S={}
Each choice creates a new sub-tree ‘s’ which we add into are set.
Now there exist two cases:
S+s is valid set
S+s is not valid set
In case the set is valid then we further make choices and repeat the
process until a solution is found, otherwise we backtrack our decision
of including ‘s’ and explore other paths until a solution is found or all
the possible paths are exhausted.
Pseudo code for Backtracking
The best way to implement backtracking is through recursion, and all
backtracking code can be summarised as per the given Pseudo code:
void FIND_SOLUTIONS( parameters):
if (valid solution):
store the solution
Return
for (all choice):
if (valid choice):
APPLY (choice)
FIND_SOLUTIONS (parameters)
BACKTRACK (remove choice)
Return
Complexity Analysis of Backtracking
Since backtracking algorithm is purely brute force therefore in terms of
time complexity, it performs very poorly. Generally backtracking can be
seen having below mentioned time complexities:
Exponential (O(K^N))
Factorial (O(N!))
These complexities are due to the fact that at each state we have multiple
choices due to which the number of paths increases and sub-trees
expand rapidly.
How Backtracking is different from Recursion?
Recursion and Backtracking are related concepts in computer science and
programming, but they are not the same thing. Let’s explore the key
differences between them:
Recursion Backtracking
Recursion does not always need Backtracking always uses recursion to
backtracking solve problems
Solving problems with multiple
Solving problems by breaking them
choices and exploring options
into smaller, similar sub problems and
systematically, backtracking when
solving them recursively.
needed.
Controlled by function calls and call Managed explicitly with loops and
stack. state.
Application of Backtracking: N
Applications of Recursion: Tree and
Queen problem, Rat in a Maze
Graph Traversal, Towers of Hanoi,
problem, Knight’s Tour Problem,
Divide and Conquer Algorithms, Merge
Sudoku solver, and Graph colouring
Sort, Quick Sort, and Binary Search.
problems.
Applications of Backtracking
Creating smart bots to play Board Games such as Chess.
Solving mazes and puzzles such as N-Queen problem.
Network Routing and Congestion Control.
Decryption
Text Justification
8 queen problem using Backtracking
Problem: The eight queen’s problem is the problem of placing eight
queens on an 8×8 chessboard such that none of them attack one another
(no two are in the same row, column, or diagonal). More generally, the n
queen’s problem places n queens on an n×n chessboard.
Explanation:
This pseudo code uses a backtracking algorithm to find a solution to
the 8 Queen problem, which consists of placing 8 queens on a
chessboard in such a way that no two queens threaten each other.
The algorithm starts by placing a queen on the first column, then it
proceeds to the next column and places a queen in the first safe row of
that column.
If the algorithm reaches the 8th column and all queens are placed in
a safe position, it prints the board and returns true.
If the algorithm is unable to place a queen in a safe position in a certain
column, it backtracks to the previous column and tries a different row.
The “is Safe” function checks if it is safe to place a queen on a
certain row and column by checking if there are any queens in the
same row, diagonal or anti-diagonal.
It’s worth to notice that this is just a high-level pseudo code and it
might need to be adapted depending on the specific implementation
and language you are using.
Here is an example of pseudo code for solving the 8 Queen problem
using backtracking:
#include <iostream>
#include <vector>
using namespace std;
const int N = 8;
bool isSafe(vector<vector<int> >& board, int row, int col)
{
for (int x = 0; x < col; x++)
if (board[row][x] == 1)
return false;
for (int x = row, y = col; x >= 0 && y >= 0; x--, y--)
if (board[x][y] == 1)
return false;
for (int x = row, y = col; x < N && y >= 0; x++, y--)
if (board[x][y] == 1)
return false;
return true;
}
bool solveNQueens(vector<vector<int> >& board, int col)
{
if (col == N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
cout << endl;
return true;
}
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueens(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
int main()
{
vector<vector<int> > board(N, vector<int>(N, 0));
if (!solveNQueens(board, 0))
cout << "No solution found";
return 0;
}
Output:
[[1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0], [0, 0,
0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0,
0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0]]
Time Complexity : O((m + q) log^2 n)
Space Complexity : O((m + q) log n)
