37. Sudoku Solver

using System;
public class Solution {
    int n = 3;
    int N;
    int[][] rows, columns, boxes;
    char[][] board;
    bool sudokuSolved = false;
    public Solution() {
        N = n * n;
        rows = new int[N][];
        columns = new int[N][];
        boxes = new int[N][];
        for (int i = 0; i < N; i++) {
            rows[i] = new int[N + 1];
            columns[i] = new int[N + 1];
            boxes[i] = new int[N + 1];
        }
    }
    private bool CouldPlace(int d, int row, int col) {
        int idx = (row / n) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }
    private void PlaceOrRemove(int d, int row, int col, bool place) {
        int idx = (row / n) * n + col / n;
        int delta = place ? 1 : -1;
        rows[row][d] += delta;
        columns[col][d] += delta;
        boxes[idx][d] += delta;
        board[row][col] = place ? (char)(d + '0') : '.';
    }
    private void Backtrack(int row = 0, int col = 0) {
        if (col == N) { col = 0; row++; }
        if (row == N) { sudokuSolved = true; return; }
        if (board[row][col] == '.') {
            for (int d = 1; d <= 9; d++) {
                if (CouldPlace(d, row, col)) {
                    PlaceOrRemove(d, row, col, true);
                    Backtrack(row, col + 1);
                    if (!sudokuSolved) PlaceOrRemove(d, row, col, false);
                }
            }
        } else {
            Backtrack(row, col + 1);
        }
    }
    public void SolveSudoku(char[][] inputBoard) {
        board = inputBoard;
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++)
            if (board[r][c] != '.') PlaceOrRemove((int)char.GetNumericValue(board[r][c]), r, c, true);
        Backtrack();
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    int n = 3;
    int N;
    int[][] rows, columns, boxes;
    char[][] board;
    bool sudokuSolved = false;
    public Solution() {
        N = n * n;
        rows = new int[N][];
        columns = new int[N][];
        boxes = new int[N][];
        for (int i = 0; i < N; i++) {
            rows[i] = new int[N + 1];
            columns[i] = new int[N + 1];
            boxes[i] = new int[N + 1];
        }
    }
    private bool CouldPlace(int d, int row, int col) {
        int idx = (row / n) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }
    private void PlaceOrRemove(int d, int row, int col, bool place) {
        int idx = (row / n) * n + col / n;
        int delta = place ? 1 : -1;
        rows[row][d] += delta;
        columns[col][d] += delta;
        boxes[idx][d] += delta;
        board[row][col] = place ? (char)(d + '0') : '.';
    }
    private void Backtrack(int row = 0, int col = 0) {
        if (col == N) { col = 0; row++; }
        if (row == N) { sudokuSolved = true; return; }
        if (board[row][col] == '.') {
            for (int d = 1; d <= 9; d++) {
                if (CouldPlace(d, row, col)) {
                    PlaceOrRemove(d, row, col, true);
                    Backtrack(row, col + 1);
                    if (!sudokuSolved) PlaceOrRemove(d, row, col, false);
                }
            }
        } else {
            Backtrack(row, col + 1);
        }
    }
    public void SolveSudoku(char[][] inputBoard) {
        board = inputBoard;
        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++)
            if (board[r][c] != '.') PlaceOrRemove((int)char.GetNumericValue(board[r][c]), r, c, true);
        Backtrack();
    }
}

import java.util.*;

class Solution {
    public void solveSudoku(char[][] board) {
        int n = 3, N = n * n;
        List<Map<Character, Integer>> track = new ArrayList<>(N * 3);
        for (int i = 0; i < N * 3; i++) track.add(new HashMap<>());

        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) 
            if (board[r][c] != '.') update(board, r, c, board[r][c], true, n, track);

