Design and Analysis of

Algorithms
ALGORITHM DESIGN TECHNIQUES
 Greedy
 Shortest path, minimum spanning tree, …
 Divide and Conquer
 Divide the problem into smaller subproblems,
solve them, and combine into the overall solution
 Often done recursively
 Quick sort, merge sort are great examples
 Dynamic Programming
 Brute force through all possible solutions, storing
solutions to subproblems to avoid repeat computation
 Backtracking
 A clever form of exhaustive search
BACKTRACKING
 Suppose you have to make a series of
decisions, among various choices, where
 You don’t have enough information to know
what to choose
 Each decision leads to a new set of choices
 Some sequence of choices (possibly more than
one) may be a solution to your problem
 Backtracking is a methodical way of trying
out various sequences of decisions, until
you find the correct one that “works”.
BACKTRACKING
 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.
 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.
BACKTRACK ALGORITHM

 Based on depth-first recursive search

 Approach
1. Tests whether solution has been found
2. If found solution, return it
3. Else for each choice that can be made
a) Make that choice
b) Recursive
c) If recursion returns a solution, return it
4. If no choices remain, return failure
 Some times called “search tree”
BACKTRACKING EXAMPLES
 The backtracking can be used in this
cases:
 Solving a maze
 Coloring a map
 Solving a puzzle
 N queens problem etc.,
MAZES AND BACKTRACKING
 A example of something that can be solved using
backtracking is a maze.
 From your start point, you will iterate through each
possible starting move.
 From there, you recursively move forward.
 If you ever get stuck, the recursion takes you back to
where you were, and you try the next possible move.

 In dealing with a maze, to make sure you don't

try too many possibilities,
 one should mark which locations in the maze have
been visited already so that no location in the maze
gets visited twice.
 (If a place has already been visited, there is no point
in trying to reach the end of the maze from there
 BACKTRACKING: IDEA
 Backtracking is a technique used to solve problems with a
large search space, by systematically trying and
eliminating possibilities.
 A standard example of backtracking would be going
through a maze.
 At some point, you mightPortion B options of which direction to
have two
go:
Junction
Portion A
 BACKTRACKING
One strategy would on
t i
be to try going through Junc
Portion A of the maze. Portion B
 If you get stuck before
you find your way out,

Portion A
then you "backtrack" to
the junction.

Atthis point in time you

know that Portion A will
NOT lead you out of the
maze,
 so you then start
searching in Portion B
 BACKTRACKING

 Clearly, at a single junction

you could have even more
than 2 choices.

 The backtracking strategy

says to try each choice,
one after the other, i on
n ct
 if you ever get stuck, Ju C
"backtrack" to the junction
and try the next choice. B
A
 If you try all choices and
never found a way out,
then there IS no solution to
the maze.
BACKTRACKING

dead end

?
dead end
dead end

?
start ? ?
dead end

dead end

success!
BACKTRACKING TECHNIQUE

Backtracking is used to solve problems in which a feasible

solution is needed rather than an optimal one, such as the solution
to a maze or an arrangement of squares in the 15-puzzle.
Backtracking problems are typically a sequence of items (or
objects) chosen from a set of alternatives that satisfy some
criterion.
 BACKTRACKING IMPLEMENTATION

Backtracking is a modified depth-first search of the solution-space

tree. In the case of the maze the start location is the root of a tree,
that branches at each point in the maze where there is a choice of
direction.
SUDOKU AND BACKTRACKING
 Another common puzzle that can be solved by
backtracking is a Sudoku puzzle.

 The basic idea behind the solution is as follows:

1) Scan the board to look for an empty square that could take on
the fewest possible values based on the simple game
constraints.
2) If you find a square that can only be one possible value, fill it
in with that one value and continue the algorithm.
3) If no such square exists, place one of the possible numbers for
that square in the number and repeat the process.
4) If you ever get stuck, erase the last number placed and see if
there are other possible choices for that slot and try those
next.
 N Queens Problem
N queens problem is one of the
most common examples of
backtracking. Our goal is to
arrange N queens on an NxN
chessboard such that no queen can
strike down any other queen. A
queen can attack -
• horizontally,
• vertically,
• or diagonally.
So, we start by placing the first queen anywhere arbitrarily and then
place the next queen in any of the safe places. We continue this
process until the number of unplaced queens becomes zero (a
solution is found) or no safe place is left. If no safe place is left, then
we change the position of the previously placed queen.
Let's test this algorithm on a 4x4 chessboard.
 N-Queens Problem (cont.)
