841: Backtracking — Generic Recursive Framework with Pruning

Difficulty: 3 Level: Intermediate Enumerate all valid solutions by building candidates incrementally and abandoning dead-end branches early — the algorithmic engine behind N-queens, Sudoku solvers, and combinatorial optimization.

The Problem This Solves

Many problems require finding all (or the best) solution in a combinatorial search space: N-queens placement, Sudoku, graph coloring, subset sum, scheduling with constraints. Brute force generates all candidates then filters — O(n! × n) for permutations. Backtracking does better by pruning: if a partial assignment already violates constraints, abandon it immediately without completing it. This is not just an academic exercise. Sudoku solvers, SAT solvers (DPLL algorithm), constraint satisfaction in AI planning, and automatic theorem provers are all backtracking with increasingly sophisticated pruning strategies. The difference between a 1ms and a 1s Sudoku solve is almost entirely in the quality of the pruning predicate. The generic framework makes the pattern explicit: try each choice, check the constraint predicate after each extension (not just at leaves), recurse, then undo the choice (backtrack). Implemented in Rust with mutable `Vec` state passed by `&mut` reference — no heap allocation per recursive call.

The Intuition

Think of it as tree search: each node is a partial solution, branches are choices at the next position. DFS with pruning: at each node, check if the current partial solution is still consistent. If not, don't explore any of its subtrees — that's the prune. If yes, extend to all children. At leaf nodes (full assignment), collect the solution. The key insight: check constraints at every extension, not just at the end. For N-queens, check whether placing a queen in column `col` at row `row` conflicts with any already-placed queen. This eliminates entire subtrees of size (n-row)! at each prune.

How It Works in Rust

// Constraint check: can we place a queen at (row, col)?
fn is_safe(board: &[usize], row: usize, col: usize) -> bool {
 for r in 0..row {
     let c = board[r];
     // Conflicts: same column, or same diagonal
     if c == col || c.abs_diff(col) == r.abs_diff(row) {
         return false;
     }
 }
 true
}

// N-Queens: board[row] = column of queen in that row
fn n_queens(n: usize) -> Vec<Vec<usize>> {
 let mut solutions = Vec::new();
 let mut board = vec![0usize; n];
 n_queens_rec(n, 0, &mut board, &mut solutions);
 solutions
}

fn n_queens_rec(n: usize, row: usize, board: &mut Vec<usize>, solutions: &mut Vec<Vec<usize>>) {
 if row == n {
     solutions.push(board.clone());  // Complete solution: collect
     return;
 }
 for col in 0..n {
     if is_safe(board, row, col) {
         board[row] = col;                              // Choose
         n_queens_rec(n, row + 1, board, solutions);   // Explore
         // Backtrack: board[row] will be overwritten in next iteration
         // (explicit undo only needed if state isn't overwritten)
     }
 }
}

// Permutations: explicit undo via used[] flag
fn permutations_rec<T: Clone>(xs: &[T], current: &mut Vec<T>,
                            used: &mut Vec<bool>, result: &mut Vec<Vec<T>>) {
 if current.len() == xs.len() { result.push(current.clone()); return; }
 for i in 0..xs.len() {
     if !used[i] {
         used[i] = true;          // Choose
         current.push(xs[i].clone());
         permutations_rec(xs, current, used, result);  // Explore
         current.pop();           // Undo choice
         used[i] = false;         // Undo flag — explicit backtrack
     }
 }
}

The `&mut Vec` pattern — passing mutable collections by reference rather than returning them — is idiomatic Rust for recursive algorithms that accumulate results. It avoids cloning partial solutions on every recursive call.

What This Unlocks

SAT solvers and constraint programming: The DPLL algorithm for satisfiability is backtracking with unit propagation as pruning — the core of every modern SAT solver (MiniSAT, Z3).
Sudoku and puzzle solving: Constraint propagation (eliminating candidate values from peers) + backtracking solves any Sudoku; the same pattern handles Nonograms, Kakuro, and logic puzzles.
Subset enumeration and knapsack variants: "Find all subsets with sum exactly k" is backtracking with a sum constraint — used in portfolio optimization, scheduling, and combinatorial auction algorithms.

