UNIT 5: BACKTRACKING

Introduction to Backtracking
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.

What is Backtracking?

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.

Introduction to Backtracking

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.

Determining Backtracking Problems:

Generally every constraint satisfaction problem can be solved using backtracking but, Is it optimal to use
backtracking every time? Turns out NO, there are a vast number of problem that can be solved
using Greedy or Dynamic programming in logarithmic or polynomial time complexity which is far better
than exponential complexity of Backtracking. However many problems still exists that can only be solved
using Backtracking.

To understand whether a problem is Backtracking based or not, let us take a simple problem:
Problem: Imagine you have 3 closed boxes, among which 2 are empty and 1 has a gold coin. Your task is
to get the gold coin.

Why dynamic programming fails to solve this question: Does opening or closing one box has any effect
on the other box? Turns out NO, each and every box is independent of each other and opening/closing
state of one box can not determine the transition for other boxes. Hence DP fails.

Why greedy fails to solve this question: Greedy algorithm chooses a local maxima in order to get global
maxima, but in this problem each and every box has equal probability of having a gold coin i.e 1/3 hence
there is no criteria to make a greedy choice.

Why Backtracking works: As discussed already, backtracking algorithm is simply brute forcing each and
every choice, hence we can one by one choose every box to find the gold coin, If a box is found empty we
can close it back which acts as a Backtracking step.

Technically, for backtracking problems:

• The algorithm builds a solution by exploring all possible paths created by the choices in the
problem, this solution begins with an empty set S={}

• Each choice creates a new sub-tree ‘s’ which we add into are set.

• Now there exist two cases:

o S+s is valid set

o S+s is not valid set

• In case the set is valid then we further make choices and repeat the process until a solution is
found, otherwise we backtrack our decision of including ‘s’ and explore other paths until a solution
is found or all the possible paths are exhausted.

8 queen problem
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of
them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens
problem places n queens on an n×n chessboard. There are different solutions for the
problem. Backtracking | Set 3 (N Queen Problem) Branch and Bound | Set 5 (N Queen Problem) You can
find detailed solutions at [Link]
Explanation:

• This pseudocode uses a backtracking algorithm to find a solution to the 8 Queen problem, which
consists of placing 8 queens on a chessboard in such a way that no two queens threaten each
other.

• The algorithm starts by placing a queen on the first column, then it proceeds to the next column
and places a queen in the first safe row of that column.

• If the algorithm reaches the 8th column and all queens are placed in a safe position, it prints the
board and returns true.
If the algorithm is unable to place a queen in a safe position in a certain column, it backtracks to
the previous column and tries a different row.

• The “isSafe” function checks if it is safe to place a queen on a certain row and column by checking
if there are any queens in the same row, diagonal or anti-diagonal.

• It’s worth to notice that this is just a high-level pseudocode and it might need to be adapted
depending on the specific implementation and language you are using.

Subset Sum Problem

It is one of the most important problems in complexity theory. The problem is given an A set of integers
a1, a2,…., an upto n integers. The question arises that is there a non-empty subset such that the sum of
the subset is given as M integer?. For example, the set is given as [5, 2, 1, 3, 9], and the sum of the subset
is 9; the answer is YES as the sum of the subset [5, 3, 1] is equal to 9. This is an NP-complete problem
again. It is the special case of knapsack

Let's understand this problem through an example.

problem.

We have a set of 5 integers given below:

N = 4, -2, 2, 3, 1

We want to find out the subset whose sum is equal to 5. There are many solutions to this problem.

The naïve approach, i.e., brute-force search generates all the possible subsets of the original array, i.e.,
there are 2n possible states. Here the running time complexity would be exponential. Then, we consider
all these subsets in O(N) linear running time and checks whether the sum of the items is M or not.

The dynamic programming has pseudo-polynomial running time.

Statement: Given a set of positive integers, and a value sum, determine that the sum of the subset of a
given set is equal to the given sum.

Or

Given an array of integers and a sum, the task is to have all subsets of given array with sum equal to the
given sum.
 Example 1:

