UNIT-2 Solutions

11. Explain the general method of backtracking? Provide a detailed explanation with a clear
algorithm and an example to illustrate how backtracking works.
Solution:

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.
The backtracking algorithm works by recursively exploring all possible solutions to a problem.
The algorithm starts by selecting an initial solution, and then recursively explores all possible
solutions by adding one element at a time. When a dead end is reached, the algorithm
backtracks to a previous state and explores another branch.
The backtracking algorithm can be broken down into three main steps:
1. Select a starting point: The algorithm starts by selecting an initial solution or a starting
point. This starting point is often an empty solution or a partial solution.
2. Explore possible solutions: The algorithm recursively explores all possible solutions by
adding one element at a time. This is done by generating all possible solutions and evaluating
each solution to determine if it is a valid solution.
3. Backtrack and explore another branch: When a dead end is reached, the algorithm
backtracks to a previous state and explores another branch. This process continues until a
solution is found or all possible solutions have been exhausted.

Key Components of Backtracking

1. State Space Tree:

o A tree representation of all possible states/solutions explored during the
backtracking process.
o Nodes represent intermediate or partial solutions.
o Branching occurs as we add choices incrementally to the solution.
2. Feasibility Function:
o This function checks if the current solution satisfies the constraints of the
problem.
3. Backtrack Step:
o If a partial solution violates the constraints, backtrack by undoing the last
decision and exploring other options.
Steps of the Backtracking Algorithm:

• Start with an empty solution.

• At each step:
– Add a component (candidate) to the solution.
– Check if the current solution satisfies the problem constraints.
• If valid, proceed to the next step.
• If invalid, remove (backtrack) the current component and explore other
possibilities.
• If a complete solution is found, record it or output it.
• Repeat until all possibilities have been explored.
Advantages

• Backtracking is a simple and intuitive algorithm that is easy to implement.

• It is particularly useful for solving problems with a recursive structure.
• It can be used to solve problems that have multiple solutions.
Disadvantages

• Backtracking can be computationally expensive, especially for large problem sizes.

• It can be difficult to implement, especially for complex problems.
• It may not always find the optimal solution, especially for problems with multiple local
optima.
Backtracking explores all possible solutions systematically and discards invalid paths early. It
works efficiently for problems like N-Queens, Subset Sum, Graph Coloring, and Hamiltonian
Cycles, where an exhaustive search is required.
Example: Solving the 4-Queens Problem
Place 4 queens on a 4×4 chessboard such that no two queens attack each other. Queens can
attack in rows, columns, and diagonals.
Steps to Solve Using Backtracking:

• Place queens row by row, one queen per row.

• For each queen placement, check if the position is safe:
– No queen in the same column.
– No queen on the same diagonal.
• If a safe position is found, place the queen and proceed to the next row.
• If no safe position is found in a row, backtrack to the previous row and move the queen
to the next column.
12. Describe the general method of Backtracking and explain how it differs from other
problem-solving techniques like Divide and Conquer?
Solution:
Backtracking is a systematic and recursive approach to solving problems by building a solution
step by step. It explores all possible choices at each step, eliminates those that fail to satisfy
the constraints, and backtracks to the previous step to explore other options. It is particularly
effective for combinatorial optimization problems or problems involving exhaustive search in
a state-space tree.
Key Features of Backtracking:
• Incremental Solution Building: Solutions are built step by step by adding candidates.
At each step, the feasibility of the solution is checked.
• Constraint Checking: If the current partial solution violates the constraints, it is
abandoned, and the algorithm backtracks to explore alternative choices.
• State-Space Tree: Backtracking explores a tree structure (known as the state-space
tree), where each node represents a partial solution.
• Recursive Nature: Backtracking problems are often implemented recursively, as
recursion helps explore all paths in the state-space tree.
• Pruning Invalid Paths: By checking constraints, invalid paths are pruned early, saving
computation time.
Steps of the Backtracking Algorithm:

• Start with an empty solution.

