1063 Advanced

1063-sudoku-solver — Sudoku Solver

Functional Programming

Tutorial

The Problem

Sudoku is a constraint satisfaction problem: fill a 9×9 grid with digits 1–9 such that each row, column, and 3×3 box contains each digit exactly once. Backtracking with constraint checking is the standard algorithm — try each valid digit at each empty cell, backtrack when no digit works.

Sudoku solvers appear in puzzle generation systems, benchmarks for SAT solvers, and as interview problems testing backtracking proficiency. Peter Norvig's famous Python solver showed that constraint propagation (reducing possibilities without backtracking) handles most real puzzles without any backtracking.

🎯 Learning Outcomes

• Implement Sudoku solving using backtracking with row/column/box constraints

• Use a is_valid predicate that checks all three constraint types

• Understand the search tree and why most puzzles solve quickly

• Optimize constraint checking using bitmasks

• Connect to arc consistency in constraint satisfaction problems

Code Example

#![allow(clippy::all)]
// 1063: Sudoku Solver — Backtracking + Constraints

// Approach 1: Simple backtracking
fn solve_sudoku(board: &mut [[u8; 9]; 9]) -> bool {
    fn is_valid(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool {
        for i in 0..9 {
            if board[row][i] == num || board[i][col] == num {
                return false;
            }
        }
        let (br, bc) = ((row / 3) * 3, (col / 3) * 3);
        for r in br..br + 3 {
            for c in bc..bc + 3 {
                if board[r][c] == num {
                    return false;
                }
            }
        }
        true
    }

    fn solve(board: &mut [[u8; 9]; 9]) -> bool {
        for r in 0..9 {
            for c in 0..9 {
                if board[r][c] == 0 {
                    for num in 1..=9 {
                        if is_valid(board, r, c, num) {
                            board[r][c] = num;
                            if solve(board) {
                                return true;
                            }
                            board[r][c] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        true
    }

    solve(board)
}

// Approach 2: With constraint arrays for O(1) validation
fn solve_sudoku_fast(board: &mut [[u8; 9]; 9]) -> bool {
    let mut rows = [[false; 10]; 9];
    let mut cols = [[false; 10]; 9];
    let mut boxes = [[false; 10]; 9];

    for r in 0..9 {
        for c in 0..9 {
            let v = board[r][c] as usize;
            if v != 0 {
                rows[r][v] = true;
                cols[c][v] = true;
                boxes[(r / 3) * 3 + c / 3][v] = true;
            }
        }
    }

    fn solve(
        board: &mut [[u8; 9]; 9],
        rows: &mut [[bool; 10]; 9],
        cols: &mut [[bool; 10]; 9],
        boxes: &mut [[bool; 10]; 9],
    ) -> bool {
        for r in 0..9 {
            for c in 0..9 {
                if board[r][c] == 0 {
                    let b = (r / 3) * 3 + c / 3;
                    for num in 1..=9usize {
                        if !rows[r][num] && !cols[c][num] && !boxes[b][num] {
                            board[r][c] = num as u8;
                            rows[r][num] = true;
                            cols[c][num] = true;
                            boxes[b][num] = true;
                            if solve(board, rows, cols, boxes) {
                                return true;
                            }
                            board[r][c] = 0;
                            rows[r][num] = false;
                            cols[c][num] = false;
                            boxes[b][num] = false;
                        }
                    }
                    return false;
                }
            }
        }
        true
    }

    solve(board, &mut rows, &mut cols, &mut boxes)
}

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

    fn test_board() -> [[u8; 9]; 9] {
        [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ]
    }

    #[test]
    fn test_sudoku_simple() {
        let mut board = test_board();
        assert!(solve_sudoku(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }

    #[test]
    fn test_sudoku_fast() {
        let mut board = test_board();
        assert!(solve_sudoku_fast(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }
}

(* 1063: Sudoku Solver — Backtracking + Constraints *)

(* Approach 1: Simple backtracking *)
let solve_sudoku board =
  let is_valid board row col num =
    (* Check row *)
    let valid = ref true in
    for c = 0 to 8 do
      if board.(row).(c) = num then valid := false
    done;
    (* Check column *)
    for r = 0 to 8 do
      if board.(r).(col) = num then valid := false
    done;
    (* Check 3x3 box *)
    let br = (row / 3) * 3 and bc = (col / 3) * 3 in
    for r = br to br + 2 do
      for c = bc to bc + 2 do
        if board.(r).(c) = num then valid := false
      done
    done;
    !valid
  in
  let rec solve () =
    (* Find first empty cell *)
    let found = ref None in
    for r = 0 to 8 do
      for c = 0 to 8 do
        if board.(r).(c) = 0 && !found = None then
          found := Some (r, c)
      done
    done;
    match !found with
    | None -> true  (* All filled — solved! *)
    | Some (row, col) ->
      let solved = ref false in
      for num = 1 to 9 do
        if not !solved && is_valid board row col num then begin
          board.(row).(col) <- num;
          if solve () then solved := true
          else board.(row).(col) <- 0
        end
      done;
      !solved
  in
  solve ()

(* Approach 2: With constraint sets for faster validation *)
let solve_sudoku_fast board =
  let rows = Array.init 9 (fun _ -> Array.make 10 false) in
  let cols = Array.init 9 (fun _ -> Array.make 10 false) in
  let boxes = Array.init 9 (fun _ -> Array.make 10 false) in
  (* Initialize constraints *)
  for r = 0 to 8 do
    for c = 0 to 8 do
      let v = board.(r).(c) in
      if v <> 0 then begin
        rows.(r).(v) <- true;
        cols.(c).(v) <- true;
        boxes.((r / 3) * 3 + c / 3).(v) <- true
      end
    done
  done;
  let rec solve () =
    let found = ref None in
    for r = 0 to 8 do
      for c = 0 to 8 do
        if board.(r).(c) = 0 && !found = None then found := Some (r, c)
      done
    done;
    match !found with
    | None -> true
    | Some (r, c) ->
      let b = (r / 3) * 3 + c / 3 in
      let solved = ref false in
      for num = 1 to 9 do
        if not !solved && not rows.(r).(num) && not cols.(c).(num) && not boxes.(b).(num) then begin
          board.(r).(c) <- num;
          rows.(r).(num) <- true;
          cols.(c).(num) <- true;
          boxes.(b).(num) <- true;
          if solve () then solved := true
          else begin
            board.(r).(c) <- 0;
            rows.(r).(num) <- false;
            cols.(c).(num) <- false;
            boxes.(b).(num) <- false
          end
        end
      done;
      !solved
  in
  solve ()

let () =
  let board = [|
    [|5;3;0;0;7;0;0;0;0|];
    [|6;0;0;1;9;5;0;0;0|];
    [|0;9;8;0;0;0;0;6;0|];
    [|8;0;0;0;6;0;0;0;3|];
    [|4;0;0;8;0;3;0;0;1|];
    [|7;0;0;0;2;0;0;0;6|];
    [|0;6;0;0;0;0;2;8;0|];
    [|0;0;0;4;1;9;0;0;5|];
    [|0;0;0;0;8;0;0;7;9|]
  |] in
  assert (solve_sudoku board);
  assert (board.(0).(2) = 4);
  assert (board.(4).(4) = 5);

  let board2 = [|
    [|5;3;0;0;7;0;0;0;0|];
    [|6;0;0;1;9;5;0;0;0|];
    [|0;9;8;0;0;0;0;6;0|];
    [|8;0;0;0;6;0;0;0;3|];
    [|4;0;0;8;0;3;0;0;1|];
    [|7;0;0;0;2;0;0;0;6|];
    [|0;6;0;0;0;0;2;8;0|];
    [|0;0;0;4;1;9;0;0;5|];
    [|0;0;0;0;8;0;0;7;9|]
  |] in
  assert (solve_sudoku_fast board2);
  assert (board2.(0).(2) = 4);

  Printf.printf "✓ All tests passed\n"

Key Differences

Mutable 2D array: Rust uses &mut [[u8; 9]; 9]; OCaml uses int array array — both support direct index assignment.

Early termination: Both return bool to signal success/failure; Rust's return true/false is explicit while OCaml uses the last expression.

Bitmask optimization: Both can use three arrays of u16 (bit per digit) for O(1) constraint checks; the bitmask logic is identical.

Constraint propagation: Norvig's algorithm extends this with naked pairs/triples elimination — available in both languages with similar code complexity.

OCaml Approach

let solve board =
  let is_valid r c num =
    let rec check i =
      if i = 9 then true
      else if board.(r).(i) = num || board.(i).(c) = num then false
      else check (i + 1)
    in
    let br, bc = (r/3)*3, (c/3)*3 in
    check 0 && (* also check 3x3 box *)
    let rec check_box i =
      if i = 9 then true
      else if board.(br + i/3).(bc + i mod 3) = num then false
      else check_box (i + 1)
    in check_box 0
  in
  (* ... backtracking solve *)

The logic is identical. OCaml's board.(r).(c) vs Rust's board[r][c] is the main syntactic difference.

Full Source

#![allow(clippy::all)]
// 1063: Sudoku Solver — Backtracking + Constraints

// Approach 1: Simple backtracking
fn solve_sudoku(board: &mut [[u8; 9]; 9]) -> bool {
    fn is_valid(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool {
        for i in 0..9 {
            if board[row][i] == num || board[i][col] == num {
                return false;
            }
        }
        let (br, bc) = ((row / 3) * 3, (col / 3) * 3);
        for r in br..br + 3 {
            for c in bc..bc + 3 {
                if board[r][c] == num {
                    return false;
                }
            }
        }
        true
    }

    fn solve(board: &mut [[u8; 9]; 9]) -> bool {
        for r in 0..9 {
            for c in 0..9 {
                if board[r][c] == 0 {
                    for num in 1..=9 {
                        if is_valid(board, r, c, num) {
                            board[r][c] = num;
                            if solve(board) {
                                return true;
                            }
                            board[r][c] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        true
    }

    solve(board)
}

// Approach 2: With constraint arrays for O(1) validation
fn solve_sudoku_fast(board: &mut [[u8; 9]; 9]) -> bool {
    let mut rows = [[false; 10]; 9];
    let mut cols = [[false; 10]; 9];
    let mut boxes = [[false; 10]; 9];

    for r in 0..9 {
        for c in 0..9 {
            let v = board[r][c] as usize;
            if v != 0 {
                rows[r][v] = true;
                cols[c][v] = true;
                boxes[(r / 3) * 3 + c / 3][v] = true;
            }
        }
    }

    fn solve(
        board: &mut [[u8; 9]; 9],
        rows: &mut [[bool; 10]; 9],
        cols: &mut [[bool; 10]; 9],
        boxes: &mut [[bool; 10]; 9],
    ) -> bool {
        for r in 0..9 {
            for c in 0..9 {
                if board[r][c] == 0 {
                    let b = (r / 3) * 3 + c / 3;
                    for num in 1..=9usize {
                        if !rows[r][num] && !cols[c][num] && !boxes[b][num] {
                            board[r][c] = num as u8;
                            rows[r][num] = true;
                            cols[c][num] = true;
                            boxes[b][num] = true;
                            if solve(board, rows, cols, boxes) {
                                return true;
                            }
                            board[r][c] = 0;
                            rows[r][num] = false;
                            cols[c][num] = false;
                            boxes[b][num] = false;
                        }
                    }
                    return false;
                }
            }
        }
        true
    }

    solve(board, &mut rows, &mut cols, &mut boxes)
}

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

    fn test_board() -> [[u8; 9]; 9] {
        [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ]
    }

    #[test]
    fn test_sudoku_simple() {
        let mut board = test_board();
        assert!(solve_sudoku(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }

    #[test]
    fn test_sudoku_fast() {
        let mut board = test_board();
        assert!(solve_sudoku_fast(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }
}

(* 1063: Sudoku Solver — Backtracking + Constraints *)

(* Approach 1: Simple backtracking *)
let solve_sudoku board =
  let is_valid board row col num =
    (* Check row *)
    let valid = ref true in
    for c = 0 to 8 do
      if board.(row).(c) = num then valid := false
    done;
    (* Check column *)
    for r = 0 to 8 do
      if board.(r).(col) = num then valid := false
    done;
    (* Check 3x3 box *)
    let br = (row / 3) * 3 and bc = (col / 3) * 3 in
    for r = br to br + 2 do
      for c = bc to bc + 2 do
        if board.(r).(c) = num then valid := false
      done
    done;
    !valid
  in
  let rec solve () =
    (* Find first empty cell *)
    let found = ref None in
    for r = 0 to 8 do
      for c = 0 to 8 do
        if board.(r).(c) = 0 && !found = None then
          found := Some (r, c)
      done
    done;
    match !found with
    | None -> true  (* All filled — solved! *)
    | Some (row, col) ->
      let solved = ref false in
      for num = 1 to 9 do
        if not !solved && is_valid board row col num then begin
          board.(row).(col) <- num;
          if solve () then solved := true
          else board.(row).(col) <- 0
        end
      done;
      !solved
  in
  solve ()

(* Approach 2: With constraint sets for faster validation *)
let solve_sudoku_fast board =
  let rows = Array.init 9 (fun _ -> Array.make 10 false) in
  let cols = Array.init 9 (fun _ -> Array.make 10 false) in
  let boxes = Array.init 9 (fun _ -> Array.make 10 false) in
  (* Initialize constraints *)
  for r = 0 to 8 do
    for c = 0 to 8 do
      let v = board.(r).(c) in
      if v <> 0 then begin
        rows.(r).(v) <- true;
        cols.(c).(v) <- true;
        boxes.((r / 3) * 3 + c / 3).(v) <- true
      end
    done
  done;
  let rec solve () =
    let found = ref None in
    for r = 0 to 8 do
      for c = 0 to 8 do
        if board.(r).(c) = 0 && !found = None then found := Some (r, c)
      done
    done;
    match !found with
    | None -> true
    | Some (r, c) ->
      let b = (r / 3) * 3 + c / 3 in
      let solved = ref false in
      for num = 1 to 9 do
        if not !solved && not rows.(r).(num) && not cols.(c).(num) && not boxes.(b).(num) then begin
          board.(r).(c) <- num;
          rows.(r).(num) <- true;
          cols.(c).(num) <- true;
          boxes.(b).(num) <- true;
          if solve () then solved := true
          else begin
            board.(r).(c) <- 0;
            rows.(r).(num) <- false;
            cols.(c).(num) <- false;
            boxes.(b).(num) <- false
          end
        end
      done;
      !solved
  in
  solve ()

let () =
  let board = [|
    [|5;3;0;0;7;0;0;0;0|];
    [|6;0;0;1;9;5;0;0;0|];
    [|0;9;8;0;0;0;0;6;0|];
    [|8;0;0;0;6;0;0;0;3|];
    [|4;0;0;8;0;3;0;0;1|];
    [|7;0;0;0;2;0;0;0;6|];
    [|0;6;0;0;0;0;2;8;0|];
    [|0;0;0;4;1;9;0;0;5|];
    [|0;0;0;0;8;0;0;7;9|]
  |] in
  assert (solve_sudoku board);
  assert (board.(0).(2) = 4);
  assert (board.(4).(4) = 5);

  let board2 = [|
    [|5;3;0;0;7;0;0;0;0|];
    [|6;0;0;1;9;5;0;0;0|];
    [|0;9;8;0;0;0;0;6;0|];
    [|8;0;0;0;6;0;0;0;3|];
    [|4;0;0;8;0;3;0;0;1|];
    [|7;0;0;0;2;0;0;0;6|];
    [|0;6;0;0;0;0;2;8;0|];
    [|0;0;0;4;1;9;0;0;5|];
    [|0;0;0;0;8;0;0;7;9|]
  |] in
  assert (solve_sudoku_fast board2);
  assert (board2.(0).(2) = 4);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    fn test_board() -> [[u8; 9]; 9] {
        [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ]
    }

    #[test]
    fn test_sudoku_simple() {
        let mut board = test_board();
        assert!(solve_sudoku(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }

    #[test]
    fn test_sudoku_fast() {
        let mut board = test_board();
        assert!(solve_sudoku_fast(&mut board));
        assert_eq!(board[0][2], 4);
        assert_eq!(board[4][4], 5);
    }
}

Deep Comparison

Sudoku Solver — Comparison

Core Insight

Sudoku is backtracking with three overlapping constraints (row, column, 3×3 box). Maintaining constraint arrays reduces validation to O(1) per candidate. Both languages use in-place mutation with undo on backtrack.

OCaml Approach

• 2D arrays with ref for found-cell tracking

• Nested for loops with ref flags for early exit simulation

• Array.init 9 (fun _ -> Array.make 10 false) for constraint arrays

• Box index: (r/3)*3 + c/3

Rust Approach

• Fixed-size arrays [[u8; 9]; 9] — stack-allocated, cache-friendly

• Nested for loops with early return false — cleaner control flow

• [[bool; 10]; 9] constraint arrays — also stack-allocated

• Inner fn with explicit mutable references

Comparison Table

Aspect	OCaml	Rust
Board type	`int array array` (heap)	`[[u8; 9]; 9]` (stack)
Constraint arrays	`bool array array`	`[[bool; 10]; 9]` (fixed)
Empty cell search	`ref None` + iteration	Nested `for` with early `return`
Backtrack	`board.(r).(c) <- 0`	`board[r][c] = 0`
Early exit	`ref` flag + `not !solved` check	`return false` / `return true`

Exercises

Add bitmask optimization: use row_mask: [u16; 9], col_mask: [u16; 9], box_mask: [u16; 9] to replace the O(9) validity checks with O(1) bit operations.

Implement a Sudoku generator that creates valid puzzles by solving from scratch and then removing cells while maintaining uniqueness.

Count the total number of valid solutions for a given puzzle (most puzzles should have exactly one).

Open Source Repos

functional-rust

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

Rust