Backtracking in Computer Science
• Principles, Algorithms, and Applications
• Presented by: Akshat
• Date: [Add Date]
Introduction
• Backtracking is a general algorithmic
technique that considers searching every
possible combination to solve a computational
problem.
• It incrementally builds candidates to the
solutions and abandons a candidate as soon as
it determines the candidate cannot be
completed to a valid solution.
Why Use Backtracking?
• • Useful in solving problems with a large set of
input possibilities.
• • Applies constraints early to reduce
computation.
• • Helps find all or one valid solution efficiently.
• • Preferred in problems involving decision
making, permutations, combinations, and
game solving.
Backtracking vs Brute Force
• Feature | Brute Force | Backtracking
• --------|-------------|-------------
• Tries all options | Yes | Yes, but intelligently
• Uses constraints | No | Yes (early pruning)
• Efficiency | Very Low | Higher
• Memory usage | Depends | Depends (uses
recursion)
General Backtracking Algorithm
• function backtrack(parameters):
• if solution is found:
• return or print solution
• for all available choices:
• if choice is valid:
• make the choice
• backtrack(next parameters)
• undo the choice (backtrack)
Key Concepts
• • Decision Tree: Explores all possible decisions
at each step.
• • Recursion: Uses stack to go deep into
possible choices.
• • Pruning: Eliminate choices that violate
constraints.
• • Constraint Satisfaction: Only continue if
current step satisfies problem rules.
Example 1 – N-Queens Problem
• • Place N queens on an N x N chessboard so
that no two queens threaten each other.
• • Constraints: No two queens share the same
row, column, or diagonal.
• • Use backtracking to try placing queen row
by row.
• • Backtrack if placing a queen leads to conflict.
N-Queens Code (Python)
• def solveNQueens(board, row):
• if row >= N:
• print(board)
• return
• for col in range(N):
• if isSafe(board, row, col):
• board[row][col] = 'Q'
• solveNQueens(board, row + 1)
• board[row][col] = '.' # backtrack
Example 2 – Rat in a Maze
• • Find a path from top-left to bottom-right in a
grid.
• • Rat can move in allowed directions (usually
right and down).
• • Blocked paths are avoided.
• • Backtrack when no further move is possible.
Other Backtracking Problems
• • Sudoku Solver
• • Subset Sum Problem
• • Permutation Generator
• • Knight’s Tour
• • Combination Sum
• • All require checking constraints at each step.
Optimizations in Backtracking
• • Pruning: Avoid unnecessary paths.
• • Ordering: Try promising choices first.
• • Memoization: Cache intermediate results
(rare in pure backtracking).
• • Helps reduce time complexity.
Time Complexity
• • Worst-case time complexity is usually
exponential.
• • For N-Queens: O(N!) due to permutations.
• • Depends on branching factor and depth of
recursion.
Advantages and Limitations
• Advantages:
• • Simple and intuitive
• • Works well for constraint satisfaction
problems
• • Finds all possible solutions
• Limitations:
• • Slow for large datasets
• • Uses stack memory due to recursion
Real-World Applications
• • Puzzle solving: Sudoku, Crosswords
• • AI Game solving: Chess, Tic-Tac-Toe
• • Cryptography: Key space exploration
• • Automated Planning: Decision making in
robotics
Conclusion
• • Backtracking is a powerful technique.
• • Efficient in solving recursive and constraint-
based problems.
• • Foundation for many algorithms in computer
science and AI.
References
• • GeeksforGeeks.org
• • TutorialsPoint.com
• • CLRS (Introduction to Algorithms)
• • Lecture slides and notes