• At each step:
– Add a component (candidate) to the solution.
– Check if the current solution satisfies the problem constraints.
• If valid, proceed to the next step.
• If invalid, remove (backtrack) the current component and explore other
possibilities.
• If a complete solution is found, record it or output it.
• Repeat until all possibilities have been explored.
Pseudocode for Backtracking
Backtrack(Solution s, Options o)
1. if s is a complete solution:
Output s
return
2. for each option in Options(o):
if isValid(s, option): // Check feasibility of adding option
Add option to s
Backtrack(s, o) // Recursive call
Remove option from s // Undo the addition (backtrack)
Backtracking Differs from Divide and Conquer

Aspect Backtracking Divide and Conquer

Backtracking is an algorithmic Divide and Conquer is a method where a
technique used to solve problems problem is divided into smaller
Definition incrementally by exploring all possible independent sub problems, solved
solutions and backtracking when a recursively, and the results are
constraint is violated. combined to solve the main problem.
Exploratory: It systematically explores Partitioning: Divides the problem into
Nature
all possible solutions (state space). smaller independent sub problems.
Used for problems that require
Used for problems that can be split into
Problem Type searching, constraint satisfaction, or
independent sub problems.
combinatorial optimization.
Solution Explores the entire solution space Breaks the problem into sub problems
Space systematically. and merges results.
Incrementally builds a solution and Divides the problem, solves sub
Recursive
backtracks when constraints are problems independently, and merges
Steps
violated. the results.
Constraint Dynamically checks constraints to No constraint checking; only focuses on
Checking prune invalid solutions. solving and merging results.
Generally more efficient due to its
Can involve exponential time
Efficiency divide-and-merge strategy (e.g., O(n log
complexity in the worst case.
n) for sorting).
Overlapping Does not use overlapping sub Can utilize overlapping sub problems
Solutions problems. (optimized using dynamic programming).
- N-Queens Problem - Merge Sort
Example - Subset Sum Problem - Quick Sort
Problems - Graph Coloring - Binary Search
- Hamiltonian Cycle - Matrix Multiplication
Incremental solution construction and Divide the problem into parts, solve
Key Approach
pruning (backtracking). recursively, and combine the results.
State-Space Explores a state-space tree where Does not require a state-space tree;
Tree nodes represent partial solutions. focuses on dividing and merging.

13. Elaborate the N-Queens problem and provide a backtracking solution to solve it.
Solution:
The N-Queens problem is a classic combinatorial problem that involves placing N queens on
an N×N chessboard such that no two queens attack each other. A queen in chess can move
horizontally, vertically, or diagonally, so the challenge is to ensure that no two queens share
the same row, column, or diagonal.
 N Queen Problem using Backtracking:
The idea is to place queens one by one in different columns, starting from the leftmost
column. When we place a queen in a column, we check for clashes with already placed
queens. In the current column, if we find a row for which there is no clash, we mark this row
and column as part of the solution. If we do not find such a row due to clashes, then we
backtrack and return false.
Follow the steps mentioned below to implement the idea:
• Start in the leftmost column
• If all queens are placed return true
• Try all rows in the current column. Do the following for every row.
– If the queen can be placed safely in this row
o Then mark this [row, column] as part of the solution and
recursively check if placing queen here leads to a solution.
o If placing the queen in [row, column] leads to a solution then
return true.
o If placing queen doesn’t lead to a solution then unmark this
[row, column] then backtrack and try other rows.
– If all rows have been tried and valid solution is not found return false
to trigger backtracking.
Algorithm for N-Queens
function solveNQueens(board, row, N):
if row == N: // All queens are placed
Print the board as a solution
return
for col = 0 to N-1:
if isSafe(board, row, col, N): // Check if placing queen is safe
board[row][col] = 1 // Place queen
solveNQueens(board, row + 1, N) // Recur to place queen in next row
board[row][col] = 0 // Backtrack and remove queen from (row, col)

function isSafe(board, row, col, N): // Check column for conflicts

