1063: Sudoku Solver

Difficulty: Advanced Category: Backtracking Concept: Solve a 9×9 Sudoku puzzle using backtracking with constraint propagation Key Insight: Pre-computing constraint sets (which numbers are used in each row, column, and 3×3 box) reduces the validation from O(27) per check to O(1), dramatically speeding up the backtracking.

// 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)
}

fn main() {
    let mut 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],
    ];
    solve_sudoku(&mut board);
    for row in &board {
        println!("{:?}", row);
    }
}

#[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"

📊 Detailed 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`