Sudoku Solver: Constraint Propagation + Backtracking

def solveSudoku(board):
    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch: return False
            if board[i][c] == ch: return False
            box_r = (r // 3) * 3 + i // 3
            box_c = (c // 3) * 3 + i % 3
            if board[box_r][box_c] == ch: return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for ch in '123456789':
                        if is_valid(r, c, ch):
                            board[r][c] = ch
                            if solve(): return True
                            board[r][c] = '.'
                    return False  # no valid digit
        return True  # all filled

    solve()

# Optimized: precompute valid sets with bitmasking
def solveSudokuFast(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []

    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                d = board[r][c]
                rows[r].add(d); cols[c].add(d); boxes[(r//3)*3+c//3].add(d)
            else:
                empty.append((r, c))

    def solve(idx):
        if idx == len(empty): return True
        r, c = empty[idx]
        b = (r // 3) * 3 + c // 3
        for d in '123456789':
            if d not in rows[r] and d not in cols[c] and d not in boxes[b]:
                board[r][c] = d
                rows[r].add(d); cols[c].add(d); boxes[b].add(d)
                if solve(idx + 1): return True
                board[r][c] = '.'
                rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)
        return False

    solve(0)

#include <bits/stdc++.h>
using namespace std;

void solveSudoku(vector<vector<char>>& board) {
    // Use bitmasks for O(1) validity check
    int rows[9]={}, cols[9]={}, boxes[9]={};

    auto idx = [](int r, int c) { return (r/3)*3 + c/3; };
    auto setBit = [&](int r, int c, char ch, bool set) {
        int bit = 1 << (ch - '1');
        if (set) { rows[r]|=bit; cols[c]|=bit; boxes[idx(r,c)]|=bit; }
        else { rows[r]&=~bit; cols[c]&=~bit; boxes[idx(r,c)]&=~bit; }
    };

    vector<pair<int,int>> empty;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') setBit(r, c, board[r][c], true);
            else empty.push_back({r, c});
        }

    function<bool(int)> solve = [&](int i) -> bool {
        if (i == (int)empty.size()) return true;
        auto [r, c] = empty[i];
        int used = rows[r] | cols[c] | boxes[idx(r, c)];
        for (int d = 1; d <= 9; d++) {
            if (used & (1 << (d-1))) continue;
            board[r][c] = '0' + d;
            setBit(r, c, board[r][c], true);
            if (solve(i + 1)) return true;
            setBit(r, c, board[r][c], false);
            board[r][c] = '.';
        }
        return false;
    };
    solve(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 empty = [];

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            if (board[r][c] !== '.') {
                const d = board[r][c];
                rows[r].add(d); cols[c].add(d); boxes[Math.floor(r/3)*3+Math.floor(c/3)].add(d);
            } else empty.push([r, c]);
        }
    }

    function solve(i) {
        if (i === empty.length) return true;
        const [r, c] = empty[i];
        const b = Math.floor(r/3)*3 + Math.floor(c/3);
        for (let d = 1; d <= 9; d++) {
            const s = String(d);
            if (rows[r].has(s) || cols[c].has(s) || boxes[b].has(s)) continue;
            board[r][c] = s;
            rows[r].add(s); cols[c].add(s); boxes[b].add(s);
            if (solve(i+1)) return true;
            board[r][c] = '.';
            rows[r].delete(s); cols[c].delete(s); boxes[b].delete(s);
        }
        return false;
    }
    solve(0);
}