Input: set[] = {4, 16, 5, 23, 12}, sum = 9

Output = true

Subset {4, 5} has the sum equal to 9.

Example 2:

Input: set[] = {2, 3, 5, 6, 8, 10}, sum = 10

Output = true

There are three possible subsets that have the sum equal to 10.

Subset1: {5, 2, 3}

Subset2: {2, 8}

Subset3: {10}

There are two ways of solving the subset problem:

o Recursion

o Dynamic programming

Method 1: Recursion

Before knowing about the recursive approach, we should know about two things in a subset which are
given below:

o Include: Here include means that we are selecting the element from the array.

o Exclude: Here, exclude means that we are rejecting the element from the array.

To implement the recursive approach, we consider the following two cases:

o Now we consider the first element and now the required sum is equal to the difference between
the target sum and value of first element. The number of elements is equal to the difference
between the total elements and 1.

o Leave the 'first' element and now the required sum = target sum. The number of elements is equal
to the difference between the total elements and 1.

Let's understand that how can we solve the problem using recursion. Consider the array which is given
below:

arr = [3, 4, 5, 2]

sum = 9

result = []
In the above example, we have taken an array, and the empty array named result that stores all the values
whose resultant sum is equal to 9.

First element in an array is 3. There are two scenarios:

o First scenario is select. The sum is equal to the target sum - value of first element, i.e., 9 - 3 = 6
and the first element, i.e., 3 gets stored in the result array, i.e., result[].

o Second scenario is reject. The array arr contains the elements 4, 5, 2, i.e., arr = [4, 5, 2] and sum
would be same as 9 as we are rejecting the element 3. The result[] array would remain empty.

Now we perform the same select and reject operation on element 4 as it is the first element of
the array now.

o Select the element 4 from the array. Since we are selecting 4 from the array so array arr would
contain the elements 5, 2, i.e., arr = [5, 2]. The sum is equal to the 6-4 = 2 and the element 4 gets
stored in the result arr. The result[] = {3, 4}.

o Reject the element 4 from the array. Since we are rejecting the 4 from the array so array arr would
contain the elements 5, 2, i.e., arr = [5, 2]. The sum would remain same as 6 and the result array
would be same as previous, i.e., {3}.

Now we perform the select and reject operation on element 5.

o Select the element 5 from the array. Since we are selecting 5 from the array so array arr would
contain the elements 2, i.e., arr = [2]. The sum is equal to the 2 - 5 equals to -3 and the element 5
gets stored in the result arr. The result[] = {3, 4, 5}.

o Reject the element 5 from the array. Since we are rejecting 5 from the array so array arr would
contain the element 2, i.e., arr = [2]. The sum would remain same as previous, i.e., 6 and the result
 array would be same as previous, i.e., {3, 4}.

If we observe S-5, we can see that the sum is negative that returns false. It means that there is no further
subset available in the set.

Consider R-5. It also has two scenarios:

o Select the element 2 from the array. Once the element 2 gets selected, the array becomes empty,
i.e., arr[] = " ". The sum would be 2-2 equals to 0 and the element 2 gets stored in the result array.
The result[] = [3, 4, 2].

o Reject the element 2 from the array. Once the element 2 gets rejected, the array becomes empty,
i.e., arr[] = " ". The sum would be same as previous, i.e., 2 and the result array would also be same
as previous, i.e., [3, 4].

Consider R-4. It has two scenarios:

o Select the element 5 from the array. Since we are selecting 5 from the array so array arr would
contain the elements 2, i.e., arr = [2]. The sum would be 6-5 equals to 1 and the element 5 gets
stored in the result array. The result[] = [3, 5].

o Reject the element 5 from the array. Since we are rejecting 5 from the array so array arr would
contain the element 2, i.e., arr = [2]. The sum would remain same as previous, i.e., 6 and the result
array would be same as previous, i.e., {3}.
Consider S-5. It has two scenarios:

