811 Advanced

811-hamiltonian-backtrack — Hamiltonian Path (Backtracking)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "811-hamiltonian-backtrack — Hamiltonian Path (Backtracking)" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. A Hamiltonian path visits every vertex exactly once. Key difference from OCaml: 1. **Backtracking style**: Rust's mutable `path` and `visited` with explicit push/pop is imperative; OCaml's recursive approach with immutable lists is more idiomatic but allocates more.

Tutorial

The Problem

A Hamiltonian path visits every vertex exactly once. Unlike Eulerian path (efficient, O(V+E)), Hamiltonian path is NP-complete — no polynomial algorithm is known. The backtracking approach prunes the search tree by abandoning partial paths that cannot possibly complete. It is the basis for TSP (traveling salesman) solvers and appears in puzzle solving (knight's tour, Sudoku) and genome sequencing (alternative to Eulerian for short reads).

🎯 Learning Outcomes

• Implement backtracking for Hamiltonian path: try each unvisited neighbor, recurse, undo on failure

• Use a visited: Vec<bool> array to track which vertices are in the current path

• Understand why backtracking is still exponential worst-case but practical for small graphs

• Apply pruning heuristics: Warnsdorff's rule for knight's tour

• See why Hamiltonian is NP-complete while Eulerian is polynomial

Code Example

#![allow(clippy::all)]
//! # Hamiltonian Path (Backtracking)
pub fn hamiltonian_path(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![vec![false; n]; n];
    for &(u, v) in edges {
        adj[u][v] = true;
        adj[v][u] = true;
    }
    let mut path = vec![0];
    let mut visited = vec![false; n];
    visited[0] = true;
    fn backtrack(n: usize, adj: &[Vec<bool>], path: &mut Vec<usize>, vis: &mut [bool]) -> bool {
        if path.len() == n {
            return true;
        }
        let last = *path.last().unwrap();
        for next in 0..n {
            if !vis[next] && adj[last][next] {
                vis[next] = true;
                path.push(next);
                if backtrack(n, adj, path, vis) {
                    return true;
                }
                path.pop();
                vis[next] = false;
            }
        }
        false
    }
    if backtrack(n, &adj, &mut path, &mut visited) {
        Some(path)
    } else {
        None
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ham() {
        let p = hamiltonian_path(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (1, 3), (0, 2)]);
        assert!(p.is_some());
    }
}

(* Hamiltonian Cycle — backtracking O(n!) worst case *)

let hamiltonian_cycle adj n =
  let path    = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0)    <- 0;
  visited.(0) <- true;

  let rec backtrack pos =
    if pos = n then
      (* Check if last vertex connects to start *)
      List.mem 0 adj.(path.(n-1))
    else
      List.exists (fun v ->
        if not visited.(v) && List.mem v adj.(path.(pos-1)) then begin
          path.(pos)    <- v;
          visited.(v)   <- true;
          let result = backtrack (pos + 1) in
          if not result then begin
            path.(pos)  <- -1;
            visited.(v) <- false
          end;
          result
        end else false
      ) (List.init n (fun i -> i))
  in
  if backtrack 1 then
    Some (Array.to_list path @ [0])
  else
    None

let () =
  (* Petersen graph — known to have Hamiltonian cycle *)
  let n   = 5 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 3; add 3 4; add 4 0;  (* outer 5-cycle *)
  (match hamiltonian_cycle adj n with
   | None   -> Printf.printf "No Hamiltonian cycle\n"
   | Some p -> Printf.printf "Hamiltonian cycle: [%s]\n"
       (String.concat " -> " (List.map string_of_int p)));

  (* Complete graph K4 *)
  let n2  = 4 in
  let adj2 = Array.make n2 [] in
  for u = 0 to n2-1 do
    for v = 0 to n2-1 do
      if u <> v then adj2.(u) <- v :: adj2.(u)
    done
  done;
  (match hamiltonian_cycle adj2 n2 with
   | None   -> Printf.printf "No Hamiltonian cycle in K4\n"
   | Some p -> Printf.printf "K4 Hamiltonian cycle: [%s]\n"
       (String.concat " -> " (List.map string_of_int p)))

Key Differences

Backtracking style: Rust's mutable path and visited with explicit push/pop is imperative; OCaml's recursive approach with immutable lists is more idiomatic but allocates more.

