Scribd
Upload
9 views11 pages

Backtracking Algorithms Explained

Backtracking algorithms are problem-solving strategies that explore various options to find optimal solutions by trying different paths and reverting when necessary. They are commonly used in scenarios like puzzles, maze navigation, and scheduling problems. Key examples include the N-Queens problem and the Subset Sum problem, which illustrate the algorithm's application in placing queens on a chessboard and finding subsets that sum to a specific value, respectively.

Uploaded by

Radha Rani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
9 views11 pages

Backtracking Algorithms Explained

Backtracking algorithms are problem-solving strategies that explore various options to find optimal solutions by trying different paths and reverting when necessary. They are commonly used in scenarios like puzzles, maze navigation, and scheduling problems. Key examples include the N-Queens problem and the Subset Sum problem, which illustrate the algorithm's application in placing queens on a chessboard and finding subsets that sum to a specific value, respectively.

Uploaded by

Radha Rani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Backtracking

Algorithm
Backtracking algorithms
• Backtracking algorithms are like problem-solving strategies that help explore
different options to find the best solution.
• They work by trying out different paths and if one doesn’t work, they backtrack
and try another until they find the right one.
• It’s like solving a puzzle by testing different pieces until they fit together perfectly.
• 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.
The following is a general outline of
how a backtracking algorithm
works:
1. Choose an initial solution.
2. Explore all possible extensions of the current solution.
3. If an extension leads to a solution, return that solution.
4. If an extension does not lead to a solution, backtrack to the
previous solution and try a different extension.
5. Repeat steps 2-4 until all possible solutions have been explored.
Applications of Backtracking
Algorithm
• Solving puzzles (e.g., Sudoku, puzzles)
• Finding the shortest path through a maze
• Scheduling problems
• Resource allocation problems
• Network optimization problem
Examples
• n-Queens problem
• Subset sum problem
• Graph Coloring
N Queen Problem
• The N Queen is the problem of
placing N chess queens on
an N×N chessboard so that no
two queens attack each other.
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
• Then mark this [row, column] as part of the solution and recursively
check if placing queen here leads to a solution.
• If placing the queen in [row, column] leads to a solution then return true.
• 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.
Subset Sum Problem using
Backtracking
• 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.
• 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.

You might also like