o Select the element 2 from the array. Since we are selecting 2 from the array so array arr would be
empty, i.e., arr = " ". The sum would be 1-2 equals to -1 and the element 2 gets stored in the result
array. The result[] = [3, 5, 2].

o Reject the element 2 from the array. Since we are rejecting 2 from the array so array arr would
become empty. The sum would remain same as previous, i.e., 1 and the result array would be
same as previous, i.e., {3, 5}.

Consider R-5. It has two scenarios:

o Select the element 2 from the array. Since we are selecting 2 from the array so array arr would be
empty, i.e., arr = " ". The sum would be 6-2 equals to 4 and the element 2 gets stored in the result
array. The result[] = [3, 2].

o Reject the element 2 from the array. Since we are rejecting 2 from the array so array arr would
become empty. The sum would remain same as previous, i.e., 6 and the result array would be
same as previous, i.e., {3}.

Similarly, we get the reject case, i.e., R-3 as shown as below:

Following are the base conditions:
if sum == 0
return true
if sum < 0
return false
if (arr[] && sum!= 0)
return false
When we apply the base conditions on the above tree, then we will find two subsets given below:

S1 = {3, 4, 2}

S2 = {4, 5}

Implementation

def subset_sum(arr, res, sum)

 if sum ==0

return true

if sum < 0

return false

if len(arr) == 0 and sum!= 0

return false

[Link](0);

if len(arr) > 0

[Link](arr[0])

select = subset_sum(arr, sum-arr[0], res)

reject = subset_sum(arr, res, sum)

return reject or sum

Method 2: Dynamic Programming

Let A be an array or set which contains 'n' non-negative integers. Find a subset 'x' of set 'A' such that the
sum of all the elements of x is equal to w where x is another input (sum).

For example:

A = {1, 2, 5, 9, 4}

Sum(w) = 18

Now we have to find out the subset from the given set whose sum is equal to 18. Here we will use the
dynamic programming approach to solve the subset sum problem.

Example:

A = [2, 3, 5, 7, 10]

Sum(w) = 14

First, we create a table. The column contains the values from 0 to 14 while row contains the elements of
the given set shown as below:

In the below table:

i: It represents the rows. Rows represents the elements.

j: It represents the columns. Columns represent the sum.

Consider the element 2. We will use 1 as a true value and 0 as a false value. The value 1 comes under 0
and 2 columns shown as below:

Here i=1, a[i] =2

Note: The rule for filling each column is given below:

Required sum = j - element
A[i][j] = A[i-1][required sum]

When j= 1

Required sum = 1 - 2 = -1; Since the sum is negative so put 0 under the column 1 as shown in the above
table.

When j= 2

Required sum = 2 - 2 = 0; Since the value of sum is zero so we put 1 under the column 2 as shown in the
above table.

We put 0 under the columns whose sum is greater than 2 as we cannot make sum more than 2 from the
element 2.

Consider the element 3.

Here i = 2, a[i] = 3
The columns whose sum is less than 3 will have the same values as the previous columns.

When j = 3, sum[j] = 3

Required sum = 3 -3 = 0; since the sum is zero so we put 1 under the column 3 as shown in the above
table.

When j = 4; sum[j] = 4

Required sum = 4 - 3 = 1; Since the sum is 1 so we move to the previous row, i.e., i=1 and j=1. The value
at a[1][1] is 0 so we put 0 at a[2][4].

When j = 5, sum[j] = 5

Required sum = 5 -3 = 2; The value of sum is 2 so the value at a[1][2] equals to 1. Therefore, the value at
a[2][5] would be 1.

When j = 6, sum[j] = 6

Required sum = 6 -3 = 3; The value of sum is 3 so the value at a[1][3] equals to 0. Therefore, the value at
a[2][6] would be 0.

When j = 7, sum[7] = 7

Required sum = 7 - 3 = 4; The value of sum is 4 so the value at a[1][4] equals to 0. Therefore, the value at
a[2][7] would be 0.

In this way, we get the value 0 from the columns 8 to 14.

Consider the element 5.

Here i=3, a[i] = 5