for i from 0 to row-1:
if board[i][col] == 1:
return false
for i, j from (row-1, col-1) to (0, 0): // Check upper-left diagonal
if board[i][j] == 1:
 return false
for i, j from (row-1, col+1) to (0, N-1): // Check upper-right diagonal
if board[i][j] == 1:
return false
return true

isSafe Function:
• Checks if placing a queen at a specific position (row, col) is valid by ensuring:
• No queens are placed in the same column.
• No queens are placed in the upper-left diagonal.
• No queens are placed in the upper-right diagonal.
solveNQueensUtil Function:
• Recursively attempts to place a queen row by row. If no valid position is found in the
current row, it backtracks to the previous row.
Solution Printing:
• When all queens are placed successfully (base case row == N), the solution is printed.

Time Complexity

• Worst-case Time Complexity: O(N!), since there are N possibilities for each of the N
rows.
• Space Complexity: O(N2) for the board and O(N) for the recursion stack.

The N-Queens problem is efficiently solved using backtracking. By placing queen’s row by row
and pruning invalid solutions, the algorithm explores only feasible solutions and backtracks
when necessary.

14. Solve the 4-Queen problem using backtracking. Show the steps and explain how the
algorithm avoids invalid placements
Solution:
In the 4 - Queens problem we have to place 4 queens such as Q1, Q2, Q3, and Q4 on the chessboard,
in such a way that no two queens attack each other. To solve this problem generally Backtracking
algorithm or approach is used.
In backtracking, start with one possible move out of many available moves, then try to solve
the problem. If it can solve the problem with the selected move then it will print the solution,
else it will backtrack and select some other move and try to solve it.If none of the moves
works out the claim that there is no solution for the problem.
Working of an Algorithm to solve the 4-Queens Problem:
• To solve the problem place a queen in a position and try to find out all the possibilities
for any queen being under attack or not.
• Based on the findings place only one queen in each row/column.
• If we found that the queen is under attack at its chosen position, then try for the next
position.
• If a queen is under attack at all the positions in a row, we backtrack and change the
position of the queen placed prior to the current position.
• Repeat this process of placing a queen and backtracking until all the N queens are
placed successfully.
Step 1 -
As this is the 4-Queens problem, therefore, create a 4×4 chessboard.

Step 2 -

• Place the Queen Q1 at the left-most position which means row 1 and column 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q1. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q1 at [1, 1] position:

Step 3 -

• The possible safe cells for Queen Q2 at row 2 are of column3 and 4 because these cells
do not come under the attack from a queen Q1.
• So, here we place Q2 at the first possible safe cell which is row 2 and column 3.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 3] position:
Step 4 -

• We see that no safe place is remaining for the Queen Q3 if we place Q2 at position [2,
3]
• Therefore make position [2, 3] false and backtrack.

Step 5 -

• So, we place Q2 at the second possible safe cell which is row 2 and column 4.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 4] position:

Step 6 -

• The only possible safe cell for Queen Q3 is remaining in row 3 and column 2.
• Therefore, we place Q3 at the only possible safe cell which is row 3 and column 2.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q3. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q3 at [3, 2] position:

Step 7 -

• We see that no safe place is remaining for the Queen Q4 if we place Q3 at position [3,
2]
• Therefore make position [3, 2] false and backtrack.

Step 8 -

• This time we backtrack to the first queen Q1.

• Place the Queen Q1 at column 2 of row 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q1. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q1 at [1, 2] position:
Step 9 -

• The only possible safe cell for Queen Q2 is remaining in row 2 and column 4.
• Therefore, we place Q2 at the only possible safe cell which is row 2 and column 4.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 4] position:

Step 10 -

• The only possible safe cell for Queen Q3 is remaining in row 3 and column 1.
• Therefore, we place Q3 at the only possible safe cell which is row 3 and column 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen
Q3. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q3 at [3, 1] position:

Step 11 -

