Backtracking
Backtracking
Can be applied for the problems which search for a set of solutions or ask for
By
an optimal solution satisfying some constrains (conditions).
There will be a use of some criteria function P known as bounding function.
Prasanta K. Jana, IEEE Senior Member
Solution can be expressed as a n-tuple (x1, x2, …, xn)
Strategy:
1) At each time one component xi is used to test the modified bounding
function Pi(x1, x2, …, xi). If it satisfies the criteria, xi is included.
2) If it is realized that the partial vector (x1, x2, …, xi) in no way lead to an
optimal solution, then backtrack operation is performed.
Department of Computer Science and Engineering
Indian Institute of Technology (ISM), Dhanbad
E-mail: prasantajana@iitism.ac.in
An Example: Sum of subsets problem:
Solution type 1:
Or (1, 2, 4) and (3, 4) using indices of wi’s.
Solution type 2: n-tuple (x1, x2, …, xn) such that
xi {0,1} , 1≤ i ≤ n.
Then xi =0 if wi is not chosen and xi = 1 if wi is chosen.
Hence we have solutions (1, 1, 0, 1) and (0, 0, 1, 1)
Note:
Solution type 1 is called variable sized tuple solution
Solution type 2 is called variable sized tuple solution
Constraints:
i) No two tuples are same, e.g. (1, 2, 4) and (1, 4, 2)
n
ii) i1wi m
iii) xi < xi+1
Note: 2n distinct tuples for any solution type
They form the solution space of the problem.
This solution space can be organized by means of a tree organization:
Fig. 1. Using variable sized tuple solution: Solution space is defined by all paths
from root to any node
Fig. 2: Using fixed sized tuple solution: Solution space is defined by all paths from
root to any leaf node
Note: Nodes are numbered according to BFS order in both the cases. Once the tree
is built solutions can obtained by systematically search the tree.
Terminologies:
Problem State: Each node of the tree
Solution states: Are those problem states for which the path from the root to S
defines a tuple in the solution space-any node in Fig. 1 and every leaf node in Fig. 2
Answer states: Are those solution states S for which the path from the root to S
defines a tuple that is member of the set of solutions of the problem.
Backtrack Solution:
Task: Generated tree after backtracking to obtain the set of solutions.
n-queens Problem
To place n queens in an n×n chessboard such that no two attack, i.e., no two
queens will be placed
i) on the same row
ii) on the same column or
iii) on the same diagonal.
Fig. 1 One solution to 8-queens problem
Solution space consists of 88 8-tuples
Let us number the chessboard 1 through 8.
The queens are also numbered 1 through 8.
So we can assume that queen i is to be placed on row i.
Solution representations:
(x1, x2, …, xn) where xi is the column on which queen i is placed.
The tuple solution of the above figure is (4, 6, 8, 2, 7, 1, 3, 5)
Constraints:
i) No two xi’s to be same
ii) No two queens can be on the same diagonal.
If we impose constraint i), then
All solutions of 8-queens problem are the permutations 8-tuple (1, 2, 3, 4, 5,
6, 7, 8)
This reduces the solution space from 88 to 8!
General State Space Tree for 4-queens problem:
Fig. Nodes are numbered in DFS order.
Fig. An example of backtrack solution to 4-queens problem
Fig. Portion of the generated during backtrack
How do you test that no two queens will be placed on the same diagonal?
Observation 1: Every element on the same diagonal from the upper left to the
lower right has the same "row - column" value.
Observation 2: Every element on the same diagonal from the upper right to the
lower left has the same "row + column" value.
Now, suppose two queens are placed at positions (i, j) and (k, l).
Then they are on the same diagonal only if
i-j=k–l => j–l=i-k
or i + j = k + l => j – l = k - i
Combining, j-l i-k
Place(k, i) returns true if the Queen k can be placed in column i
Fig. Can a new queen be placed?
Fig. All solutions to n-queens problem
Graph Colouring Problem
Problem Statement:
m-Colouring:
Chromatic number:
An Example: 3- colourability of a graph:
Planner Graph:
4-colour problem of a planner graph: Coloring of a map (A famous special case)
An example of a map and its planar graph representation:
Important Note:
Note: We are interested for all possible solutions of m-colouring of a planer graph
Solution representation: For a graph with n nodes and m colours.
Let colours be represented by integers 1, 2, 3, …, m.
Then n-tuple solution: (x1, x2, …, xn) where xi is the colour of node i.
State Space tree:
Degree of each node:
Height:
Time Complexity:
No. of internal nodes
At each internal node, NextValue takes O(mn)
Hence total time:
Hamiltonian Cycle Problem
Problem Statement:
Fig. 1: Two graphs, one containing a Hamiltonian cycle
Assumption: To avoid same cycle we assume v1 is the start vertex
Tuple Solution: (x1, x2.. , xn) where xi represents the ith visited vertex of the cycle.
Fig. 2. Finding all Hamiltonian cycles
Fig. 3. Generating a next vertex
Task 1: Draw the state space tree and also draw the portion of the same generated
by the Hamiltonian backtrack algorithm for the following graph.
1 2
4 3
Task 2: Draw the state space tree and also draw the portion of the same generated
by m-colouring backtrack algorithm as given in Fig. 2 for the following graph.
1 2
4 3