The columns whose sum is less than 5 will have the same values as the previous columns.

When j =5, sum[j] = 5

Required sum = 5-5 = 0; Since the value of sum is 0; therefore, the value at a[2][5] equals to 1.

When j = 6, sum[j] = 6

Required sum = 6-5 = 1; the value of sum is 1 so the value at a[2][1] equals to 0; therefore, the value at
a[3][6] equals to 0.

When j=7, sum[j] = 7

Required sum = 7-5 = 2; the value of sum is 2 so the value at a[2][2] equals to 1; therefore, the value at
a[3][7] equals to 1.

When j=8, sum[j] = 8

Required sum = 8-5 = 3; the value of sum is 3 so the value at a[2][3] equals to 1; therefore, the value at
a[3][8] equals to 1.

When j=9, sum[j] =9

Required sum= 9-5 = 4; the value of sum is 4 so the value at a[2][4] equals to 0; therefore the value at
a[3][9] equals to 0.

In this way, we get the values from the columns 10 to 14.

Consider the element 7.

Here i=4, a[i] =7

The columns whose sum is less than 7 will have the same values as the previous columns.

When j=9, sum[j] = 9

Required sum = 9 - 7 = 2; the value of sum is 2 so the value at a[3][2] equals to 1; therefore the value at
a[4][9] equals to 1.

When j=10, sum[j] = 10

Required sum = 10 - 7= 3; the value of sum is 3 so the value at a[3][3] equals to 1; therefore, the value at
a[4][10] equals to 1.

When j=11, sum[j] =11

Required sum = 11-7 = 4; the value of sum is 4 so the value at a[3][4] equals to 0; therefore, the value at
a[4][11] equals to 0.

When j=12, sum[j] = 12

Required sum = 12-7 = 5; the value of sum is 5 so the value at a[3][5] equals to 1; therefore, the value at
a[4][12] equals to 1.

When j=13, sum[j] =13

Required sum= 13 - 7 = 6; the value of sum is 6 so the value at a[3][6] equals to 0; therefore, the value at
a[4][13] equals to 0.
When j=14, sum[j] = 14

Required sum = 14 - 7 = 7; the value of sum is 7 so the value at a[3][7] equals to 1; therefore, the value at
a[4][14] equals to 1.

Consider the element 10

Here i=5, a[i] = 10

The columns whose sum is less than 10 will have the same values as the previous columns.

When j = 10, sum[j] = 10

Required sum = 10 - 10 = 0; the value of sum is 0 so the value at a[4][0] equals to 1; therefore, the value
at a[5][10] equals to 1.

When j = 11, sum[j] = 11

Required sum = 11 - 10 = 1; the value of sum is 1 so the value at a[4][1] equals to 0; therefore, the value
at a[5][11] equals to 0.

When j=12, sum[j] = 12

Required sum = 12-10 = 2; the value of sum is 2 so the value at a[4][2] equals to 1; therefore, the value at
a[5][12] equals to 1.

When j=13, sum[j] = 13

Required sum = 13 - 10 = 3; the value of sum is 3 so the value at a[4][3] equals to 1; therefore, the value
at a[5][13] equals to 1.

To determine whether the above given problem contains the subset or not, we need to check the last row
and the last column. If the value is 1 which means that there would exist atleast one subset.

We have basically followed three conditions where we write 1 in the cell of the table:

• A[i] = j

• A[i-1][j] = 1

• A[i-1][j-A[i]] = 1

Graph Coloring
Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent
vertices get same color. The objective is to minimize the number of colors while coloring a graph. The
smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph
coloring problem is a NP Complete problem.

Method to Color a Graph

The steps required to color a graph G with n number of vertices are as follows −

Step 1 − Arrange the vertices of the graph in some order.

Step 2 − Choose the first vertex and color it with the first color.

Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored
on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to
it. Repeat this step until all the vertices are colored.

Example

In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are again adjacent,
vertex b and vertex d are colored with different color, green and blue respectively. Then vertex c is colored
as red as no adjacent vertex of c is colored red. Hence, we could color the graph by 3 colors. Hence, the
chromatic number of the graph is 3.