        backtrack(board, 0, 0, n, N, track);
    }

    private boolean backtrack(char[][] board, int r, int c, int n, int N, List<Map<Character, Integer>> track) {
        if (c == N) { r++; c = 0; }
        if (r == N) return true;

        if (board[r][c] != '.') return backtrack(board, r, c + 1, n, N, track);

        for (char num = '1'; num <= '9'; num++) 
            if (canPlace(num, r, c, n, track)) {
                update(board, r, c, num, true, n, track);
                if (backtrack(board, r, c + 1, n, N, track)) return true;
                update(board, r, c, num, false, n, track);
            }

        return false;
    }

    private boolean canPlace(char num, int r, int c, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n;
        return track.get(r).getOrDefault(num, 0) == 0 && track.get(n + c).getOrDefault(num, 0) == 0 
            && track.get(2 * n + idx).getOrDefault(num, 0) == 0;
    }

    private void update(char[][] board, int r, int c, char num, boolean place, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n, delta = place ? 1 : -1;
        track.get(r).put(num, track.get(r).getOrDefault(num, 0) + delta);
        track.get(n + c).put(num, track.get(n + c).getOrDefault(num, 0) + delta);
        track.get(2 * n + idx).put(num, track.get(2 * n + idx).getOrDefault(num, 0) + delta);
        board[r][c] = place ? num : '.';
    }
}

from collections import defaultdict

class Solution:
    def solveSudoku(self, board):
        n = 3
        N = n * n
        rows, cols, boxes = [defaultdict(int) for _ in range(N)], [defaultdict(int) for _ in range(N)], [defaultdict(int) for _ in range(N)]

        def place_or_remove(d, r, c, add=True):
            idx = (r // n) * n + (c // n)
            rows[r][d] = rows[r].get(d, 0) + (1 if add else -1)
            cols[c][d] = cols[c].get(d, 0) + (1 if add else -1)
            boxes[idx][d] = boxes[idx].get(d, 0) + (1 if add else -1)
            board[r][c] = str(d) if add else '.'
            if rows[r][d] == 0: del rows[r][d]
            if cols[c][d] == 0: del cols[c][d]
            if boxes[idx][d] == 0: del boxes[idx][d]

        def can_place(d, r, c):
            idx = (r // n) * n + (c // n)
            return not (d in rows[r] or d in cols[c] or d in boxes[idx])

        def backtrack(r=0, c=0):
            if c == N:
                r, c = r + 1, 0
            if r == N:
                return True
            if board[r][c] == '.':
                for d in map(str, range(1, 10)):
                    if can_place(d, r, c):
                        place_or_remove(d, r, c, True)
                        if backtrack(r, c + 1):
                            return True
                        place_or_remove(d, r, c, False)
            else:
                return backtrack(r, c + 1)
            return False

        for r in range(N):
            for c in range(N):
                if board[r][c] != '.':
                    place_or_remove(board[r][c], r, c, True)

        backtrack()

type Solution struct {
    n, N int
    rows, columns, boxes [][]int
    board [][]byte
}

func Constructor() Solution {
    n, N := 3, 9
    rows, columns, boxes := make([][]int, N), make([][]int, N), make([][]int, N)
    for i := 0; i < N; i++ {
        rows[i], columns[i], boxes[i] = make([]int, N+1), make([]int, N+1), make([]int, N+1)
    }
    return Solution{n: n, N: N, rows: rows, columns: columns, boxes: boxes}
}

func (s *Solution) couldPlace(d, row, col int) bool {
    idx := (row / s.n) * s.n + col / s.n
    return s.rows[row][d]+s.columns[col][d]+s.boxes[idx][d] == 0
}

func (s *Solution) placeOrRemove(d, row, col int, place bool) {
    idx := (row / s.n) * s.n + col / s.n
    delta := 1
    if !place {
        delta = -1
        s.board[row][col] = '.'
    } else {
        s.board[row][col] = byte(d) + '0'
    }
    s.rows[row][d] += delta
    s.columns[col][d] += delta
    s.boxes[idx][d] += delta
}

func (s *Solution) backTrack(row, col int) bool {
    if col == s.N {
        col, row = 0, row+1
    }
    if row == s.N {
        return true
    }
    if s.board[row][col] != '.' {
        return s.backTrack(row, col+1)
    }
    for d := 1; d <= 9; d++ {
        if s.couldPlace(d, row, col) {
            s.placeOrRemove(d, row, col, true)
            if s.backTrack(row, col+1) {
                return true
            }
            s.placeOrRemove(d, row, col, false)
        }
    }
    return false
}

func solveSudoku(board [][]byte) {
    s := Constructor()
    s.board = board
    for r := 0; r < s.N; r++ {
        for c := 0; c < s.N; c++ {
            if board[r][c] != '.' {
                d := int(board[r][c] - '0')
                s.placeOrRemove(d, r, c, true)
            }
        }
    }
    s.backTrack(0, 0)
}

Explanation