# 37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

# Solution

Approach 1: Iteration.

# Code (Python)

Approach 1:

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        unfilled = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    unfilled.append((i, j))
                rows[i].add(board[i][j])
                cols[j].add(board[i][j])
                boxes[(i//3) * 3 + j//3].add(board[i][j])
        self._fill(0, unfilled, rows, cols, boxes, board)
        
    def _fill(self, index, unfilled, rows, cols, boxes, board):
        if index >= len(unfilled):
            return True
        x, y = unfilled[index]
        for num in '123456789':
            board[x][y] = num
            if (num in rows[x]) or (num in cols[y]) or (num in boxes[(x//3) * 3 + y//3]):
                    continue
            rows[x].add(num)
            cols[y].add(num)
            boxes[(x//3) * 3 + y//3].add(num)
            if self._fill(index + 1, unfilled, rows, cols, boxes, board):
                return True
            board[x][y] = '.'
            rows[x].remove(num)
            cols[y].remove(num)
            boxes[(x//3) * 3 + y//3].remove(num)
        return False

# Code (C++)

Approach 1:

class Solution {
private:
    bool usedRow[9][9], usedCol[9][9], usedBox[9][9];
    bool doSolveSudoku(vector<vector<char>>& board, int row) {
        for (int i = row; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k <= 9; ++k) {
                        if (!usedRow[i][k-1] && !usedCol[j][k-1] &&
                            !usedBox[i/3*3+j/3][k-1])
                        {
                            board[i][j] = '0' + k;
                            usedRow[i][k-1] = true;
                            usedCol[j][k-1] = true;
                            usedBox[i/3*3+j/3][k-1] = true;
                            if (doSolveSudoku(board, i))
                                return true;
                            board[i][j] = '.';
                            usedRow[i][k-1] = false;
                            usedCol[j][k-1] = false;
                            usedBox[i/3*3+j/3][k-1] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                usedRow[i][j] = false;
                usedCol[i][j] = false;
                usedBox[i][j] = false;
            }
        }
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    int val = board[i][j] - '0';
                    usedRow[i][val-1] = true;
                    usedCol[j][val-1] = true;
                    usedBox[i/3*3+j/3][val-1] = true;
                }
            }
        }
        doSolveSudoku(board, 0);
    }
};