Backtracking

V. Balasubramanian
Introduction
 introduce two algorithm design techniques—
backtracking and branch-and-bound—that often make
it possible to solve at least
 some large instances of difficult combinatorial problems.
Both strategies can be
 considered an improvement over exhaustive search,
 The name first coined by D.H. Lehmer

2 Algorithms (eadeli@iust.ac.ir)
Tackling Difficult Combinatorial Problems

There are two principal approaches to tackling difficult

combinatorial problems (NP-hard problems):

 Use a strategy that guarantees solving the problem

exactly but doesn’t guarantee to find a solution in
polynomial time

 Use an approximation algorithm that can find an

approximate (sub-optimal) solution in polynomial time
Exact Solution Strategies
 exhaustive search (brute force)
 useful only for small instances

 dynamic programming
 applicable to some problems (e.g., the knapsack problem)

 backtracking
 eliminates some unnecessary cases from consideration
 yields solutions in reasonable time for many instances but worst
case is still exponential

 branch-and-bound
 further refines the backtracking idea for optimization problems
Backtracking
 Construct the state-space tree
 nodes: partial solutions
 edges: choices in extending partial solutions

 Explore the state space tree using depth-first search

 “Prune” nonpromising nodes

 dfs stops exploring subtrees rooted at nodes that cannot
lead to a solution and backtracks to such a node’s parent to
continue the search
 Basic idea of backtracking
 • Desired solution expressed as an n-tuple (x1,x2,…,xn)
where xi are chosen from
 some set Si
 – If |Si|=mi, m=m1m2..mn candidates are possible
 • Brute force approach
 – Forming all candidates, evaluate each one, and saving the
optimum one

6 Algorithms (eadeli@iust.ac.ir)
 Backtracking
 •Yielding the same answer with far fewer than m trials
 “Its basic idea is to build up the solution vector one
component at a time and to use modified criterion
function Pi(x1,..,xi) (sometimes called
 bounding function) to test whether the vector being
formed has any chance of success. The major advantage is:
if it is realized that the partial vector (x1,..,xi) can in no
way lead to an optimum solution, then
 mi+1…mn possible test vectors can be ignored entirely.”
 Based on depth-first recursive search
7 Algorithms (eadeli@iust.ac.ir)
8 Algorithms (eadeli@iust.ac.ir)
9 Algorithms (eadeli@iust.ac.ir)
10 Algorithms (eadeli@iust.ac.ir)
 1 2 3 4
1 queen 1
2 queen 2
3 queen 3
4 queen 4

11 Algorithms (eadeli@iust.ac.ir)
State Space tree

12 Algorithms (eadeli@iust.ac.ir)
13 Algorithms (eadeli@iust.ac.ir)
 N-queens:
 void NQueens(int k, int n)
 // Using backtracking, this procedure prints all
 // possible placements of n queens on an nXn
 // chessboard so that they are nonattacking.
 {
 for (int i=1; i<=n; i++) {
 if (Place(k, i)) {
 x[k] = i;
 if (k==n) { for (int j=1;j<=n;j++)
 cout << x[j] << ' '; cout << endl;}
 else NQueens(k+1, n);
 }
 }
 }
14 Algorithms (eadeli@iust.ac.ir)
 bool Place(int k, int i)
 // Returns true if a queen can be placed in kth row and
 // ith column. Otherwise it returns false. x[] is a
 // global array whose first (k-1) values have been set.
 // abs(r) returns the absolute value of r.
 {
 for (int j=1; j < k; j++)
 if ((x[j] == i) // Two in the same column
 || (abs(x[j]-i) == abs(j-k)))
 // or in the same diagonal
 return(false);
 return(true);
 }
15 Algorithms (eadeli@iust.ac.ir)
The idea

 Maze of hedges by Hampton Court Palace

 A sequence of objects is chosen from a specified set so
that the sequence satisfies some criterion
 Example: n-Queens problem
 Sequence: n positions on the chessboard
 Set: n2 possible positions
 Criterion: no two queens can threaten each other
 Depth-first search of a tree (preorder tree traversal)

16
Depth first search

17
The algorithm

18
4-Queens problem

 State space tree

19
If checking each candidate solution …

20
Looking for signs for dead ends

21
Backtracking
 Nonpromising node
 Promising node
 Promising function
 Pruning the state space tree
 Pruned state space tree

22
The generic algorithm

23
4-Queens problem (1)

24
4-Queens problem (2)

25
4-Queens problem (3)

26
4-Queens problem (4)

27
4-Queens problem (5)

28
Pruned state space tree

29
Avoid creating nonpromising nodes

30
The n-Queens Problem

 Check whether two queens threaten

each other:
 col(i) – col(k) = i – k
 col(i) – col(k) = k - i

31
Efficiency

 Checking the entire state space tree (number of nodes

checked)

 Taking the advantage that no two queens can be placed in

