api: YAML JSON TOON Database
version: 1.0.0
format: yaml
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:
    - You need a canonical example for the backtracking technique.
    - You are practicing constraint-satisfaction problems.
  caveats:
    - 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:
    - dynamic-programming-patterns
    - graph-traversal-algorithms
    - complexity-classes
    - greedy-algorithms
  entry_count: 12
  fields:
    - section: data
      field: problem
      type: string
      example: N-Queens
    - section: data
      field: description
      type: string
      example: Place N non-attacking queens on an NxN chessboa…
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,backtracking,recursion
  view_count: 46
  created_at: 1793403093
  updated_at: 1793403093
data:
  - problem: N-Queens
    description: Place N non-attacking queens on an NxN chessboard.
  - problem: Sudoku Solver
    description: Fill a 9x9 grid satisfying row, column, and box constraints.
  - problem: Subset Sum
    description: Find a subset whose sum equals a target value.
  - problem: Graph Coloring
    description: Assign colors to vertices so adjacent vertices differ.
  - problem: Hamiltonian Cycle
    description: Find a cycle that visits every vertex exactly once.
  - problem: Maze Solving
    description: Find a path from start to goal through a maze.
  - problem: Permutations
    description: Generate all orderings of a set by fixing an element and recursing on the rest.
  - problem: Combination Sum
    description: Find all combinations of numbers that add up to a target, reusing numbers where allowed.
  - problem: Word Search
    description: Find a word in a grid by moving to adjacent cells without reusing a cell.
  - problem: Knight's Tour
    description: Move a knight so it visits every square of a chessboard exactly once.
  - problem: Palindrome Partitioning
    description: Split a string into parts so every part is a palindrome.
  - problem: Generate Parentheses
    description: Produce all well-formed strings of n pairs of parentheses.