The problem of placing N queens on an NxN chessboard in such a
way that no two of them are "attacking" each other, is a classic
problem used to demonstrate the backtracking method.
A simple brute-force method would be to try placing the first
queens on the first square, followed by the second queen on the
first available square, scanning the chessboard in a row-column
manner.
A more efficient backtracking
approach is to note that each
queen must be in its own column
and row. This reduces the search
from (N2)! to N!.
 Using Backtracking to Solve N
Queens Problem
• The picture shows a 4x4
chessboard and we have to place
4 queens on it. So, we will start
by placing the first queen in the
first row.
  Using Backtracking to Solve N Queens
Problem
• Let's place the third queen in a
safe position, somewhere in the
thirdwe
• Now, row.
can see that there is
no safe place where we can
put the last queen. So, we will
just change the position of the
previous queen i.e., backtrack
and change the previous
decision.
• Also, there is no other position
where we can place the third
queen, so we will go back one
more step and change the
position of the second queen.
 Using Backtracking to Solve N Queens
Problem

• And now we will place the third

queen again in a safe position
other than the previously placed
position in the third row.

• We will continue this process

and finally, we will get the
solution as shown below
N-QUEENS PROBLEM

Problem:
-- How do we represent the search
space?
 State space tree to represent
N-Queens Problem

Fig shows the complete state space for 4 - queens problem.

But we can use backtracking method to generate the
necessary node and stop if the next node violates the rule,
 State space tree to represent
N-Queens Problem
 Algorithm of N-Queens
Problem

N - Queens (k, n) Place (k, i) return true if a

{ queen can be placed in
For i ← 1 to n the kth row and ith
do if Place (k, i) then column otherwise return
{ is false.
x [k] ← i;
if (k ==n) then
write (x [1....n));
else
N - Queens (k + 1, n);
}
}
 Algorithm of N-Queens
Problem (i-1, j-1)

Place (k, i)
{
For j ← 1 to k - 1
(i+1, j-1)(i+1, j+1)
do if (x [j] = i)
or (Abs (x [j]) - i)) = (Abs (j
- k))
then return false;
return true;
}
x [] is a global array whose final k - 1 values have been set.
Abs (r) returns the absolute value of r.

Place (k, i) returns a Boolean value that is true if the kth queen
can be placed in column i. It tests both whether i is distinct
from all previous costs x1, x2,....xk-1 and whether there is no
other queen on the same diagonal.
 Code Snippet of N-Queens
Problem
int canPlace(int k, int i){
void nQueens(int k, int n){ int j;
int i; for (j = 1;j <= k - 1;j++){
for (i=1;i <= n;i++){ if (arr[j] == i ||
(abs(arr[j]
if (canPlace(k, i))
- i) == abs(j - k)))
{ return 0;
arr[k] = i; }
if (k == n) return 1;
}
display(n);
else int main(){
int n=4;
nQueens(k + 1, n); nQueens(1,n);
} return 0;
}
}
}
 What is the maximum number of
queens that can be placed on an n x n
chessboard such that no two attack
one another?
 The answer is n queens, which gives
eight queens for the usual 8x8 board
 POSSIBLE SOLUTION SET
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q

Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q

All possible solutions for

N=5
 POSSIBLE SOLUTION SET
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q

Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q
Q Q Q Q Q

Only 2 unique solutions for N=5

(notice transformations & reflections)
BACKTRACKING EXAMPLE—8 QUEENS PROBLEM

 The 8-queens problem is a classical

combinatorial problem in which it is required
to place eight queens on an 8 x 8
chessboard so no two can attack each other.

 A queen can attack another queen if it

exists in the same row, column or diagonal
as the queen.

31
SOLUTION: BACKTRACKING
 place a queen in the top row, then note the column and
diagonals it occupies.
 then place a queen in the next row down, taking care not to
place it in the same column or diagonal. Keep track of the
occupied columns and diagonals and move on to the next
row.
 If no position is open in the next row, we back track to the
previous row and move the queen over to the next
available spot in its row and the process starts over again.
THE "8 QUEENS" PROBLEM
 Consider the problem of trying to place 8 queens on
a chess board such that no queen can attack
another queen.
Q

Q
 What are the "choices"?
Q
 How do we "make" or Q
"un-make" a choice?
Q

 How do we know when Q

to stop? Q

Q
NAIVE ALGORITHM
 for (each square on board):
1 2 3 4 5 6 7 8
 Place a queen there.
1 Q ... ... ... ... ... ... ...
 Try to place the rest
2 ... ... ... ... ... ... ... ...
of the queens.
 Un-place the queen.3 ...

5
 How large is the 6
solution space for
this algorithm? 7
 64 * 63 * 62 * ... 8
BETTER ALGORITHM IDEA
 Observation: In a working
1 2 3 4 5 6 7 8
solution, exactly 1 queen
must appear in each
1 Q ... ...