the same row or in the same column
1 + n + n(n-1) + n(n-1)(n-2) + … + n! promising nodes

32
Comparison

33
The Sum-of-Subsets Problem

34
State Space Tree

 w1 = 2, w2 = 4, w3 = 5

35
When W = 6 and w1 = 2, w2 = 4, w3 = 5

36
To check whether a node is promising
 Sort the weights in nondecreasing order
 To check the node at level i
 weight + wi+1 > W
 weight + total < W

37
When W = 13 and w1 = 3, w2 = 4, w3 = 5, w4 = 6

38
The algorithm 5.4
void sum_of_subsets (index i, int weight, int total){
if (promising (i))
if (weight == W)
cout << include [1] through include [i];
else{
include [i + 1] = "yes";
sum_of_subsets (i + 1, weight + w[i + 1], total - w[i + 1]);
include [i + 1] = "no";
sum_of_subsets (i + 1, weight, total - w [i + 1]);
}
}

bool promising (index i);{

return (weight + total >=W) &&
(weight == W || weight + w[i + 1] <= W);
}
39
Time complexity

 The first call to the function

sum_of_subsets(0, 0, total) where
n
total   w[ j ]
j 1

 The number of nodes checked

1 + 2 + 22 + … + 2n = 2n+1

40
Graph coloring
 The m-Coloring problem
 Finding all ways to color an undirected graph using at most m
different colors, so that no two adjacent vertices are the same
color.
 Usually the m-Coloring problem consider as a unique problem
for each value of m.

41
Example

 2-coloring problem
 No solution!
 3-coloring problem
Vertex Color
v1 color1
v2 color2
v3 color3
v4 color2

42
Application: Coloring of maps
 Planar graph
 It can be drawn in a plane in such a way that no two edges
cross each other.

 To every map there corresponds a planar graph

43
Example (1)
 Map

44
Example (2)
 corresponded planar graph

45
The pruned state space tree

46
Algorithm 5.5 (1)

void m_coloring (index i) {

int color;
if (promising (i))
if (i == n)
cout << vcolor [1] through vcolor [n];
else
for (color = 1; color <= m; color++){
vcolor [i + 1] = color;
m_coloring (i + 1);
}
}
47
Algorithm 5.5 (2)

bool promising (index i) {

index j;
bool switch;
switch = true;
j = 1;
while (j<i && switch){
if (W[i][j] && vcolor[i] == vcolor[j])
switch = false;
j++;
}
return switch;
}

48
Algorithm 5.5 (3)
 The top level call to m_coloring
 m_coloring(0)
 The number of nodes in the state space tree for this
algorithm

49
The Hamiltonian Circuits Problem
 The traveling sales person problem
 Chapter 3: Dynamic programming
 T(n) = (n-1)(n-2)2n-3
 Hamiltonian Circuit (also called a tour)
 Given a connected, undirected graph
 A path that starts at a given vertex, visits each vertex in the
graph exactly once, and ends at the starting vertex

50
Example (1)
 Hamiltonian Circuit
 [v1, v2, v8, v7, v6, v5, v4, v3, v2]

51
Example (2)
 No Hamiltonian Circuit!

52
Algorithm 5.6 (1)

void hamiltonian (index i) {

index j;
if (promising (i))
if (i == n-1)
cout << vindex [0] through vindex [n - 1];
else
for (j = 2; j <=n; j++){
vindex [i + 1] = j;
hamiltonian (i + 1);
}
}

53
Algorithm 5.6 (2)
bool promising (index i) {
index j;
bool switch;
if (i == n-1 && !W[vindex[n - 1]] [vindex [0]])
switch = false;
else if (i > 0 && !W[vindex[i - 1]] [vindex [i]])
switch = false;
else{
switch = true;
j = 1;
while (j < i && switch){
if (vindex[i] == vindex [j])
switch = false; j++;
}
}
return switch;
}

54
Example
 bool Place(int k, int i) // Returns true if a queen can be
placed in kth row and // ith column. Otherwise it returns
false. x[] is a // global array whose first (k-1) values have
been set. // abs(r) returns the absolute value of r. { for (int
j=1; j < k; j++) if ((x[j] == i) // Two in the same column ||
(abs(x[j]-i) == abs(j-k))) // or in the same diagonal
return(false); return(true); }
N-Queens algorithm place(int k,int i)
 bool Place(int k, int i)
 // Returns true if a queen can be placed in kth row and // ith column.