Early termination: Rust returns true immediately on finding a path; OCaml uses exceptions or Option for early return through the recursion stack.

NP-completeness: Both languages face the same exponential worst case; pruning heuristics matter more than language choice.

Knight's tour: The knight's tour (finding a Hamiltonian path on a chessboard for a knight) is solvable in O(n²) using Warnsdorff's heuristic — a practical exception to the NP-hardness.

OCaml Approach

OCaml implements backtracking with let rec backtrack path vis = .... OCaml's recursive style makes backtracking natural: if success then Some path else List.fold_left try_next None neighbors. The exception Found of int list pattern enables early termination when a path is found. Heuristics like Warnsdorff's rule (choose vertex with fewest onward moves first) dramatically speed up knight's tour solutions.

Full Source

#![allow(clippy::all)]
//! # Hamiltonian Path (Backtracking)
pub fn hamiltonian_path(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![vec![false; n]; n];
    for &(u, v) in edges {
        adj[u][v] = true;
        adj[v][u] = true;
    }
    let mut path = vec![0];
    let mut visited = vec![false; n];
    visited[0] = true;
    fn backtrack(n: usize, adj: &[Vec<bool>], path: &mut Vec<usize>, vis: &mut [bool]) -> bool {
        if path.len() == n {
            return true;
        }
        let last = *path.last().unwrap();
        for next in 0..n {
            if !vis[next] && adj[last][next] {
                vis[next] = true;
                path.push(next);
                if backtrack(n, adj, path, vis) {
                    return true;
                }
                path.pop();
                vis[next] = false;
            }
        }
        false
    }
    if backtrack(n, &adj, &mut path, &mut visited) {
        Some(path)
    } else {
        None
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ham() {
        let p = hamiltonian_path(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (1, 3), (0, 2)]);
        assert!(p.is_some());
    }
}

(* Hamiltonian Cycle — backtracking O(n!) worst case *)

let hamiltonian_cycle adj n =
  let path    = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0)    <- 0;
  visited.(0) <- true;

  let rec backtrack pos =
    if pos = n then
      (* Check if last vertex connects to start *)
      List.mem 0 adj.(path.(n-1))
    else
      List.exists (fun v ->
        if not visited.(v) && List.mem v adj.(path.(pos-1)) then begin
          path.(pos)    <- v;
          visited.(v)   <- true;
          let result = backtrack (pos + 1) in
          if not result then begin
            path.(pos)  <- -1;
            visited.(v) <- false
          end;
          result
        end else false
      ) (List.init n (fun i -> i))
  in
  if backtrack 1 then
    Some (Array.to_list path @ [0])
  else
    None

let () =
  (* Petersen graph — known to have Hamiltonian cycle *)
  let n   = 5 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 3; add 3 4; add 4 0;  (* outer 5-cycle *)
  (match hamiltonian_cycle adj n with
   | None   -> Printf.printf "No Hamiltonian cycle\n"
   | Some p -> Printf.printf "Hamiltonian cycle: [%s]\n"
       (String.concat " -> " (List.map string_of_int p)));

  (* Complete graph K4 *)
  let n2  = 4 in
  let adj2 = Array.make n2 [] in
  for u = 0 to n2-1 do
    for v = 0 to n2-1 do
      if u <> v then adj2.(u) <- v :: adj2.(u)
    done
  done;
  (match hamiltonian_cycle adj2 n2 with
   | None   -> Printf.printf "No Hamiltonian cycle in K4\n"
   | Some p -> Printf.printf "K4 Hamiltonian cycle: [%s]\n"
       (String.concat " -> " (List.map string_of_int p)))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ham() {
        let p = hamiltonian_path(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (1, 3), (0, 2)]);
        assert!(p.is_some());
    }
}

Deep Comparison

OCaml vs Rust: Hamiltonian Backtrack

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 Warnsdorff's heuristic for the knight's tour: always move to the square with the fewest onward moves. Verify it solves 8×8 chessboard instantly.

Add pruning: if any unvisited vertex has 0 remaining unvisited neighbors before the path is complete, immediately backtrack.

Implement the Hamiltonian cycle variant (returns to start) by adding a check at path.len() == n that adj[last][start] is true.

Open Source Repos

functional-rust

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

Rust