Module 5: Backtracking and Branch and Bound

BACKTRACKING
 Backtracking is a systematic and recursive algorithmic technique used to solve complex
problems by incrementally making choices and exploring decision trees until a valid
solution is found or all possibilities are exhausted.
 Backtracking is a versatile technique that can be applied to various problem domains,
including puzzles, optimization problems, and search algorithms. Some well-known
problems that can be solved using backtracking include the N-Queens puzzle, Sudoku,
maze-solving, and graph traversal.
 Types of Backtracking Algorithm:
o N-Queen Problem
o Sum of Subset Problem
o Graph coloring Problem

N-Queen Problem
 N Queen problem demands us to place N queens on a N x N chessboard so that no
queen can attack any other queen directly.
 Problem Statement: We need to find out all the possible arrangements in which N
queens can be seated in each row and each column so that all queens are safe. The
queen moves in 8 directions and can directly attack in these 8 directions only.
 Algorithm:
Step 1: Place queen in the current row.
Step 2: Check if the position is safe (row, column, diagonals).
Step 3: If safe, move to the next row (recursive call).
Step 4: If not safe or no position is valid, backtrack.
1. 4 - Queen Problem
 This problem demands us to put 4 queens on 4 X 4 chessboard in such a way that one
queen is present in each row and column and no queen can attack any other queen
directly. this means no 2 or more queens can be placed in the same diagonal or row or
column.

 Let's try to put queens Q1, Q2, Q3, and Q4 in the above present chessboard. The first
queen i.e. Q1 can be put anywhere on the chessboard as there is no other queen present
on the board and hence no restrictions. Therefore, putting Q1 at position (0,0). So the
path so far is| (0,0)|.
 When Q1 has been placed there are some places where the next queens can't be placed
to fulfill given conditions. So to put queen Q2 in the second row we have positions - (1,2)
and (1,3). Let's put it at (1,2). The path so far is | (0,0) -> (1,2)|.

 Now this placement of Q2 blocks all the boxes of row 3 and hence there is no way to put
Q3. If we put it at (2,0) or (2,2), Q1 will attack it, and at (2,1) and (2,3) Q2 attacks it.
Therefore, we backtrack from here and revisit the previous solution by readjusting the
position of Q2. So instead of putting it at (1,2), we put it at (1,3). The path so far is | (0,0)
-> (1,3)|.

 We put Q3 at (2,1). Hence, the path so far is | (0,0) -> (1,3) -> (2,1)|.
 Now again the same problem occurs, there left no box to place Q4. There was only 1 way
to place Q3 and all placements of Q2 have been explored, so now we come to Q1 for re-
adjustment. We move it from (0,0) to (0,1). The path so far is | (0,1)|.

 We put Q2 at (1,0). The path so far is | (0,1) -> (1,0)|.

 Q3 is put at (2,2). The path so far is | (0,1) -> (1,0) -> (2,2)|.
 Now again there is no space left for placement of Q4 in row 4. Therefore, we again
backtrack and readjust position of Q2 from (1,0) to (1,3). The path so far is | (0,1) -> (1,3).

 Q3 is put at (2,0). The path so far is | (0,1) -> (1,0) -> (2,0)|.

 We put Q4 at (3,2). The path so far is | (0,1) -> (1,0) -> (2,0) -> (3,2)|.

 Therefore, through backtracking, we reached a solution where 4 queens are put in each
row and column so that no queen is attacking any other on a 4 X 4 chessboard.
 Another solution can be:
2. 8 - Queen Problem
 Our goal is to place 8 queens on the board in such a way that no two queens attack each
other, which will require careful strategic positioning.
Solution:

 Time Complexity: O(N!) (worst case)

Sum of Subsets Problem

 In the sum of subsets problem, there is a given set with some non-negative integer
elements. And another sum value is also provided, our task is to find all possible subsets
of the given set whose sum is the same as the given sum value.
 Suppose the given set and sum value is −
Set = {1, 9, 7, 5, 18, 12, 20, 15} and sum value = 35
All possible subsets of the given set, where sum is equal to Value
o {1 9 7 18}
o {1 9 5 20}
o {5 18 12}
 Algorithm:
Step 1: First, take an empty subset.
Step 2: Include the next element, which is at index 0 to the empty set.
Step 3: If the subset is equal to the sum value, mark it as a part of the solution.
Step 4: 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.
Step 5: Now, move to the next element in the set and check for another solution until all
combinations have been tried.
 Example:
Consider w = {5, 7, 10, 12, 15, 18, 20} and capacity M = 35

Items in sub set Condition Comment