Applications of Graph Coloring

Some applications of graph coloring include −

• Register Allocation

• Map Coloring

• Bipartite Graph Checking

• Mobile Radio Frequency Assignment

• Making time table, etc.

Knapsack Problem Using Greedy Method: The selection of some things, each with profit and weight
values, to be packed into one or more knapsacks with capacity is the fundamental idea behind all families
of knapsack problems. The knapsack problem had two versions that are as follows:
Fractional Knapsack Problem

0 /1 Knapsack Problem

The fractional Knapsack problem using the Greedy Method is an efficient method to solve it, where you
need to sort the items according to their ratio of value/weight. In a fractional knapsack, we can break
items to maximize the knapsack’s total value. This problem in which we can break an item is also called
the Fractional knapsack problem. Here, we will see Knapsack Problem using Greedy method in detail,
along with its algorithm and examples.

What is Knapsack Problem Using Greedy Method?

In this method, the Knapsack’s filling is done so that the maximum capacity of the knapsack is utilized so
that maximum profit can be earned from it. The knapsack problem using the Greedy Method is referred
to as:
Given a list of n objects, say {I1, I2,……, In) and a knapsack (or bag).
The capacity of the knapsack is M.
Each object Ij has a weight wj and a profit of pj
If a fraction xj (where x ∈ {0…., 1)) of an object Ij is placed into a knapsack, then a profit of pjxj is earned.
The problem (or Objective) is to fill the knapsack (up to its maximum capacity M), maximizing the total
profit earned.

Mathematically:
Note that the value of xj will be any value between 0 and 1 (inclusive). If any object Ij is completely
placed into a knapsack, its value is 1 (xj = 1). If we do not pick (or select) that object to fill into a
knapsack, its value is 0 ( xj = 0). Otherwise, if we take a fraction of any object, then its value will be any
value between 0 and 1.

Knapsack Problem Algorithm Using Greedy Method

Knapsack Problem Using Greedy Method Pseudocode

A pseudo-code for solving knapsack problems using the greedy method is;
greedy fractional-knapsack (P[1…n], W[1…n], X[1..n]. M)
/*P[1…n] and W[1…n] contain the profit and weight of the n-objects ordered such that X[1…n] is a
solution set and M is the capacity of knapsack*/
{
For j ← 1 to n do
X[j]← 0
profit ← 0 // Total profit of item filled in the knapsack
weight ← 0 // Total weight of items packed in knapsacks
j←1
While (Weight < M) // M is the knapsack capacity

if (weight + W[j] =< M)

X[j] = 1
weight = weight + W[j]
else{
X[j] = (M – weight)/w[j]
weight = M

}
Profit = profit + p[j] * X[j]
j++;
} // end of while
} // end of Algorithm

Knapsack Problem Using Greedy Method Example

We have thoroughly discussed the fractional knapsack problem and the algorithm for the knapsack
problem using Greedy method. Now to understand it better, let us see an example.

Consider the knapsack instances, the capacity of the knapsack is 15, and 7 object has profit and weight
as follows:

Object X1 X2 X3 X4 X5 X6 X7

Weight 2 3 5 7 1 4 1

Profit 10 5 15 7 6 18 3

Which object is partially placed in the knapsack using the fractional knapsack problem?

1. X4
2. X2
3. X1
4. X3

Answer: Option B
Solution: Let us first find each object’s profit by weight ratio.

object X1 X2 X3 X4 X5 X6 X7

Profit/weight 5 1.66 3 1 6 4.5 3

Now we will arrange the profit by weight ratio in descending order and pick the objects accordingly.

X5 X1 X6 X7 X3 X2

6 5 4.5 3 3 1.6

The total capacity of the knapsack = 15

After selecting X5 capacity = 15-1=14

After selecting X1 capacity = 14-2=12

After selecting X6 capacity = 12-4=8

After selecting X7 capacity = 8-1=7

After selecting X3 capacity = 7-5=2