Key Differences

Concept	OCaml	Rust
Mutable accumulator	`ref` list or `Buffer`	`&mut Vec` passed down — explicit
Board state	`int list` (functional, no undo needed)	`Vec<usize>` with in-place update
Undo step	Functional: no undo (immutable state)	`current.pop(); used[i] = false;`
Collect solutions	`results := sol :: !results`	`solutions.push(board.clone())`
Constraint check	Pure function on list	Pure function on slice — identical style

/// Backtracking: Generic Recursive Framework with Pruning.
///
/// Demonstrated with N-Queens and permutation generation.
/// Pattern: try choice → check constraint → recurse → undo (backtrack).

/// Check if placing a queen at (row, col) is safe.
fn is_safe(board: &[usize], row: usize, col: usize) -> bool {
    for r in 0..row {
        let c = board[r];
        if c == col || c.abs_diff(col) == r.abs_diff(row) {
            return false;
        }
    }
    true
}

/// N-Queens: find all solutions. board[row] = column of queen.
fn n_queens(n: usize) -> Vec<Vec<usize>> {
    let mut solutions = Vec::new();
    let mut board = vec![0usize; n];
    n_queens_rec(n, 0, &mut board, &mut solutions);
    solutions
}

fn n_queens_rec(n: usize, row: usize, board: &mut Vec<usize>, solutions: &mut Vec<Vec<usize>>) {
    if row == n {
        solutions.push(board.clone());
        return;
    }
    for col in 0..n {
        if is_safe(board, row, col) {
            board[row] = col;                             // choose
            n_queens_rec(n, row + 1, board, solutions);  // explore
            // board[row] = 0; -- undo (implicit, will be overwritten)
        }
    }
}

/// Generate all permutations of a slice.
fn permutations<T: Clone>(xs: &[T]) -> Vec<Vec<T>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; xs.len()];
    permutations_rec(xs, &mut current, &mut used, &mut result);
    result
}

fn permutations_rec<T: Clone>(
    xs: &[T],
    current: &mut Vec<T>,
    used: &mut Vec<bool>,
    result: &mut Vec<Vec<T>>,
) {
    if current.len() == xs.len() {
        result.push(current.clone());
        return;
    }
    for i in 0..xs.len() {
        if !used[i] {
            used[i] = true;
            current.push(xs[i].clone());  // choose
            permutations_rec(xs, current, used, result);
            current.pop();                // undo
            used[i] = false;              // undo
        }
    }
}

/// Subset sum: does any subset of nums sum to target?
fn subset_sum(nums: &[i64], target: i64) -> bool {
    fn bt(nums: &[i64], idx: usize, remaining: i64) -> bool {
        if remaining == 0 { return true; }
        if idx == nums.len() || remaining < 0 { return false; }
        // Include nums[idx] or skip it
        bt(nums, idx + 1, remaining - nums[idx]) || bt(nums, idx + 1, remaining)
    }
    bt(nums, 0, target)
}

fn print_board(board: &[usize]) {
    let n = board.len();
    for &col in board {
        let row: String = (0..n).map(|c| if c == col { 'Q' } else { '.' }).collect();
        println!("{row}");
    }
    println!();
}

