Design Technique: Backtracking
Algorithms
Backtracking Algorithms
A backtracking algorithm is a problem-solving algorithm that uses
a brute force approach to find the desired output.
The Brute force approach tries out all the possible solutions and choose
the desired/best solutions. So, its complexity will be very high. While, in
backtracking, only a few solutions are explored.
The term backtracking suggests if the current solution is not suitable,
then backtrack and try other solutions.
Backtracking is used to solve problems in which a sequence of objects is
chosen from a specified set so that the sequence satisfies some
criterion.
DAA (CS-204) PDPM IIITDM, Jabalpur 2
Backtracking Algorithms
Backtracking is a modified depth-first search of a tree.
It is the procedure whereby, after determining that a node can lead
to nothing but dead nodes, we go back (“backtrack”) to the node’s
parent and proceed with the search on the next child.
DAA (CS-204) PDPM IIITDM, Jabalpur 3
Backtracking Algorithms
• Based on depth-first recursive search
Approach
Backtrack(x)
if x is not a solution
return false
if x is a new solution
add to list of solutions
backtrack(expand x)
DAA (CS-204) PDPM IIITDM, Jabalpur 4
Backtracking Algorithms
Problem: We want to find all the possible ways of arranging 2 boys
and 1 girl on 3 benches. Constraint: Girl should not be on the
middle bench.
DAA (CS-204) PDPM IIITDM, Jabalpur 5
Brute-Force Approach
Problem: We want to find all the possible ways of arranging 2 boys
and 1 girl on 3 benches. Constraint: Girl should not be on the
middle bench.
There are a total of 3! = 6 possibilities. We will try all the possibilities
and get the possible solutions. We recursively try all the possibilities.
B1 B2 G
For better understanding, a state-space tree can be constructed.
DAA (CS-204) PDPM IIITDM, Jabalpur 6
Brute-Force Approach
Problem: We want to find all the possible ways of arranging 2 boys and 1
girl on 3 benches. Constraint: Girl should not be on the middle bench.
B1 B2 G
B2 G B1 G B1 B2
B1B2 B1G B2B1 B2G GB1 GB2
G B2 G B1 B2 B1
B1B2G B1GB2 B2B1G B2GB1 GB1B2 GB2B1
The state space tree
DAA (CS-204) PDPM IIITDM, Jabalpur 7
Brute-Force Approach
Problem: We want to find all the possible ways of arranging 2 boys and 1
girl on 3 benches. Constraint: Girl should not be on the middle bench.
Time Complexity
Total possibility for n
B1 G
boys and girls = n!
B2
Time taken to find the
solution that satisfy the
B2 G B1 B2
constraint= n*n!
B1 G
Total time= O(n*n!)
B1B2 B1G B2B1 B2G GB1 GB2
G B2 G B1 B2 B1
B1B2G B1GB2 B2B1G B2GB1 GB1B2 GB2B1
The state space tree
DAA (CS-204) PDPM IIITDM, Jabalpur 8
Backtracking Algorithms
Problem: We want to find all the possible ways of arranging 2 boys and 1 girl on
3 benches. Constraint: Girl should not be on the middle bench.
In backtracking, if a generated sub solutions do not satisfy the constraint, then
backtrack and try other possible solutions. No need to generate all possible
solutions.
Backtrack Backtrack
DAA (CS-204) PDPM IIITDM, Jabalpur 9
The N-Queens Problem
Problem: To place n - queens in such a manner on an n x n chessboard that no
queens attack each other by being in the same row, column or diagonal.
Constraint: Queens cannot be placed in the same row, column or diagonal.
0 1 2 3
For the given queen placement, following
locations in the chess board will be under 0
attack.
Row Col. Dig.1 Diag.2 1 Q
(1,0) (0, 2) (0,1) (3,0)
(1,1) (2,2) (2,3) (2,1)
(1,3) (3,2) (0,3) 2
Dig. 1 attack positions = 0-1 = 2-3 => -1 3
Dig. 2 attack positions= 3+0= 2+1= 0+3
DAA (CS-204) PDPM IIITDM, Jabalpur 10
The N-Queens Problem
Place 0th queen at 0th column of 0th row.
Positions
(0,0)
0th level Q
1st
2nd
0 1 2 3
0 Q0
3rd
1
DAA (CS-204) PDPM IIITDM, Jabalpur 11
The N-Queens Problem
Call recursive function and place 1st queen
It will be placed at 2nd column of row 1, since other positions can be attacked by the
Q0.
Positions
0th level Q0
(0,0)
(1,2)
1st Q1
2nd
0 1 2 3
0 Q0
3rd
1 Q1
2
DAA (CS-204) PDPM IIITDM, Jabalpur 12
The N-Queens Problem
Call recursive function and place 2nd queen
It cannot be placed at any column of row 2, since all positions can be attacked by
other queens.
Positions
0th level Q0
(0,0)
(1,2)
1st Q1
F
2nd
Dead end 0 1 2 3
X 0 Q0
3rd
1 Q1
2
DAA (CS-204) PDPM IIITDM, Jabalpur 13
The N-Queens Problem
Return false to the calling function and shift queen at level 1 to one position
right.
Positions
0th level Q0
(0,0)
(1,3)
1st Q1
F
2nd
Dead end 0 1 2 3
X 0 Q0
3rd
1 Q1
2
DAA (CS-204) PDPM IIITDM, Jabalpur 14
The N-Queens Problem
Call recursive function and place 2nd queen
It can be placed at 1st column of row 2.
Positions
0th level Q0
(0,0)
(1,3)
(2,1)
1st Q1
F
2nd Q2
Dead end 0 1 2 3
X 0 Q0
3rd
1 Q1
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 15
The N-Queens Problem
Call recursive function and place 3rd queen
It cannot be placed at any column of row 3, since all positions can be attacked by
other queens.
Positions
0th level Q0
(0,0)
(1,3)
(2,1)
1st Q1
F
2nd Q2
Dead end 0 1 2 3
X 0 Q0
3rd
Dead end 1 Q1
X
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 16
The N-Queens Problem
Return false to the calling function and shift queen at level 2 to one position right
and check for the attack. If positions can be attack keep shifting until all positions
are explored.
Positions
0th level Q0
(0,0)
(1,3)
(2,1)
1st Q1
F
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 17
The N-Queens Problem
Shift queen at level 2 to one position right and check for the attack. If positions can
be attack keep shifting until all positions are explored.
Positions
0th level Q0
(0,0)
(1,3)
(2,2)
1st Q1
Can be
F attacked
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 18
The N-Queens Problem
Shift queen at level 2 to one position right and check for the attack. If positions can
be attack keep shifting until all positions are explored.
Positions
0th level Q0
(0,0)
(1,3)
(2,3)
1st Q1
Can be
F attacked
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 19
The N-Queens Problem
Since all positions at level 2 can be attacked so remove Q2 from its position and
return false to the calling function (one level up).
Positions
0th level Q0
(0,0)
(1,3)
(2,3)
1st Q1
F
F
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2
DAA (CS-204) PDPM IIITDM, Jabalpur 20
The N-Queens Problem
Shift queen at level 1 to one position right, if any block is available, otherwise return
false to the calling function (one level up).
Positions
0th level Q0
(0,0)
F (1,3)
(2,3)
1st Q1
F
F
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1
X
2
DAA (CS-204) PDPM IIITDM, Jabalpur 21
The N-Queens Problem
Shift queen at level 0 to one position right and update the position list.
Positions
0th level Q0 (0,1)
F (1,3)
(2,3)
1st Q1
F
F
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1
X
2
DAA (CS-204) PDPM IIITDM, Jabalpur 22
The N-Queens Problem
Call recursive function and place 1st queen
It will be placed at 3rd column of row 1, since other positions can be attacked by the
Q0.
Positions
0th level Q0 (0,1)
F (1,3)
1st Q1 Q1
F
F
2nd Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2
DAA (CS-204) PDPM IIITDM, Jabalpur 23
The N-Queens Problem
Call recursive function and place 2nd queen
It will be placed at 0th column of row 2, since other positions can be attacked by the
Q0.
Positions
0th level Q0 (0,1)
F (1,3)
(2,0)
1st Q1 Q1
F
F
2nd Q2 Q2
Dead end 0 1 2 3
F
X 0 Q0
3rd
Dead end 1 Q1
X
2 Q2
3
DAA (CS-204) PDPM IIITDM, Jabalpur 24
The N-Queens Problem
Call recursive function and place 3rd queen
It will be placed at 3rd column of row 3, since other positions can be attacked by the
Q0.
Positions
0th level Q0 (0,1)
T (1,3)
F
(2,0)
1st Q1 Q1
F (3,2)
T
F
2nd Q2 Q2
Dead end T 0 1 2 3
F
X 0 Q0
3rd Q3
Dead end 1 Q1
X
2 Q2
3
Q3
DAA (CS-204) PDPM IIITDM, Jabalpur 25
The N-Queens Problem
bool isSafe(int arr[][], int x, int y, int n) row=x, col=y;
{
while(row>=0 && col<n)
for (int row=0;row<x;row++)
{
{
if(arr[row][col]==1)
if(arr[row][y]==1)
{ {
return false; return false;
}
}
}
int row=x, int col=y; row--, col++;
while(row>=0 && col>=0) }
{ return true;
if(arr[row][col]==1)
}
{
return false;
}
row--, col--;
}
DAA (CS-204) PDPM IIITDM, Jabalpur 26
The N-Queens Problem
bool NQ(int arr[][], int row, int N)
{
if (row> == n)
return true;
for (int col = 0; col < N; col++)
{
if (isSafe(arr, row, col, N))
{
arr[row][col] = 1;
if (NQ(arr, row + 1, N)){
return true;
}
arr[row][col] = 0; //backtracking
}
}
return false;
}
DAA (CS-204) PDPM IIITDM, Jabalpur 27
The N-Queens Problem
Time Complexity : O(N!), Since we have N choices in the first row,
then N-1 choices in the second row and so on so the overall
complexity become O(N!)
Space Complexity: O(N*N)
DAA (CS-204) PDPM IIITDM, Jabalpur 28
Rat in a Maze problem
Problem: Given a maze[][] of n*n matrix, a rat has to find path from source
to destination. The top corner maze [0][0] is the source, and the right
bottom corner [n-1][n-1] is the destination. The rat can move in two
directions- right and down. In the maze, 1 represent free space and 0 means
it is blocked/ dead end.
Use the concept of backtracking and print the path from (0,0) to (n-1, n-1) if
exists else print -1;
DAA (CS-204) PDPM IIITDM, Jabalpur 29
Rat in a Maze problem
The following is the binary representation of the mentioned maze.
1.{1, 0, 0, 0}
2.{1, 1, 0, 1}
3.{0, 1, 0, 0}
4.{1, 1, 1, 1}
Here, 1 means that the cell is open, and the rat can enter. 0 means the cell is
blocked, and the rat cannot enter.
DAA (CS-204) PDPM IIITDM, Jabalpur 30
Rat in a Maze problem
The following is the binary representation of the path shown in the above
diagram.
1.{1, 0, 0, 0}
2.{1, 1, 0, 0}
3.{0, 1, 0, 0}
4.{0, 1, 1, 1}
Only the entries marked using the number 1 represent the path.
DAA (CS-204) PDPM IIITDM, Jabalpur 31
Rat in a Maze problem
Backtrack
DAA (CS-204) PDPM IIITDM, Jabalpur 32
Rat in a Maze problem
Backtrack
DAA (CS-204) PDPM IIITDM, Jabalpur 33
Rat in a Maze problem
Reached to
destination
DAA (CS-204) PDPM IIITDM, Jabalpur 34
Rat in a Maze problem
bool isSafe(int arr[][], int x, y, int n) {
if(x<n && y<n && arr[x][y]==1){
return true;
}
return false;
}
bool ratinMaze(int arr[][], int x, int y, int n int sol[][]){
if(x==n-1 && y==n-1){
sol[x][y]=1;
return true; }
if(isSafe(arr, x, y, n) {
sol[x][y]=1;
if(ratinMaze(arr, x+1, y, n, sol)){
return true;}
if(ratinMaze(arr, x, y+1, n, sol)){
return true; }
sol[x][y]=0; // Backtracking
return false;
}
ratinMaze(arr, 0,0, n, sol)
return false;
}
DAA (CS-204) PDPM IIITDM, Jabalpur 35
The N-Queens Problem
Time Complexity-
The number of moves possible for rat is two. The algorithm can go down and
go right and then try out every possibility to fill the lower square. Time
complexity for the backtracking solution = O(2n^2 ) because we need to
consider two different paths at every position.
Space Complexity – O(n2), since to keep the input and solution, 2-D array is
used.
DAA (CS-204) PDPM IIITDM, Jabalpur 36