After selecting X2 capacity = 2-(2/3)*3=0

Thus we are taking only 2/3rd weight of the object X2

We take fractional parts from X2.

Therefore, option B is correct.

Branch and bound

What is Branch and bound?

Branch and bound is one of the techniques used for problem solving. It is similar to the backtracking since
it also uses the state space tree. It is used for solving the optimization problems and minimization
problems. If we have given a maximization problem then we can convert it using the Branch and bound
technique by simply converting the problem into a maximization problem.

Let's understand through an example.

Jobs = {j1, j2, j3, j4}

P = {10, 5, 8, 3}

d = {1, 2, 1, 2}

The above are jobs, problems and problems given. We can write the solutions in two ways which are given
below:

Suppose we want to perform the jobs j1 and j2 then the solution can be represented in two ways:

The first way of representing the solutions is the subsets of jobs.

S1 = {j1, j4}

The second way of representing the solution is that first job is done, second and third jobs are not done,
and fourth job is done.

S2 = {1, 0, 0, 1}

The solution s1 is the variable-size solution while the solution s2 is the fixed-size solution.

First, we will see the subset method where we will see the variable size.

First method:

In this case, we first consider the first job, then second job, then third job and finally we consider the last
job.

As we can observe in the above figure that the breadth first search is performed but not the depth first
search. Here we move breadth wise for exploring the solutions. In backtracking, we go depth-wise
whereas in branch and bound, we go breadth wise.

Now one level is completed. Once I take first job, then we can consider either j2, j3 or j4. If we follow the
route then it says that we are doing jobs j1 and j4 so we will not consider jobs j2 and j3.
Now we will consider the node 3. In this case, we are doing job j2 so we can consider either job j3 or j4.
Here, we have discarded the job j1.

Now we will expand the node 4. Since here we are doing job j3 so we will consider only job j4.

Now we will expand node 6, and here we will consider the jobs j3 and j4.

Now we will expand node 7 and here we will consider job j4.
Now we will expand node 9, and here we will consider job j4.

The last node, i.e., node 12 which is left to be expanded. Here, we consider job j4.

The above is the state space tree for the solution s1 = {j1, j4}

Second method:

We will see another way to solve the problem to achieve the solution s1.

First, we consider the node 1 shown as below:

Now, we will expand the node 1. After expansion, the state space tree would be appeared as:

On each expansion, the node will be pushed into the stack shown as below:
Now the expansion would be based on the node that appears on the top of the stack. Since the node 5
appears on the top of the stack, so we will expand the node 5. We will pop out the node 5 from the stack.
Since the node 5 is in the last job, i.e., j4 so there is no further scope of expansion.

The next node that appears on the top of the stack is node 4. Pop out the node 4 and expand. On
expansion, job j4 will be considered and node 6 will be added into the stack shown as below:

The next node is 6 which is to be expanded. Pop out the node 6 and expand. Since the node 6 is in the last
job, i.e., j4 so there is no further scope of expansion.

The next node to be expanded is node 3. Since the node 3 works on the job j2 so node 3 will be expanded
to two nodes, i.e., 7 and 8 working on jobs 3 and 4 respectively. The nodes 7 and 8 will be pushed into the
stack shown as below:
The next node that appears on the top of the stack is node 8. Pop out the node 8 and expand. Since the
node 8 works on the job j4 so there is no further scope for the expansion.

The next node that appears on the top of the stack is node 7. Pop out the node 7 and expand.
Since the node 7 works on the job j3 so node 7 will be further expanded to node 9 that works
on the job j4 as shown as below and the node 9 will be pushed into the stack.

The next node that appears on the top of the stack is node 9. Since the node 9 works on the
job 4 so there is no further scope for the expansion.

The next node that appears on the top of the stack is node 2. Since the node 2 works on the
job j1 so it means that the node 2 can be further expanded. It can be expanded upto three
nodes named as 10, 11, 12 working on jobs j2, j3, and j4 respectively. There newly nodes will
be pushed into the stack shown as below:
In the above method, we explored all the nodes using the stack that follows the LIFO principle.

