# 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:
- Each of the digits 1-9 must occur exactly once in each row.
- Each of the digits 1-9 must occur exactly once in each column.
- 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);
}
};