• The only possible safe cell for Queen Q4 is remaining in row 4 and column 3.
• Therefore, we place Q4 at the only possible safe cell which is row 4 and column 3.
• The chessboard looks as follows after placing Q3 at [4, 3] position:
Step 12 -

• Now, here we got the solution for the 4-queens problem because all 4 queens are
placed exactly in each row/column individually.

Backtracking Avoids Invalid Placements

Row-by-Row Placement:
• Queens are placed row by row, ensuring no two queens are in the same row.
Safety Check: Before placing a queen, the algorithm checks:
• Columns: No other queen is in the same column.
• Upper-left Diagonal: No queen lies diagonally left above.
• Upper-right Diagonal: No queen lies diagonally right above.
Backtracking: If no safe column is found in a row:
• The algorithm removes the queen from the previous row.
• Moves the queen to the next column in the previous row.
• Reattempts to place queens in subsequent rows.
Systematic Search:
• By iterating through all columns in a row, the algorithm guarantees all possible
configurations are explored.
15. Explain how backtracking is applied to solve the subset sum problem. Write an algorithm
to find all subsets that sum to a given target.
Solution:
The Subset Sum Problem involves finding all subsets of a given set of integers whose
elements sum up to a specific target value. Given a set[] of non-negative integers and a value
sum, the task is to print the subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {1,2,1}, sum = 3
Output: [1,2],[2,1]
Explanation: There are subsets [1,2],[2,1] with sum 3.
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: []
Explanation: There is no subset that add up to 30.

The solution uses backtracking, which systematically explores all possible subsets and
backtracks whenever the current subset's sum exceeds the target.

Backtracking Approach to solve Subset Sum Problem:

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.

Algorithm

1. Start with an empty subset.

2. For each element in the set, recursively:
 o Include the element in the subset.
o Exclude the element from the subset.
3. Track the current sum of elements in the subset.
4. If the current sum equals the target, store the subset as a solution.
5. If the current sum exceeds the target, backtrack and exclude the element.

void findSubsets(int[] arr, int index, List<Integer> currentSubset, int currentSum, int target)
{
// Base Case: If current sum equals target, print the subset
if (currentSum == target)
{
System.out.println(currentSubset);
return;
}
// If current sum exceeds target or all elements are processed
if (currentSum > target || index == arr.length)
{
return;
}

// Include the current element

currentSubset.add(arr[index]);
findSubsets(arr, index + 1, currentSubset, currentSum + arr[index], target);

// Exclude the current element (Backtrack)

currentSubset.remove(currentSubset.size() - 1);
findSubsets(arr, index + 1, currentSubset, currentSum, target);
}

Backtracking Avoids Invalid Placements

• Pruning: If the current sum exceeds the target, the algorithm stops exploring that path
and backtracks.
• Exploration: By systematically including and excluding each element, backtracking
explores all possible subsets.
• Efficient Search: Backtracking ensures that only subsets with potential to reach the
target are explored, avoiding unnecessary calculations.

The backtracking algorithm efficiently solves the Subset Sum Problem by exploring all subsets
of the input set. It avoids invalid paths through pruning and ensures all valid subsets are
found.
16. Given the set S={10,7,5,18,12,20,15} and a target sum = 35. Solve the sum of subset
problem step by step using backtracking. Show the recursive tree structure explored.

Solution:

We solve the Sum of Subset Problem for the set S = {10,7,5,18,12,20,15} with a target sum of
35 using backtracking. Below is the detailed step-by-step solution along with the recursive
tree structure.
Steps to Solve
1. Start with an empty subset.
2. Recursively include or exclude each element of S in the subset.
3. Track the current subset sum:
o If the sum equals the target, record the subset as a solution.
o If the sum exceeds the target, backtrack (terminate that branch).
o If all elements are processed, backtrack.
Each level in the tree corresponds to a decision for one element in S:
• Include the element in the subset.
• Exclude the element from the subset.

Start: []
Current Sum = 0

Step 1: Include 10 → [10]

