Unit -5 Backtracking

5.1 The general method

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.

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 untill
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.

5. Fixed 2 Tuple vs. Variable Tuple Formulation

5.3 n-queens problem
N - Queens problem is 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.

It can be seen that for n =1, the problem has a trivial solution, and no
solution exists for n =2 and n =3. So first we will consider the 4 queens
problem and then generate it to n - queens problem.

Given a 4 x 4 chessboard and number the rows and column of the

chessboard 1 through 4.

Since, we have to place 4 queens such as q 1 q2 q3 and q4 on the

chessboard, such that no two queens attack each other. In such a
conditional each queen must be placed on a different row, i.e., we put
queen "i" on row "i." Now, we place queen q 1 in the very first acceptable
position (1, 1). Next, we put queen q 2 so that both these queens do not
attack each other. We find that if we place q 2 in column 1 and 2, then the
dead end is encountered. Thus the first acceptable position for q 2 in
column 3, i.e. (2, 3) but then no position is left for placing queen 'q 3'
safely. So we backtrack one step and place the queen 'q 2' in (2, 4), the
next best possible solution. Then we obtain the position for placing 'q 3'
which is (3, 2). But later this position also leads to a dead end, and no
place is found where 'q4' can be placed safely. Then we have to backtrack
till 'q1' and place it to (1, 2) and then all other queens are placed safely by
moving q2 to (2, 4), q3 to (3, 1) and q4 to (4, 3). That is, we get the solution
(2, 4, 1, 3). This is one possible solution for the 4-queens problem. For
another possible solution, the whole method is repeated for all partial
solutions. The other solutions for 4 - queens problems is (3, 1, 4, 2) i.e.

The implicit tree for 4 - queen problem for a solution (2, 4, 1, 3) is as

follows:
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, i.e., if two queens are attacking.

It can be seen that all the solutions to the 4 queens problem can be
represented as 4 - tuples (x1, x2, x3, x4) where xi represents the column on
which queen "qi" is placed.

One possible solution for 8 queens problem is shown in fig:

1.
Thus, the solution for 8 -queen problem for (4, 6, 8, 2, 7, 1, 3, 5).
2. If two queens are placed at position (i, j) and (k, l).
3. Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.
4. The first equation implies that j - l = i - k.
5. The second equation implies that j - l = k - i.
6. Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|

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.

Place (k, i)
{
For j ← 1 to k - 1
do if (x [j] = i)
or (Abs x [j]) - i) = (Abs (j - k))
 then return false;
return true;
}

Place (k, i) return true if a queen can be placed in the kth row and ith
column otherwise return is false.

x [] is a global array whose final k - 1 values have been set. Abs (r)
returns the absolute value of r.

N - Queens (k, n)
{
For i ← 1 to n
do if Place (k, i) then
{
x [k] ← i;
if (k ==n) then
write (x [1....n));
else
N - Queens (k + 1, n);
}
}

5.4 Graph Colouring

Given an undirected graph and a number m, the task is to color the given graph with at most m colors
such that no two adjacent vertices of the graph are colored with the same color
Note: Here coloring of a graph means the assignment of colors to all vertices
Below is an example of a graph that can be colored with 3 different colors:
Assign colors one by one to different vertices, starting from vertex 0. Before assigning a color, check
for safety by considering already assigned colors to the adjacent vertices i.e check if the adjacent
vertices have the same color or not. If there is any color assignment that does not violate the
conditions, mark the color assignment as part of the solution. If no assignment of color is possible then
backtrack and return false
Follow the given steps to solve the problem:
 Create a recursive function that takes the graph, current index, number of vertices, and color array.
 If the current index is equal to the number of vertices. Print the color configuration in the color
array.
 Assign a color to a vertex from the range (1 to m).
 For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do
not have the same color) and recursively call the function with the next index and number of
vertices otherwise, return false
 If any recursive function returns true then return true
 If no recursive function returns true then return false
 To color the graph, color each node one by one.
 To color the first node there are 3 choices of colors Red, Green and Blue, so lets take
the red color for first node.
 After Red color for first node is fixed then we have made choice for second node in similar manner
as we did for first node, then for 3rd node and so on.
 There is one important point to remember. while choosing color for the node, it should not be same
as the color of the adjacent node.


As shown in the above diagram, all the solutions are shown by coloring the first node in Green.
 Let’s choose Blue color for the first node and explore the options for the remaining nodes.
5.5 Sum of subsets
In the naive method to solve a subset sum problem, the algorithm generates all
the possible permutations and then checks for a valid solution one by one.
Whenever a solution satisfies the constraints, mark it as a part of the solution.

In solving the subset sum problem, the backtracking approach is used for
selecting a valid subset. When an item is not valid, we will backtrack to get the
previous subset and add another element to get the solution.

In the worst-case scenario, backtracking approach may generate all

combinations, however, in general, it performs better than the naive approach.

Follow the below steps to solve subset sum problem using the backtracking
approach −

 first, take an empty subset.

 Include the next element, which is at index 0 to the empty set.
 If the subset is equal to the sum value, mark it as a part of the solution.
 If the subset is not a solution and it is less than the sum value, add next
element to the subset until a valid solution is found.
 Now, move to the next element in the set and check for another solution
until all combinations have been tried.
5.6 Hamiltonian cycles
Given a graph G = (V, E) we have to find the Hamiltonian Circuit using
Backtracking approach. We start our search from any arbitrary vertex say
'a.' This vertex 'a' becomes the root of our implicit tree. The first element
of our partial solution is the first intermediate vertex of the Hamiltonian
Cycle that is to be constructed. The next adjacent vertex is selected by
alphabetical order. If at any stage any arbitrary vertex makes a cycle with
any vertex other than vertex 'a' then we say that dead end is reached. In
this case, we backtrack one step, and again the search begins by
selecting another vertex and backtrack the element from the partial;
solution must be removed. The search using backtracking is successful if
a Hamiltonian Cycle is obtained.

Example: Consider a graph G = (V, E) shown in fig. we have to find a

Hamiltonian circuit using Backtracking method.
Solution: Firstly, we start our search with vertex 'a.' this vertex 'a'
becomes the root of our implicit tree.
 Next, we select vertex 'f'
adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already
visited. Thus, we get the dead end, and we backtrack one step and
remove the vertex 'f' from partial solution.
 From backtracking, the
vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already
been checked, and b, c, d have already visited. So, again we backtrack
one step. Now, the vertex adjacent to d are e, f from which e has already
been checked, and adjacent of 'f' are d and e. If 'e' vertex, revisited them
we get a dead state. So again we backtrack one step.

Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd'
and adjacent to 'd' is 'a.' Here, we get the Hamiltonian Cycle as all the
vertex other than the start vertex 'a' is visited only once. (a - b - c - e - f -d
- a).
Here we have generated one Hamiltonian circuit, but another Hamiltonian
circuit can also be obtained by considering another vertex.