## # 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))
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
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, usedCol, usedBox;
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);
}
};
``````