Step 2: Include 7 → [10, 7]
Step 3: Include 5 → [10, 7, 5]
Step 4: Include 18 → [10, 7, 5, 18] (Sum = 40) → Backtrack
Step 4: Exclude 18 → [10, 7, 5]
Step 5: Include 12 → [10, 7, 5, 12] (Sum = 34) → Backtrack
Step 5: Exclude 12 → [10, 7, 5]
Step 6: Include 20 → [10, 7, 5, 20] (Sum = 42) → Backtrack
Step 6: Exclude 20 → [10, 7, 5]
Step 7: Include 15 → [10, 7, 5, 15] (Sum = 37) → Backtrack
Step 7: Exclude 15 → [10, 7, 5] → Backtrack
Step 3: Exclude 5 → [10, 7]
Step 4: Include 18 → [10, 7, 18] (Sum = 35) → Solution Found
Step 4: Exclude 18 → [10, 7]
Step 5: Include 12 → [10, 7, 12] (Sum = 29)
Step 6: Include 20 → [10, 7, 12, 20] (Sum = 49) → Backtrack
Step 6: Exclude 20 → [10, 7, 12]
Step 7: Include 15 → [10, 7, 12, 15] (Sum = 44) → Backtrack
Step 7: Exclude 15 → [10, 7, 12] → Backtrack
Step 5: Exclude 12 → [10, 7]
 Step 6: Include 20 → [10, 7, 20] (Sum = 37) → Backtrack
Step 6: Exclude 20 → [10, 7]
Step 7: Include 15 → [10, 7, 15] (Sum = 32)
Step 8: Backtrack
Step 2: Exclude 7 → [10]
(Repeat similar steps with remaining elements)

Final subsets are as follows:

1. Subset = [10, 7, 18]
o Sum = 10+7+18=35 → Valid Solution
2. Subset = [10, 5, 20]
o Sum = 10+5+20=35→ Valid Solution
3. Subset = [5, 18, 12]
o Sum = 5+18+12=35→ Valid Solution
4. Subset = [20, 15]
o Sum = 20+15=35→ Valid Solution

The algorithm explores all combinations of elements, ensuring no valid subset is missed.
When the sum exceeds the target or no more elements are left, the algorithm "backtracks"
by excluding the last included element. Pruning invalid branches (those that exceed the
target) reduces unnecessary calculations. This recursive exploration ensures all valid subsets
summing to 35 are found.

17. Explain the Graph Coloring problem and how backtracking can be used to solve it.
Provide an example
Solution:
Graph coloring refers to the problem of coloring vertices of a graph in such a way that no
two adjacent vertices have the same color. This is also called the vertex coloring problem. If
coloring is done using at most m colors, it is called m-coloring.
The Graph Coloring Problem involves assigning colors to the vertices of a graph such that:
• No two adjacent vertices (connected by an edge) have the same color.
• The goal is to use the minimum number of colors possible or satisfy a given number
of colors 𝑘
This is an NP-complete problem and is often solved using backtracking for smaller graphs
where an exhaustive search is feasible. Graph coloring problem is both, a decision problem
as well as an optimization problem.
A decision problem is stated as, “With given M colors and graph G, whether a such color
scheme is possible or not?”.
The optimization problem is stated as, “Given M colors and graph G, find the minimum
number of colors required for graph coloring.”
 Algorithm of Graph Coloring using Backtracking:
Assign colors one by one to different vertices, starting from vertex 0. Before assigning a
color, 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 else return false
• If any recursive function returns true then break the loop and return true
• If no recursive function returns true then return false

We are given a graph G:

• V={v1,v2,v3,v4}
• Edges E={(v1,v2),(v1,v3),(v2,v4),(v3,v4)}

This graph can be represented as an adjacency matrix:

graph[][] = {
{0, 1, 1, 0}, // v1
{1, 0, 0, 1}, // v2
{1, 0, 0, 1}, // v3
{0, 1, 1, 0} // v4
};

Find a valid 2-coloring of the graph.

Step-by-Step Solution

