Skip to main content

Classic Backtracking Problems

Fundamental backtracking problems that demonstrate key principles and techniques.

N-Queens​

  • Problem: Place n queens on n×n chessboard so no two queens attack each other
  • Constraints: No two queens in same row, column, or diagonal
  • Backtracking: Try placing queen in each row, backtrack if conflict
  • Optimization: Use column and diagonal arrays for faster conflict checking

Sudoku solver​

  • Problem: Fill 9×9 grid with digits 1-9 following Sudoku rules
  • Constraints: No duplicate digits in row, column, or 3×3 box
  • Backtracking: Try each digit in empty cell, backtrack if invalid
  • Optimization: Use bit manipulation for faster constraint checking

Permutations & combinations​

  • Permutations: Generate all possible arrangements of elements
  • Combinations: Generate all possible selections of elements
  • Backtracking: Build solution incrementally, backtrack when complete
  • Optimization: Use swap-based approach for permutations

Subset generation​

  • Problem: Generate all possible subsets of given set
  • Backtracking: For each element, include or exclude it
  • Binary Representation: Use bit manipulation for subset generation
  • Lexicographic Order: Generate subsets in specific order
  • Problem: Find words in 2D grid of characters
  • Constraints: Words must be formed by adjacent cells
  • Backtracking: Explore all possible paths from each cell
  • Optimization: Use Trie for efficient word matching