Otherwise it returns false. x[] is a
 // global array whose first (k-1) values have been set.
 // abs(r) returns the absolute value of r.
 {
 for (int j=1; j < k; j++)
 if ((x[j] == i) // Two in the same column
 || (abs(x[j]-i) == abs(j-k)))
 // or in the same diagonal
return(false);
return(true);
}
N-Queens algorithm
 void NQueens(int k, int n)
 // Using backtracking, this procedure prints all
 // possible placements of n queens on an n X n
 // chessboard so that they are nonattacking.
 {
 for (int i=1; i<=n; i++)
 {
 if (Place(k, i))
 { x[k] = i;
 if (k==n) { for (int j=1;j<=n;j++)
 cout << x[j] << ' '; cout << endl;}
 else NQueens(k+1, n); } } }
Sum of subsets
 void SumOfSub(float s, int k, float r)
 // Find all subsets of w[1:n] that sum to m. The values
 // of x[j], 1<=j<k, have already been determined.
 // s=sigma{j=1}^{k-1} w[j]*x[j] and r=sigma{j=k}^n
w[j].
 // The w[j]'s are in nondecreasing order.
 // It is assumed that w[1]<=m and sigma{i=1}^n w[i]>=m.
{
 // Generate left child. Note that s+w[k] <= m
 // because B_{k-1} is true.
 x[k] = 1;
 if (s+w[k] == m) { // Subset found
 for (int j=1; j<=k; j++) cout << x[j] << ' ';
 cout << endl; }
 // There is no recursive call here
 // as w[j] > 0, 1 <= j <= n.
 else if (s+w[k]+w[k+1] <= m)
 SumOfSub(s+w[k], k+1, r-w[k]);
Contd…
 // Generate right child and evaluate B_k.
 if ((s+r-w[k] >= m) && (s+w[k+1] <= m)) {
 x[k] = 0;
 SumOfSub(s, k+1, r-w[k]); } }
Graph Coloring algorithm
 void mColoring(int k)
 // This program was formed using the recursive
backtracking
 // schema. The graph is represented by its boolean
adjacency
 // matrix G[1:n][1:n]. All assignments of 1,2,...,m to the
// vertices of the graph such that adjacent vertices are
 // assigned distinct integers are printed. k is the index of
// the next vertex to color.
Contd…
 { do { // Generate all legal assignments for x[k].
NextValue(k); // Assign to x[k] a legal color.
 if (!x[k]) break; // No new color possible
 if (k == n) { // At most m colors have been used
// to color the n vertices.
 for (int i=1; i<=n; i++) cout << x[i] << ' ';
 cout << endl; } //if
 else mColoring(k+1);
 } while(1);
 }
Contd… algorithm for next color
 void NextValue(int k)
 // x[1],..., x[k-1] have been assigned integer values in
 // the range [1,m] such that adjacent vertices have distinct
 // integers. A value for x[k] is determined in the range
 // [0,m]. x[k] is assigned the next highest numbered color
 // while maintaining distinctness from the adjacent vertices
 // of vertex k. If no such color exists, then x[k] is zero.
 {
Contd…
 do {
 x[k] = (x[k]+1) % (m+1); // Next highest color
 if (!x[k]) return; // All colors have been used.
 for (int j=1; j<=n; j++) { // Check if this color is //
distinct from adjacent colors.
 if ( G[k][j] // If (k, j) is an edge
 && (x[k] == x[j])) // and if adj. vertices have the same color
break; }
 if (j == n+1) return; // New color found
 } while (1); // Otherwise try to find another color.
 }
Hamiltonian circuit – Next Vertex
 void NextValue(int k)
 // x[1],...,x[k-1] is a path of k-1 distinct vertices. If
 // x[k]==0, then no vertex has as yet been assigned to x[k].
 // After execution x[k] is assigned to the next highest
 // numbered vertex which i) does not already appear in
 // x[1],x[2],...,x[k-1]; and ii) is connected by an edge
 // to x[k-1]. Otherwise x[k]==0. If k==n, then
 // in addition x[k] is connected to x[1].
 {
Contd…
 do {
 x[k] = (x[k]+1) % (n+1); // Next vertex
 if (!x[k]) return;
 if (G[x[k-1]][x[k]]) { // Is there an edge?
 for (int j=1; j<=k-1; j++) if (x[j]==x[k]) break; //
Check for distinctness.
 if (j==k) // If true, then the vertex is distinct.
 if ((k<n) || ((k==n) && G[x[n]][x[1]]))
 return;
 }
 } while(1);
 }
Contd…
 void Hamiltonian(int k)
 // This program uses the recursive formulation of
 // backtracking to find all the Hamiltonian cycles
 // of a graph. The graph is stored as an adjacency
 // matrix G[1:n][1:n]. All cycles begin at node 1.
 {
 do { // Generate values for x[k].
 NextValue(k); // Assign a legal next value to x[k].
 if (!x[k]) return;
 if (k == n) {
 for (int i=1; i<=n; i++) cout << x[i] << ' ';
 cout << "1\n";
 }
 else Hamiltonian(k+1);
 } while (1);
 }