Sudoku Solver

hard array backtracking matrix

Problem

Fill in the empty cells of a 9×9 Sudoku grid so every row, column, and 3×3 sub-box contains digits 1–9 exactly once.

Inputpartially filled 9×9 board with '.' for blanks

Outputthe same board, fully filled

Maintain row/col/box bitmasks (or sets) of used digits to test placements in O(1).

board (81 chars, '.' = empty)

def solve_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.': empties.append((r, c))
            else:
                rows[r].add(v); cols[c].add(v); boxes[(r // 3) * 3 + c // 3].add(v)
    def dfs(k):
        if k == len(empties): return True
        r, c = empties[k]
        b = (r // 3) * 3 + c // 3
        for d in "123456789":
            if d in rows[r] or d in cols[c] or d in boxes[b]: continue
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            if dfs(k + 1): return True
            board[r][c] = '.'
            rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
        return False
    dfs(0)

function solveSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());
  const empties = [];
  for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) {
    const v = board[r][c];
    if (v === '.') empties.push([r, c]);
    else { rows[r].add(v); cols[c].add(v); boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)].add(v); }
  }
  function dfs(k) {
    if (k === empties.length) return true;
    const [r, c] = empties[k];
    const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    for (const d of "123456789") {
      if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) continue;
      board[r][c] = d; rows[r].add(d); cols[c].add(d); boxes[b].add(d);
      if (dfs(k + 1)) return true;
      board[r][c] = '.'; rows[r].delete(d); cols[c].delete(d); boxes[b].delete(d);
    }
    return false;
  }
  dfs(0);
}

class Solution {
    boolean[][] rows = new boolean[9][10], cols = new boolean[9][10], boxes = new boolean[9][10];
    char[][] board;
    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++)
            if (board[r][c] != '.') {
                int d = board[r][c] - '0';
                rows[r][d] = cols[c][d] = boxes[(r / 3) * 3 + c / 3][d] = true;
            }
        dfs(0);
    }
    private boolean dfs(int k) {
        if (k == 81) return true;
        int r = k / 9, c = k % 9;
        if (board[r][c] != '.') return dfs(k + 1);
        int b = (r / 3) * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            if (rows[r][d] || cols[c][d] || boxes[b][d]) continue;
            board[r][c] = (char)('0' + d);
            rows[r][d] = cols[c][d] = boxes[b][d] = true;
            if (dfs(k + 1)) return true;
            board[r][c] = '.';
            rows[r][d] = cols[c][d] = boxes[b][d] = false;
        }
        return false;
    }
}

class Solution {
    bool rows[9][10] = {}, cols[9][10] = {}, boxes[9][10] = {};
    bool dfs(vector<vector<char>>& b, int k) {
        if (k == 81) return true;
        int r = k / 9, c = k % 9;
        if (b[r][c] != '.') return dfs(b, k + 1);
        int bi = (r / 3) * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            if (rows[r][d] || cols[c][d] || boxes[bi][d]) continue;
            b[r][c] = '0' + d;
            rows[r][d] = cols[c][d] = boxes[bi][d] = true;
            if (dfs(b, k + 1)) return true;
            b[r][c] = '.';
            rows[r][d] = cols[c][d] = boxes[bi][d] = false;
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++)
            if (board[r][c] != '.') {
                int d = board[r][c] - '0';
                rows[r][d] = cols[c][d] = boxes[(r / 3) * 3 + c / 3][d] = true;
            }
        dfs(board, 0);
    }
};

Explanation

Solving Sudoku is a classic backtracking problem: fill empty cells one at a time, and whenever we get stuck, undo the last guess and try another digit.

To check placements instantly, we keep three groups of sets: one per row, one per column, and one per 3×3 box. The box index is computed as (r // 3) * 3 + c // 3. Before solving, we scan the board and record the digits already present in each set.

We also collect the coordinates of all blank cells into empties. The function dfs(k) handles the k-th blank: for each digit 1..9 it checks the row, column, and box sets — if the digit is free everywhere, it places it, updates the three sets, and recurses to the next blank.

If a placement leads to a dead end, we backtrack: reset the cell to '.' and remove the digit from all three sets, then try the next digit. When k reaches the number of blanks, every cell is filled and we return True.

For example, on a cell where the row already has a 5 and the box already has a 3, those digits are skipped; the solver tries the remaining candidates and recurses, locking in the unique fill that satisfies all three constraints.

Time: worst-case exponential; practical on full puzzles Space: O(81) recursion + O(9·9) bitmasks