Backtracking: General Method
Backtracking is a general algorithmic technique that involves searching for a solution to a problem incrementally, one
piece at a time, and removing solutions that fail to satisfy the constraints of the problem. It is often used to solve
constraint satisfaction problems such as puzzles, games, and combinatorial optimization problems.
Key Steps in Backtracking:
Choose: Select a possible choice for the current position (candidate solution).
Explore: Recursively proceed to solve the problem by moving to the next position.
Check Constraints: If the current solution violates the constraints, discard (backtrack) it.
Backtrack: If a solution is invalid or reaches a dead end, undo the last choice and try a new one.
Backtracking can be represented as a state space tree, where each node represents a partial solution. The algorithm
explores the tree in a depth-first manner, pruning branches that are invalid or lead to dead ends. This reduces the
search space and improves efficiency over brute force approaches.
Example Applications:
N-Queens Problem
Sudoku Solving
Graph Coloring
Hamiltonian Path Problem
--------------------------------------------------------------------------------------------------------------------------------------------------------------
8-Queens Problem Using Backtracking
The 8-Queens problem involves placing 8 queens on a chessboard such that no two queens can attack each other. In
chess, a queen can move horizontally, vertically, or diagonally, so no two queens can share the same row, column, or
diagonal.
Approach:
The problem can be solved using backtracking by placing queens row by row and checking for conflicts in the current
column and both diagonals (primary and secondary) for each placement.
Algorithm Steps:
Start with the first row.
Try placing a queen in each column of the current row.
For each placement, check if it’s safe (i.e., no other queens can attack it).
If it’s safe, move to the next row and repeat the process.
If placing a queen leads to a conflict, backtrack by removing the last placed queen and trying a new position in the
previous row.
Continue this process until all 8 queens are successfully placed on the board.
Algorithm (Pseudo-code):
function solveNQueens(board, row):
if row >= N: // If all queens are placed
print(board) // Print or store the board configuration
, return
for col in 0 to N-1: // Try all columns in the current row
if isSafe(board, row, col): // Check if placing queen is safe
board[row][col] = 1 // Place the queen
solveNQueens(board, row + 1) // Recur for the next row
board[row][col] = 0 // Backtrack by removing the queen
function isSafe(board, row, col):
// Check the column, left diagonal, and right diagonal
for each previous row i:
if a queen is placed in the same column or diagonal:
return false
return true
N = 8 // Number of queens
board = createEmptyBoard(N)
solveNQueens(board, 0)
Explanation:
solveNQueens is the recursive function that tries to place queens row by row.
isSafe checks if placing a queen at a particular position would result in a conflict.
The solution is built row by row. If a conflict occurs, the algorithm backtracks by removing the queen and trying the next
possible position in the previous row.
Example:
A solution for the 8-Queens problem can look like this:
. . . . . . Q .
. . Q. . . . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
Q. . . . . . .
. . . . . Q . .
. . . Q . . . .
This board represents one valid arrangement of 8 queens where none of them can attack each other.
Complexity:
Time complexity: O(N!), where N is the number of queens (since each row has N possible positions, but many invalid
solutions are pruned).
Space complexity: O(N^2) for storing the chessboard.
Summary
, Backtracking is a general method used for solving constraint satisfaction problems by incrementally building solutions
and discarding those that do not satisfy constraints.
The 8-Queens problem is a classic application of backtracking, where the solution is built row by row, and invalid
configurations are pruned by checking for conflicts.
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Backtracking: Sum of Subsets Problem
The Sum of Subsets problem is a classic combinatorial problem where the objective is to find all subsets of a given set
whose sum equals a specified target value. Backtracking is an ideal approach for this problem as it helps in exploring all
possible subsets while efficiently pruning solutions that cannot lead to the desired sum.
Problem Definition:
Given a set of positive integers,
S={s 1,s2,…,sn}, and a target sum T, the goal is to find all subsets of S such that the sum of the elements in each
subset equals T.
Approach:
Search Space: The power set (all subsets) of S is explored. For each element, there are two possibilities:
Include the element in the subset.
Exclude the element from the subset.
Backtracking Process: The algorithm incrementally builds the subset, checking at each step whether:
The subset’s current sum is equal to the target (solution found).
The current sum exceeds the target (prune the branch).
Algorithm Steps:
Start with an empty subset and explore adding elements one by one.
After adding an element, check if the sum of the subset exceeds the target sum.
If it exceeds, backtrack by removing the last added element and explore other options.
If the sum is equal to the target, print or store the current subset as a valid solution.
Recursively repeat the process for the remaining elements.
Algorithm (Pseudo-code):
function sumOfSubsets(set, subset, index, current_sum, target_sum):
if current_sum == target_sum: // If subset sum equals target
print(subset) // Valid subset found
return
if current_sum > target_sum or index == len(set): // If the sum exceeds target or no elements left
return // Prune the branch
// Include the current element
subset.append(set[index])
sumOfSubsets(set, subset, index + 1, current_sum + set[index], target_sum)
Backtracking is a general algorithmic technique that involves searching for a solution to a problem incrementally, one
piece at a time, and removing solutions that fail to satisfy the constraints of the problem. It is often used to solve
constraint satisfaction problems such as puzzles, games, and combinatorial optimization problems.
Key Steps in Backtracking:
Choose: Select a possible choice for the current position (candidate solution).
Explore: Recursively proceed to solve the problem by moving to the next position.
Check Constraints: If the current solution violates the constraints, discard (backtrack) it.
Backtrack: If a solution is invalid or reaches a dead end, undo the last choice and try a new one.
Backtracking can be represented as a state space tree, where each node represents a partial solution. The algorithm
explores the tree in a depth-first manner, pruning branches that are invalid or lead to dead ends. This reduces the
search space and improves efficiency over brute force approaches.
Example Applications:
N-Queens Problem
Sudoku Solving
Graph Coloring
Hamiltonian Path Problem
--------------------------------------------------------------------------------------------------------------------------------------------------------------
8-Queens Problem Using Backtracking
The 8-Queens problem involves placing 8 queens on a chessboard such that no two queens can attack each other. In
chess, a queen can move horizontally, vertically, or diagonally, so no two queens can share the same row, column, or
diagonal.
Approach:
The problem can be solved using backtracking by placing queens row by row and checking for conflicts in the current
column and both diagonals (primary and secondary) for each placement.
Algorithm Steps:
Start with the first row.
Try placing a queen in each column of the current row.
For each placement, check if it’s safe (i.e., no other queens can attack it).
If it’s safe, move to the next row and repeat the process.
If placing a queen leads to a conflict, backtrack by removing the last placed queen and trying a new position in the
previous row.
Continue this process until all 8 queens are successfully placed on the board.
Algorithm (Pseudo-code):
function solveNQueens(board, row):
if row >= N: // If all queens are placed
print(board) // Print or store the board configuration
, return
for col in 0 to N-1: // Try all columns in the current row
if isSafe(board, row, col): // Check if placing queen is safe
board[row][col] = 1 // Place the queen
solveNQueens(board, row + 1) // Recur for the next row
board[row][col] = 0 // Backtrack by removing the queen
function isSafe(board, row, col):
// Check the column, left diagonal, and right diagonal
for each previous row i:
if a queen is placed in the same column or diagonal:
return false
return true
N = 8 // Number of queens
board = createEmptyBoard(N)
solveNQueens(board, 0)
Explanation:
solveNQueens is the recursive function that tries to place queens row by row.
isSafe checks if placing a queen at a particular position would result in a conflict.
The solution is built row by row. If a conflict occurs, the algorithm backtracks by removing the queen and trying the next
possible position in the previous row.
Example:
A solution for the 8-Queens problem can look like this:
. . . . . . Q .
. . Q. . . . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
Q. . . . . . .
. . . . . Q . .
. . . Q . . . .
This board represents one valid arrangement of 8 queens where none of them can attack each other.
Complexity:
Time complexity: O(N!), where N is the number of queens (since each row has N possible positions, but many invalid
solutions are pruned).
Space complexity: O(N^2) for storing the chessboard.
Summary
, Backtracking is a general method used for solving constraint satisfaction problems by incrementally building solutions
and discarding those that do not satisfy constraints.
The 8-Queens problem is a classic application of backtracking, where the solution is built row by row, and invalid
configurations are pruned by checking for conflicts.
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Backtracking: Sum of Subsets Problem
The Sum of Subsets problem is a classic combinatorial problem where the objective is to find all subsets of a given set
whose sum equals a specified target value. Backtracking is an ideal approach for this problem as it helps in exploring all
possible subsets while efficiently pruning solutions that cannot lead to the desired sum.
Problem Definition:
Given a set of positive integers,
S={s 1,s2,…,sn}, and a target sum T, the goal is to find all subsets of S such that the sum of the elements in each
subset equals T.
Approach:
Search Space: The power set (all subsets) of S is explored. For each element, there are two possibilities:
Include the element in the subset.
Exclude the element from the subset.
Backtracking Process: The algorithm incrementally builds the subset, checking at each step whether:
The subset’s current sum is equal to the target (solution found).
The current sum exceeds the target (prune the branch).
Algorithm Steps:
Start with an empty subset and explore adding elements one by one.
After adding an element, check if the sum of the subset exceeds the target sum.
If it exceeds, backtrack by removing the last added element and explore other options.
If the sum is equal to the target, print or store the current subset as a valid solution.
Recursively repeat the process for the remaining elements.
Algorithm (Pseudo-code):
function sumOfSubsets(set, subset, index, current_sum, target_sum):
if current_sum == target_sum: // If subset sum equals target
print(subset) // Valid subset found
return
if current_sum > target_sum or index == len(set): // If the sum exceeds target or no elements left
return // Prune the branch
// Include the current element
subset.append(set[index])
sumOfSubsets(set, subset, index + 1, current_sum + set[index], target_sum)