• k=2 Colors are {1,2}

Backtracking Process

1. Assign color 1 to v1:

o colors[]=[1,0,0,0]
2. Move to v2:
o Adjacent to v1so cannot use color 1.
o Assign color 2:
 ▪ colors[]=[1,2,0,0]
3. Move to v3:
o Adjacent to v1, so cannot use color 1.
o Assign color 2:
▪ colors[]=[1,2,2,0]
4. Move to v4:
o Adjacent to v2 and v3, so cannot use color 2.
o Assign color 1:
▪ colors[]=[1,2,2,1]

The valid coloring for k=2 is:

• v1: Color 1
• v2: Color 2
• v3: Color 2
• v4: Color 1

18. Solve the graph coloring problem for the given graph using 3 colors: A graph with 4
vertices connected as follows:

• V1 ↔ V2
• V2 ↔ V3
• V3 ↔ V4
• V4 ↔ V1
• V1 ↔ V3
Illustrate the steps of backtracking to color the graph.

Solution:

The graph described can be represented as follows:

1. Vertices: V={V1,V2,V3,V4}
2. Edges:
o V1↔V2
o V2↔V3
o V3↔V4
o V4↔V1
o V1↔V3
This forms a cycle graph with a chord. The adjacency matrix of the graph is:
Adjacency Matrix= 0 1 1 1
1010
1101
1010
We need to color the graph using 3 colors {1, 2, 3} such that no two adjacent vertices share
the same color.

Graph Coloring Algorithm (Backtracking):

 1. Assign colors to vertices V1, V2, V3, V4.
2. Use a recursive backtracking approach to ensure adjacent vertices do not have the
same color.
3. If assigning a color to a vertex leads to a conflict, backtrack and try another color.

Step 1: Start with Vertex V1

• V1 has no adjacent vertices with assigned colors.

• Assign Color 1 to V1.
• Current color assignment: V1=1

Step 2: Move to Vertex V2

• V2 is adjacent to V1, which is colored 1.

• Assign Color 2 to V2 (since V2≠V1).
• Current color assignment: V1=1, V2=2.

Step 3: Move to Vertex V3

• V3 is adjacent to V2 (Color 2) and V1 (Color 1).

• Assign Color 3 to V3 (since V3≠V1, V3≠V2).
• Current color assignment: V1=1, V2=2, V3=3.

Step 4: Move to Vertex V4

• V4 is adjacent to V3 (Color 3) and V1 (Color 1).

• Assign Color 2 to V4 (since V4≠V1, V4≠V3).
• Current color assignment: V1=1, V2=2, V3=3, V4=2.

The graph is successfully colored using 3 colors without conflicts: V1=1, V2=2, V3=3, V4=2

19. Define the problem and explain how backtracking is used to determine if a Hamiltonian
cycle exists. Write the algorithm for solving the Hamiltonian cycle problem.

Solution:
A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once and returns to
the starting vertex. The Hamiltonian cycle problem is to determine whether a given graph
contains such a cycle. This is an NP-complete problem, meaning that there is no known
polynomial-time algorithm to solve it for all cases.
Input:
• A graph G=(V,E) with V as vertices and E as edges.
Output:
• A Hamiltonian cycle if it exists, or a statement that no such cycle exists.

Backtracking is used to explore all possible paths in the graph to find a Hamiltonian cycle. The
approach involves:
 1. Starting from a vertex: Begin at any vertex (usually vertex 0).
2. Exploring paths: Add vertices to the path one by one, ensuring that:
o Each vertex is visited only once.
o The current vertex is connected to the next vertex in the path.
3. Backtracking: If a partial path cannot lead to a valid Hamiltonian cycle (due to
violations like revisiting vertices or disconnections), backtrack to try other possibilities.
4. Termination:
o If all vertices are included in the path and the last vertex is connected to the
first vertex, a Hamiltonian cycle exists.
o If no such path is found after exploring all possibilities, no Hamiltonian cycle
exists.