{} 0 Initial condition
{5} 5 < 35 Select 5 and Add next element
{ 5, 7 } 12 < 35 Select 7 and Add next element
{ 5, 7, 10 } 22 < 35 Select 20 and Add next element
{ 5, 7, 10, 12 } 34 < 35 Select 12 and Add next element
{ 5, 7, 10, 12, 15 } 49 > 35 Sum exceeds M, so backtrack and remove 12
{ 5, 7, 10, 15 } 37 > 35 Sum exceeds M, so backtrack and remove 15
{ 5, 7, 12 } 24 < 35 Add next element
{ 5, 7, 12, 15 } 39 > 35 Sub set sum exceeds, so backtrack
{ 5, 10 } 15 < 35 Add next element
{ 5, 10, 12 } 27 < 35 Sub set sum exceeds, so backtrack
{ 5, 10, 12, 15 } 42 > 35 Sub set sum exceeds, so backtrack
{ 5, 10, 15 } 30 < 35 Add next element
{ 5, 10, 15, 18 } 48 > 35 Sub set sum exceeds, so backtrack
{ 5, 10, 18 } 33 < 35 Add next element
{ 5, 10, 18, 20 } 53 > 35 Sub set sum exceeds, so backtrack
{ 5, 10, 20 } 35 Solution Found
Graph Coloring
 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.

 Algorithm:
Step 1: Try coloring vertex v with each color from 1 to m.
Step 2: Check no adjacent node has the same color).
Step 3: If coloring is possible for all vertices, return true.
Step 4: Else, backtrack.
  Example:

BRANCH AND BOUND

 The Branch and Bound Algorithm is a method used in combinatorial optimization
problems to systematically search for the best solution.
 It works by dividing the problem into smaller sub problems, or branches, and then
eliminating certain branches based on bounds on the optimal solution.
 This process continues until the best solution is found or all branches have been
explored.
 Types of Branch and Bound:
o Travelling Salesperson Problem
o 15 Puzzle Problem
Travelling Salesperson Problem (TSP)
 The Travelling Salesperson Problem (TSP) using the Branch and Bound technique aims to
find the shortest route that visits each city exactly once and returns to the starting city.
 Branch and Bound is an optimization algorithm that systematically explores possible
solutions (routes) while pruning branches that cannot lead to an optimal solution.
 This approach reduces the computational effort compared to brute-force methods.
 Algorithm:
Step 1: Calculate cost matrix.
Step 2: Reduce matrix rows & columns to find lower bound.
Step 3: Branch on possible paths and calculate cost.
Step 4: Prune paths that exceed current best cost.

 Example:

o First Create cost matrix

row/col no 1 2 3 4

1 - 10 15 20

2 10 - 35 25

3 15 35 - 30

4 20 25 30 -
o After row reduction the matrix will be:

row/col no 1 2 3 4

1 - 0 5 10

2 0 - 25 15

3 0 20 - 15

4 0 5 10 -

o Row minimums are 10, 10, 15 and 20.

row/col no 1 2 3 4

1 - 0 0 0

2 0 - 20 5

3 0 20 - 5

4 0 5 5 -

o The column minimums are 0, 0, 5 and 10.

o So the cost reduction of the matrix is (10 + 10 + 15 + 20 + 5 + 10) = 70
o Now let us consider movement from 1 to 2: Initially after substituting the 1st
row and 2nd column to infinity, the matrix will be:

row/col no 1 2 3 4

1 - - - -

2 - - 20 5

3 0 - - 5

4 0 - 5 -
o After the matrix is reduced the row minimums will be 5, 0, 0

row/col no 1 2 3 4

1 - - - -

2 - - 15 0

3 0 - - 5

4 0 - 5 -

o and the column minimum will be 0, 5, 0

row/col no 1 2 3 4

1 - - - -

2 - - 10 0

3 0 - - 5

4 0 - 0 -

o So the cost will be 70 + cost (1, 2) + 5 + 5 = 70 + 0 + 5 + 5 = 80.

o Continue this process till traversal is complete and find the minimum cost.

 Time Complexity: O(n!), but pruning improves performance.

15 Puzzle Problem
 The 15-Puzzle is a simple puzzle. It consists of a 4 x 4 grid with tiles numbered 1 through
15, the last tile omitted (call this the blank tile).
 The goal of the puzzle is to go from a scrambled position to the solved position, which is
to arrange the numbers in ascending order from left to right, top to bottom. You can only
move tiles adjacent to the blank tile, and you do this by “swapping” positions with the
blank tile.

 Algorithm:
Step1: It's a 4x4 board containing 15 numbered tiles (1 to 15) and one empty
space.
Step2: The tiles are arranged randomly.
Step3: The goal is to move the tiles (by sliding them into the empty space) to
reach the goal configuration

 Example:
Real Life Applications
Algorithm/Problem Real-Life Applications

AI, constraint satisfaction problems, chess game

N-Queen Problem
programming

Knapsack problem, resource allocation, finance

Sum of Subsets
(investment selection)

Register allocation in compilers, map coloring,

Graph Coloring
scheduling problems

Logistics, route planning, delivery systems, circuit

TSP
design
 Algorithm/Problem Real-Life Applications

Game development, robotics path planning, AI

15 Puzzle
heuristics