api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2736
  slug: backtracking-algorithms
  title: Backtracking Algorithms
  description: Algorithms that explore candidates and abandon partial solutions.
  summary: "Classic problems solved by backtracking: N-Queens, Sudoku, subset sum, graph coloring, Hamiltonian cycles and maze solving, extended with permutations, combination sum, word search, the knight's tour, palindrome partitioning and generating parentheses."
  use_when[2]: You need a canonical example for the backtracking technique.,You are practicing constraint-satisfaction problems.
  caveats[2]: Backtracking has exponential worst-case cost; pruning decides whether it is practical.,"For optimization problems, dynamic programming or branch and bound may be better."
  related[4]: dynamic-programming-patterns,graph-traversal-algorithms,complexity-classes,greedy-algorithms
  entry_count: 12
  fields[2]{section,field,type,example}:
    data,problem,string,N-Queens
    data,description,string,Place N non-attacking queens on an NxN chessboa…
  category: Algorithms
  category_slug: algorithms
  tags: "algorithms,backtracking,recursion"
  view_count: 47
  created_at: 1793403093
  updated_at: 1793403093
data[12]{problem,description}:
  N-Queens,Place N non-attacking queens on an NxN chessboard.
  Sudoku Solver,"Fill a 9x9 grid satisfying row, column, and box constraints."
  Subset Sum,Find a subset whose sum equals a target value.
  Graph Coloring,Assign colors to vertices so adjacent vertices differ.
  Hamiltonian Cycle,Find a cycle that visits every vertex exactly once.
  Maze Solving,Find a path from start to goal through a maze.
  Permutations,Generate all orderings of a set by fixing an element and recursing on the rest.
  Combination Sum,"Find all combinations of numbers that add up to a target, reusing numbers where allowed."
  Word Search,Find a word in a grid by moving to adjacent cells without reusing a cell.
  Knight's Tour,Move a knight so it visits every square of a chessboard exactly once.
  Palindrome Partitioning,Split a string into parts so every part is a palindrome.
  Generate Parentheses,Produce all well-formed strings of n pairs of parentheses.