Algorithm for Solving the Hamiltonian Cycle Problem:

1. Input: Graph G(V,E) as an adjacency matrix.

2. Output: Hamiltonian cycle (if exists).

Steps:

1. Start with an empty path array path[] of size V, where path[i] stores the i-th vertex in
the cycle.
2. Initialize the path with the first vertex:
o path[0]=0.
3. Define a utility function isSafe to check:
o The vertex is adjacent to the previous vertex in the path.
o The vertex has not already been included in the path.
4. Use recursion to add vertices to the path:
o If the path includes all vertices and there is an edge from the last vertex to the
first vertex, return true.
o Else, for each unvisited vertex, check if it can be added to the path using isSafe.
o If a vertex is valid, add it to the path and recursively attempt to find a
Hamiltonian cycle.
o If no valid vertex is found, backtrack by removing the vertex from the path.
5. If no Hamiltonian cycle is found, return false.

Example: Let’s consider a graph with 5 vertices (V=0,1,2,3,4) This can be represented as an
adjacency matrix:

Adjacency Matrix=[0 1 0 1 0
10111
01001
11001
0 1 1 1 0]
 1. Initialization:
o Start at vertex 0: path[0]=0
o The initial path is: [0,−1,−1,−1,−1]
2. Position 1:
o Consider vertex 1 (connected to 0).
o Update the path: [0,1,−1,−1,−1]
3. Position 2:
o Consider vertex 2 (connected to 1).
o Update the path: [0,1,2,−1,−1].
4. Position 3:
o Consider vertex 4 (connected to 2).
o Update the path: [0,1,2,4,−1].
5. Position 4:
o Consider vertex 3 (connected to 4).
o Update the path: [0,1,2,4,3].
6. Complete Cycle Check:
o Check if the last vertex (3) is connected to the starting vertex (0).
o Since 3↔03, the cycle is complete.

The Hamiltonian Cycle is:

0→1→2→4→3→0

Vertices and edges: 0→1, 1→2, 2→4, 4→3, 3→0

20) Find a Hamiltonian cycle for the following graph: A graph with 5 vertices:

• V1 ↔ V2,
• V2 ↔ V3,
• V3 ↔ V4,
• V4 ↔ V5,
• V5 ↔ V1, and
• V1 ↔ V3.
Show how backtracking explores the paths to find a Hamiltonian cycle.

Solution:

A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once and returns to
the starting vertex. For the given graph, we will use backtracking to explore possible paths.
Here's the step-by-step process:

The graph can be represented as:

• Vertices: V1, V2, V3, V4, V5

• Edges:
o V1 ↔ V2
 o V2 ↔ V3
o V3 ↔ V4
o V4 ↔ V5
o V5 ↔ V1
o V1 ↔ V3

Steps of Backtracking

1. Start at V1:
o Add V1 to the path: Path = [V1]
2. Explore Neighbors of V1:
o Neighbors: V2, V3, V5
o Choose V2 (first neighbor): Path = [V1, V2]
3. Explore Neighbors of V2:
o Neighbors: V1, V3
o V1 is already visited, so choose V3: Path = [V1, V2, V3]
4. Explore Neighbors of V3:
o Neighbors: V2, V4, V1
o V2 and V1 are already visited, so choose V4: Path = [V1, V2, V3, V4]
5. Explore Neighbors of V4:
o Neighbors: V3, V5
o V3 is already visited, so choose V5: Path = [V1, V2, V3, V4, V5]
6. Check for Hamiltonian Cycle:
o V5 has a neighbor V1, which is the starting vertex.
o Add V1 to complete the cycle: Path = [V1, V2, V3, V4, V5, V1]

Backtracking Path Exploration

If at any step, no valid neighbour can be added to the path, backtracking removes the last
vertex and explores other options. However, in this graph, the first exploration results in a
Hamiltonian cycle without backtracking because the graph is simple and well-connected.

The Hamiltonian cycle for this graph is: V1 → V2 → V3 → V4 → V5 → V1