row and in 2 ... ...

each column. 3 Q ...

4 ...
 Redefine a "choice"
5 Q
to be valid placement
6
of a queen in a
7
particular column.
8
BACKTRACKING – EIGHT QUEENS
PROBLEM
 Find an arrangement of 8
queens on a single chess
board such that no two
queens are attacking one
another.

 In chess, queens can move

all the way down any row,
column or diagonal (so long
as no pieces are in the way).

 Due to the first two

restrictions, it's clear that
each row and column of the
board will have exactly one
queen.
 BACKTRACKING – EIGHT QUEENS
PROBLEM
 The backtracking strategy is Q
as follows:
1) Place a queen on the first
Q
available square in row 1. Q
Q
2) Move onto the next row,
placing a queen on the first
Q Q
available square there (that
doesn't conflict with the Continue…
previously placed queens).

3) Continue in this fashion until

either:
a) you have solved the problem,
or
b) you get stuck.
 When you get stuck, remove the
queens that got you there, until
you get to a row where there is
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 This problem can be solved by trying to

place the first queen, then the second
queen so that it cannot attack the first,
and then the third so that it is not
conflicting with previously placed
queens.
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 It is an empty 8 x 8
chess board. We
have to place the
queens in this board.
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 We have placed the

first queen on the
chess board
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 Then we have
placed the second
queen on the board.
 The darken place
should not have the
queens because
they are horizontal,
vertical, diagonal to
the placed queens.
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 We have placed the

third queen on
board.
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 We have placed the

4th queen on the
board.
 If at any point, we
placed that in the
wrong spot, so we
backtrack and change
the place of that one.
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)

 In this way, we have

to continue the
process until our is
reached ie., we
must place 8
queens on the
board.
12 UNIQUE SOLUTIONS
8-QUEENS PROBLEM
BACKTRACKING EXAMPLE—8 QUEENS
PROBLEM(CONT…)
 Backtracking provides the hope to solve some
problem instances of nontrivial sizes by pruning
non-promising branches of the state-space tree.

 The success of backtracking varies from problem

to problem and from instance to instance.

 Backtracking possibly generates all possible

candidates in an exponentially growing state-
space tree.
 Graph Coloring Problem
• Graph Coloring is a process of assigning colors to the
vertices of a graph such that no two adjacent vertices of
it are assigned the same color.

• Graph Coloring is also called as Vertex Coloring.

• It ensures that there exists no edge in the graph whose end
vertices are colored with the same color.
• Such a graph is called as a Properly colored graph.
Graph Coloring Example-

The following graph is an example of

a properly colored graph-
In this graph,

• No two adjacent vertices are

colored with the same color.
• Therefore, it is a properly
colored graph.
 Graph Coloring Applications

Some important applications of graph

coloring are as follows-

• Map Coloring
• Scheduling the tasks
• Preparing Time Table
• Assignment
• Conflict Resolution
• Sudoku

Chromatic Number-
• Chromatic Number is the minimum number of
colors required to properly color any graph.
OR
• Chromatic Number is the minimum number of
colors required to color any graph such that no
• two adjacent vertices of it are assigned the same
color.
 Chromatic Number
 State space tree

• We start by coloring a single

vertex, then we move to its adjacent
vertex. We color it with that color
which has not been used to color
any of its connected vertices. After
coloring it we then move to its
adjacent vertex which is uncolored.
We repeat the process until all vertices
of the given graph are colored.

• In case we find for a vertex that all its

adjacent (connected) are colored with
different colors and no color is left to
make it color different from them,
then it means the given number of
  Code Snippet for finding the m - colorings of
a graph
void next_color(int k){
int i,j;
x[k]=1; //coloring vertex with
color1
for(i=0;i<k;i++){ //checking all k-1
vertices-backtracking
if(G[i][k]!=0 && x[k]==x[i]) //if
connected and has same color
x[k]=x[i]+1; //assign higher
color than x[i]
}
}
How to solve the problem : First take input number of vertices and
edges in graph G. Then input all the indexes of adjacency matrix of G
whose value is 1. Now we will try to color each of the vertex. A
next_color(k) function takes in index of the kth vertex which is to be
colored. First we assign color1 to the kth vertex.Then we check whether it
is connected to any of previous (k-1) vertices using backtracking. If
connected then assign a color x[i]+1 where x[i] is the color of ith vertex
RECALL: BACKTRACKING

A general pseudo-code algorithm for

backtracking problems:

Explore(choices):
 if there are no more choices to make:
stop.
 else, for each available choice C:
 Choose C.
 Explore the remaining choices.
 Un-choose C, if necessary. (backtrack!)