fn main() {
    let sols = n_queens(4);
    println!("4-Queens: {} solutions", sols.len());
    print_board(&sols[0]);

    println!("8-Queens: {} solutions", n_queens(8).len()); // 92

    let mut perms = permutations(&[1, 2, 3]);
    perms.sort();
    println!("permutations([1,2,3]): {} (expected 6)", perms.len());
    for p in &perms { println!("  {p:?}"); }

    println!("subset_sum([3,1,4,1,5], 9): {}", subset_sum(&[3, 1, 4, 1, 5], 9));
    println!("subset_sum([3,1,4,1,5], 11): {}", subset_sum(&[3, 1, 4, 1, 5], 11));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_4_queens_count() {
        assert_eq!(n_queens(4).len(), 2);
    }

    #[test]
    fn test_8_queens_count() {
        assert_eq!(n_queens(8).len(), 92);
    }

    #[test]
    fn test_queens_valid() {
        for board in n_queens(8) {
            let n = board.len();
            // Every row has exactly one queen
            for row in 0..n {
                for other in 0..n {
                    if row != other {
                        assert_ne!(board[row], board[other], "column clash");
                        assert_ne!(board[row].abs_diff(board[other]),
                                   row.abs_diff(other), "diagonal clash");
                    }
                }
            }
        }
    }

    #[test]
    fn test_permutations_count() {
        assert_eq!(permutations(&[1, 2, 3]).len(), 6);
        assert_eq!(permutations(&[1, 2, 3, 4]).len(), 24);
    }

    #[test]
    fn test_permutations_content() {
        let mut perms = permutations(&[1, 2, 3]);
        perms.sort();
        assert_eq!(perms[0], vec![1, 2, 3]);
        assert_eq!(perms[5], vec![3, 2, 1]);
    }

    #[test]
    fn test_subset_sum() {
        assert!(subset_sum(&[3, 1, 4, 1, 5], 9));    // 3+1+5=9
        assert!(!subset_sum(&[3, 1, 4, 1, 5], 11)); // no subset sums to 11
        assert!(subset_sum(&[3, 1, 4, 1, 5], 5));    // 5 itself
    }
}

(* Backtracking Framework in OCaml — N-Queens and Permutations *)

(* N-Queens: board.(row) = column of queen in that row *)
(* Check if placing a queen at (row, col) is safe given placements so far *)
let is_safe (board : int array) (row : int) (col : int) : bool =
  let ok = ref true in
  for r = 0 to row - 1 do
    let c = board.(r) in
    if c = col || abs (c - col) = abs (r - row) then
      ok := false
  done;
  !ok

(* Solve N-Queens: returns all solutions *)
let n_queens (n : int) : int array list =
  let board = Array.make n 0 in
  let solutions = ref [] in
  let rec solve row =
    if row = n then
      solutions := Array.copy board :: !solutions
    else
      for col = 0 to n - 1 do
        if is_safe board row col then begin
          board.(row) <- col;
          solve (row + 1);
          (* backtrack: no explicit undo needed as we overwrite *)
        end
      done
  in
  solve 0;
  !solutions

(* Print a board *)
let print_board (board : int array) =
  Array.iter (fun col ->
    let row = String.init (Array.length board) (fun c -> if c = col then 'Q' else '.') in
    print_string (row ^ "\n")
  ) board;
  print_newline ()

(* Generic permutation via backtracking *)
let permutations (xs : 'a list) : 'a list list =
  let result = ref [] in
  let n = List.length xs in
  let arr = Array.of_list xs in
  let used = Array.make n false in
  let current = Array.make n (List.hd xs) in
  let rec gen depth =
    if depth = n then
      result := Array.to_list current :: !result
    else
      for i = 0 to n - 1 do
        if not used.(i) then begin
          used.(i) <- true;
          current.(depth) <- arr.(i);
          gen (depth + 1);
          used.(i) <- false  (* backtrack *)
        end
      done
  in
  gen 0;
  !result

let () =
  let sols = n_queens 4 in
  Printf.printf "4-Queens: %d solutions\n" (List.length sols);
  print_board (List.hd sols);
  Printf.printf "8-Queens: %d solutions\n" (List.length (n_queens 8));
  let perms = permutations [1; 2; 3] in
  Printf.printf "permutations([1,2,3]): %d\n" (List.length perms);
  List.iter (fun p ->
    Printf.printf "  [%s]\n" (String.concat "," (List.map string_of_int p))
  ) (List.sort compare perms)