841 Advanced

Backtracking Framework

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Backtracking Framework" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Many combinatorial optimization and enumeration problems — N-queens, Sudoku solving, permutation generation, subset enumeration, graph coloring, constraint satisfaction — require exploring a search space that grows exponentially with input size. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Many combinatorial optimization and enumeration problems — N-queens, Sudoku solving, permutation generation, subset enumeration, graph coloring, constraint satisfaction — require exploring a search space that grows exponentially with input size. Backtracking systematically explores candidates and abandons (backtracks from) any partial solution as soon as it determines it cannot lead to a valid complete solution. This pruning makes backtracking vastly more efficient than brute force for well-constrained problems, though still exponential in the worst case. Understanding backtracking as a reusable framework — not just specific puzzles — enables applying it to new combinatorial problems.

🎯 Learning Outcomes

• Implement the backtracking template: choose → explore → unchoose

• Use a used flag array to avoid revisiting elements in permutation generation

• Recognize constraint-based pruning: skip choices that violate constraints early

• Apply to N-queens: test placement validity before recursing, backtrack on conflict

• Understand the difference between backtracking (exact, complete) and heuristic search (approximate)

Code Example

#![allow(clippy::all)]
//! # Backtracking Framework
pub fn generate_permutations<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    let mut result = vec![];
    let mut current = vec![];
    let mut used = vec![false; items.len()];
    fn backtrack<T: Clone>(
        items: &[T],
        curr: &mut Vec<T>,
        used: &mut [bool],
        res: &mut Vec<Vec<T>>,
    ) {
        if curr.len() == items.len() {
            res.push(curr.clone());
            return;
        }
        for i in 0..items.len() {
            if !used[i] {
                used[i] = true;
                curr.push(items[i].clone());
                backtrack(items, curr, used, res);
                curr.pop();
                used[i] = false;
            }
        }
    }
    backtrack(items, &mut current, &mut used, &mut result);
    result
}

pub fn generate_subsets<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    let mut result = vec![];
    let mut current = vec![];
    fn backtrack<T: Clone>(items: &[T], start: usize, curr: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        res.push(curr.clone());
        for i in start..items.len() {
            curr.push(items[i].clone());
            backtrack(items, i + 1, curr, res);
            curr.pop();
        }
    }
    backtrack(items, 0, &mut current, &mut result);
    result
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_perms() {
        assert_eq!(generate_permutations(&[1, 2, 3]).len(), 6);
    }
    #[test]
    fn test_subsets() {
        assert_eq!(generate_subsets(&[1, 2, 3]).len(), 8);
    }
}

(* 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)

Key Differences

Aspect	Rust	OCaml
Used flags	`Vec<bool>`	`bool array`
Result accumulation	`&mut Vec<Vec<T>>`	`acc ref` or continuation
Choose/unchoose	`push`/`pop` on `Vec`	`Array.set` true/false
Generic type	`<T: Clone>`	Parametric `'a`
N-queens variant	Separate `fn queens`	Separate or same framework
Iterative variant	`Iterator` via generator	Sequence with `Seq.t`

OCaml Approach

OCaml backtracking uses a used array as bool array mutated in-place. The recursive function returns unit and accumulates results via an acc ref. OCaml's functional style can also express this with continuation-passing: let rec backtrack cont current used = .... The Array.make n false initializes the used flags. OCaml's pattern matching for N-queens constraint checking reads naturally. The List.rev current at leaf nodes (if building the list from head prepending) recovers the correct order.

Full Source

#![allow(clippy::all)]
//! # Backtracking Framework
pub fn generate_permutations<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    let mut result = vec![];
    let mut current = vec![];
    let mut used = vec![false; items.len()];
    fn backtrack<T: Clone>(
        items: &[T],
        curr: &mut Vec<T>,
        used: &mut [bool],
        res: &mut Vec<Vec<T>>,
    ) {
        if curr.len() == items.len() {
            res.push(curr.clone());
            return;
        }
        for i in 0..items.len() {
            if !used[i] {
                used[i] = true;
                curr.push(items[i].clone());
                backtrack(items, curr, used, res);
                curr.pop();
                used[i] = false;
            }
        }
    }
    backtrack(items, &mut current, &mut used, &mut result);
    result
}

pub fn generate_subsets<T: Clone>(items: &[T]) -> Vec<Vec<T>> {
    let mut result = vec![];
    let mut current = vec![];
    fn backtrack<T: Clone>(items: &[T], start: usize, curr: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        res.push(curr.clone());
        for i in start..items.len() {
            curr.push(items[i].clone());
            backtrack(items, i + 1, curr, res);
            curr.pop();
        }
    }
    backtrack(items, 0, &mut current, &mut result);
    result
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_perms() {
        assert_eq!(generate_permutations(&[1, 2, 3]).len(), 6);
    }
    #[test]
    fn test_subsets() {
        assert_eq!(generate_subsets(&[1, 2, 3]).len(), 8);
    }
}

(* 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)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_perms() {
        assert_eq!(generate_permutations(&[1, 2, 3]).len(), 6);
    }
    #[test]
    fn test_subsets() {
        assert_eq!(generate_subsets(&[1, 2, 3]).len(), 8);
    }
}

Deep Comparison

OCaml vs Rust: Backtracking Framework

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement N-queens backtracking using this framework: add a validity check before recursing.

Implement Sudoku solver using backtracking with forward checking (propagate constraints after each placement).

Add an Iterator interface to the backtracking framework so permutations can be consumed lazily.

Implement combination generation (choose k from n) and verify the count equals C(n, k).

Apply backtracking to graph coloring: find a k-coloring of a graph or report that none exists.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust