Sudoku solver

Array Hash Table Backtracking Matrix

65.4% acceptance

Feb 27, 2026

11021

341

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
    let mut rows = vec![0u16; 9];
    let mut cols = vec![0u16; 9];
    let mut boxes = vec![0u16; 9];
    
    // Initialize bitmasks with existing numbers
    for i in 0..9 {
      for j in 0..9 {
        if board[i][j] != '.' {
          let digit = (board[i][j] as u8 - b'0') as usize;
          let bit = 1 << digit;
          rows[i] |= bit;
          cols[j] |= bit;
          boxes[(i / 3) * 3 + (j / 3)] |= bit;
        }
      }
    }
    
    Self::sudoku_solve(board, &mut rows, &mut cols, &mut boxes);
  }

  fn sudoku_solve(
    board: &mut Vec<Vec<char>>,
    rows: &mut Vec<u16>,
    cols: &mut Vec<u16>,
    boxes: &mut Vec<u16>,
  ) -> bool {
    for i in 0..9 {
      for j in 0..9 {
        if board[i][j] == '.' {
          let box_idx = (i / 3) * 3 + (j / 3);
          let used = rows[i] | cols[j] | boxes[box_idx];
          let available = !used & 0b1111111110u16; // bits 1-9

          for digit in 1u16..=9 {
            let bit = 1u16 << digit;
            if available & bit != 0 {
              board[i][j] = (b'0' + digit as u8) as char;
              rows[i] |= bit;
              cols[j] |= bit;
              boxes[box_idx] |= bit;

              if Self::sudoku_solve(board, rows, cols, boxes) {
                return true;
              }

              board[i][j] = '.';
              rows[i] ^= bit;
              cols[j] ^= bit;
              boxes[box_idx] ^= bit;
            }
          }

          return false; // no valid digit for this cell
        }
      }
    }

    true // all cells filled
  }
}