Third method

There is one more method that can be used to find the solution and that method is Least cost
branch and bound. In this technique, nodes are explored based on the cost of the node. The
cost of the node can be defined using the problem and with the help of the given problem, we
can define the cost function. Once the cost function is defined, we can define the cost of the
node.

Let's first consider the node 1 having cost infinity shown as below:

Now we will expand the node 1. The node 1 will be expanded into four nodes named as 2, 3,
4 and 5 shown as below:

Let's assume that cost of the nodes 2, 3, 4, and 5 are 25, 12, 19 and 30 respectively.

Since it is the least cost branch n bound, so we will explore the node which is having the least
cost. In the above figure, we can observe that the node with a minimum cost is node 3. So,
we will explore the node 3 having cost 12.
Since the node 3 works on the job j2 so it will be expanded into two nodes named as 6 and 7
shown as below:

The node 6 works on job j3 while the node 7 works on job j4. The cost of the node 6 is 8 and
the cost of the node 7 is 7. Now we have to select the node which is having the minimum
cost. The node 7 has the minimum cost so we will explore the node 7. Since the node 7
already works on the job j4 so there is no further scope for the expansion.

What is Hamiltonian Cycle?

Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex of G exactly once and returns
to the starting vertex.

• If graph contains a Hamiltonian cycle, it is called Hamiltonian graph otherwise it is non-

Hamiltonian.

• Finding a Hamiltonian Cycle in a graph is a well-known NP-complete problem, which means that
there’s no known efficient algorithm to solve it for all types of graphs. However, it can be solved
for small or specific types of graphs.
The Hamiltonian Cycle problem has practical applications in various fields, such as logistics,
network design, and computer science.

What is Hamiltonian Path?

Hamiltonian Path in a graph G is a path that visits every vertex of G exactly once and Hamiltonian Path
doesn’t have to return to the starting vertex. It’s an open path.

• Similar to the Hamiltonian Cycle problem, finding a Hamiltonian Path in a general graph is
also NP-complete and can be challenging. However, it is often a more easier problem than finding
a Hamiltonian Cycle.

• Hamiltonian Paths have applications in various fields, such as finding optimal routes in
transportation networks, circuit design, and graph theory research.

Problems Statement: Given an undirected graph, the task is to determine whether the graph contains a
Hamiltonian cycle or not. If it contains, then prints the path.

Example:
Input: graph[][] = {{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 1},{0, 1, 1, 1, 0}}

Input graph[][]

Output: {0, 1, 2, 4, 3, 0}.

Input: graph[][] = {{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 0},{0, 1, 1, 0, 0}}

Input graph[][]

Output: Solution does not exist

Naive Algorithm: This problem can be solved using below idea:

Generate all possible configurations of vertices and print a configuration that satisfies the given
constraints. There will be n! (n factorial) configurations. So the overall Time Complexity of this approach
will be O(N!).

Hamiltonian Cycle using Backtracking Algorithm:

Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before
adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If
we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return
false.

Illustrations:

Let’s find out the Hamiltonian cycle for the following graph:
 • Start with the node 0 .

• Apply DFS for finding the Hamiltonian path.

• When base case reach (i.e. total no of node traversed == V (total vertex)):

o Check whether current node is a neighbour of starting node.

o As node 2 and node 0 are not neighbours of each other so return from it.

Starting from start node 0 calling DFS

• As cycle is not found in path {0, 3, 1, 4, 2}. So, return from node 2, node 4.

• Now, explore another option for node 1 (i.e node 2)

• When it hits the base condition again check for Hamiltonian cycle

• As node 4 is not the neighbour of node 0, again cycle is not found then return.
 • Return from node 4, node 2, node 1.

• Now, explore other options for node 3.

Hamiltonian Cycle

• In the Hamiltonian path {0,3,4,2,1,0} we get cycle as node 1 is the neighbour of node 0.

• So print this cyclic path .

• This is our Hamiltonian cycle.