## Algorithm

Problem Name: 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 digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

The `'.'` character indicates empty cells.

Example 1:

```Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

```

Constraints:

• `board.length == 9`
• `board[i].length == 9`
• `board[i][j]` is a digit or `'.'`.
• It is guaranteed that the input board has only one solution.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define IDX(I, J) ((I) / 3 * (boardColSize + 2) / 3 + (J) / 3)

int find_next_bit(int b, int k) {
k ++;
while (k  <  9 && (b & (1 << k))) {
k ++;
}
return k;
}

int dfs(char **board, int boardRowSize, int boardColSize, int *bits_on_row, int *bits_on_col, int *bits_on_square) {
int i, j, b, t, k;
char c;

for (i = 0; i  <  boardRowSize; i ++) {
for (j = 0; j  <  boardColSize; j ++) {
c = board[i][j];
if (c != '.') continue;

b = bits_on_row[i] |
bits_on_col[j] |
bits_on_square[IDX(i, j)];
k = -1;
while ((k = find_next_bit(b, k))  <  9) {
t = 1 << k;

board[i][j] = '1' + k;
bits_on_row[i] |= t;
bits_on_col[j] |= t;
bits_on_square[IDX(i, j)] |= t;

if (dfs(board, boardRowSize, boardColSize, bits_on_row, bits_on_col, bits_on_square)) return 1;

board[i][j] = '.';
bits_on_row[i] &= ~t;
bits_on_col[j] &= ~t;
bits_on_square[IDX(i, j)] &= ~t;
}

return 0;
}
}

return 1;
}

void solveSudoku(char** board, int boardRowSize, int boardColSize) {
int *buff, *bits_on_row, *bits_on_col, *bits_on_square;
int i, j, b;
char c;

buff = calloc(boardRowSize +
boardColSize +
(boardRowSize + 2) / 3 * (boardColSize + 2) / 3, sizeof(int));
//assert(buff);

bits_on_row = &buff[0];
bits_on_col = &buff[boardRowSize];
bits_on_square = &buff[boardRowSize + boardColSize];

for (i = 0; i  <  boardRowSize; i ++) {
for (j = 0; j  <  boardColSize; j ++) {
c = board[i][j];
if (c == '.') continue;
b = 1 << (c - '1');
bits_on_row[i] |= b;
bits_on_col[j] |= b;
bits_on_square[IDX(i, j)] |= b;
}
}

dfs(board, boardRowSize, boardColSize, bits_on_row, bits_on_col, bits_on_square);

free(buff);
}
``````
Copy The Code &

Input

cmd
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output

cmd
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 108 ms
class Solution0 {
public:
struct Trace {
int i;
int j;
int s;
Trace() : i(0), j(0), s(0) {}
Trace(int _i, int _j, int _s) : i(_i), j(_j), s(_s) {}
};

void solveSudoku(vector < vector<char>>& board) {
vector < vector<bool>> rowFlag(9, vector < bool>(9, false));
vector<vector<bool>> colFlag(9, vector < bool>(9, false));
vector<vector<bool>> boxFlag(9, vector < bool>(9, false));
vector<vector<bool>> occupied(9, vector < bool>(9, false));
int i, j;
int remains = 0;
for (i = 0; i  <  9; i++) {
for (j = 0; j  <  9; j++) {
if (board[i][j] != '.') {
int k = board[i][j] - '1';
rowFlag[i][k] = true;
colFlag[j][k] = true;
boxFlag[(i / 3) * 3 + j / 3][k] = true;
occupied[i][j] = true;
}
else {
remains++;
}
}
}

bool found = false;
vector < Trace> ans(remains);
placeNumber(board, found, ans, 0, remains, occupied, rowFlag, colFlag, boxFlag);
}

void placeNumber(vector < vector<char>>& board, bool &found,
vector < Trace> &ans, int count, int remains,
vector<vector<bool>> &occupied, vector < vector<bool>> &rowFlag,
vector < vector<bool>> &colFlag, vector < vector<bool>> &boxFlag)
{
if (count == remains) {
found = true;
int k = 0;
for (i = 0; i  <  9; i++) {
for (j = 0; j  <  9; j++) {
if (board[i][j] == '.') {
board[i][j] = ans[k++].s + '1';
}
}
}
return;
}

for (i = 0; i  <  9; i++) {
for (j = 0; j  <  9; j++) {
if (occupied[i][j] == false) {
for (int s = 0; s  <  9; s++) {

if (!rowFlag[i][s] && !colFlag[j][s] && !boxFlag[(i / 3) * 3 + j / 3][s]) {
rowFlag[i][s] = true;
colFlag[j][s] = true;
boxFlag[(i / 3) * 3 + j / 3][s] = true;
occupied[i][j] = true;
placeNumber(board, found, ans, count + 1, remains, occupied, rowFlag, colFlag, boxFlag);
}
}

if (count  < = 0) return;
Trace t = ans[count - 1];
rowFlag[t.i][t.s] = false;
colFlag[t.j][t.s] = false;
boxFlag[(t.i / 3) * 3 + t.j / 3][t.s] = false;
occupied[t.i][t.j] = false;
return;
}
}
}
}
};

// 36 ms
class Solution {
public:
void solveSudoku(vector < vector<char>>& board) {
vector < vector<bool>> rowFlag(10, vector < bool>(10, false));
vector<vector<bool>> colFlag(10, vector < bool>(10, false));
vector<vector<bool>> boxFlag(10, vector < bool>(10, false));
int i, j;
for (i = 0; i  <  9; i++) {
for (j = 0; j  <  9; j++) {
if (board[i][j] != '.') {
int k = board[i][j] - '1';
rowFlag[i][k] = true;
colFlag[j][k] = true;
boxFlag[(i / 3) * 3 + j / 3][k] = true;
}
}
}

bool found = false;
placeNumber(board, found, 0, rowFlag, colFlag, boxFlag);
}

bool placeNumber(vector < vector<char>>& board, bool &found,
int depth,
vector < vector<bool>> &rowFlag,
vector < vector<bool>> &colFlag, vector < vector<bool>> &boxFlag)
{
// suppose we have only one solution, if we found one, no need to continue
if (found) return true;

// found one solution! copy answers to the board
if (depth == 81) {
found = true;
return true;
}

int i, j;
i = depth / 9; j = depth % 9;

if (board[i][j] != '.') {
return placeNumber(board, found, depth + 1, rowFlag, colFlag, boxFlag);
}
else {
for (int s = 0; s  <  9; s++) {
// if it's valid, set flag and place another number
if (!rowFlag[i][s] && !colFlag[j][s] && !boxFlag[(i / 3) * 3 + j / 3][s]) {
// try to place a number
board[i][j] = s + '1';
rowFlag[i][s] = true;
colFlag[j][s] = true;
boxFlag[(i / 3) * 3 + j / 3][s] = true;
if (placeNumber(board, found, depth + 1, rowFlag, colFlag, boxFlag)) return true;
// backtrack
rowFlag[i][s] = false;
colFlag[j][s] = false;
boxFlag[(i / 3) * 3 + j / 3][s] = false;
board[i][j] = '.';
}
}
return false;
}
}
};

int main() {
vector < string> board0 = {
"..9748...",
"7........",
".2.1.9...",
"..7...24.",
".64.1.59.",
".98...3..",
"...8.3.2.",
"........6",
"...2759.."
};

vector<string> board1 = {
"53..7....",
"6..195...",
".98....6.",
"8...6...3",
"4..8.3..1",
"7...2...6",
".6....28.",
"...419..5",
"....8..79"
};

vector < vector<char> > board(9, vector<char>(9, 0));
int i, j;

// board0
for (i = 0; i  <  board0.size(); i++) {
for (j = 0; j  <  board0[i].length(); j++) {
board[i][j] = board0[i][j];
}
}

Solution s;
s.solveSudoku(board);

for (i = 0; i  <  board.size(); i++) {
for (j = 0; j  <  board[i].size(); j++) {
printf("%c ", board[i][j]);
}
printf("\n");
}

printf("-----------------\n");

// board1
for (i = 0; i  <  board1.size(); i++) {
for (j = 0; j  <  board1[i].length(); j++) {
board[i][j] = board1[i][j];
}
}

s.solveSudoku(board);

for (i = 0; i  <  board.size(); i++) {
for (j = 0; j  <  board[i].size(); j++) {
printf("%c ", board[i][j]);
}
printf("\n");
}

return 0;
}
``````
Copy The Code &

Input

cmd
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output

cmd
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const solveSudoku = function(board) {
dfs(0, 0)
function dfs(row, col) {
if (row === 9) return true
if (col === 9) return dfs(row + 1, 0)
if (board[row][col] === ".") {
for (let num = 1; num  < = 9; num++) {
if (isValid(row, col, `\${num}`)) {
board[row][col] = `\${num}`
if (dfs(row, col + 1)) return true
board[row][col] = "."
}
}
} else {
return dfs(row, col + 1)
}
return false
}
function isValid(row, col, num) {
for (let rowIdx = 0; rowIdx  <  9; rowIdx++) if (board[rowIdx][col] === num) return false
for (let colIdx = 0; colIdx  <  9; colIdx++) if (board[row][colIdx] === num) return false

let squareRowStart = row - (row % 3)
let squareColStart = col - (col % 3)
for (let rIdx = 0; rIdx  <  3; rIdx++) {
for (let cIdx = 0; cIdx  <  3; cIdx++) {
if (board[squareRowStart + rIdx][squareColStart + cIdx] === num) return false
}
}
return true
}
}

``````
Copy The Code &

Input

cmd
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output

cmd
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def solveSudoku(self, board):
rows, cols, triples, visit = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set), collections.deque([])
for r in range(9):
for c in range(9):
if board[r][c] != ".":
triples[(r // 3, c // 3)].add(board[r][c])
else:
visit.append((r, c))
def dfs():
if not visit:
return True
r, c = visit[0]
t = (r // 3, c // 3)
for dig in {"1", "2", "3", "4", "5", "6", "7", "8", "9"}:
if dig not in rows[r] and dig not in cols[c] and dig not in triples[t]:
board[r][c] = dig
visit.popleft()
if dfs():
return True
else:
board[r][c] = "."
visit.appendleft((r, c))
return False
dfs()
``````
Copy The Code &

Input

cmd
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output

cmd
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _037_SudokuSolver
{
bool[,] colUsed = new bool[9, 9];
bool[,] rowUsed = new bool[9, 9];
bool[,] squareUsed = new bool[9, 9];

public void SolveSudoku(char[,] board)
{
int row, column, squareId, value;
for (row = 0; row  <  9; row++)
{
for (column = 0; column  <  9; column++)
{
value = board[row, column] - '0' - 1;
if (value > 8 || value  <  0) { continue; }
squareId = (row / 3) * 3 + column / 3;
if (colUsed[column, value] || rowUsed[row, value] || squareUsed[squareId, value]) { return; }

colUsed[column, value] = rowUsed[row, value] = squareUsed[squareId, value] = true;
}
}

RecursiveSolver(board, 0, 0);
}

bool RecursiveSolver(char[,] boarder, int row, int col)
{
if (row == 9) { return true; }
if (col == 9) { return RecursiveSolver(boarder, row + 1, 0); }
if (boarder[row, col] != '.') { return RecursiveSolver(boarder, row, col + 1); }

int squareId;
for (int i = 0; i  <  9; i++)
{
squareId = (row / 3) * 3 + col / 3;
if (colUsed[col, i] || rowUsed[row, i] || squareUsed[squareId, i]) { continue; }

boarder[row, col] = (char)('1' + i);
colUsed[col, i] = rowUsed[row, i] = squareUsed[squareId, i] = true;
if (RecursiveSolver(boarder, row, col + 1))
{
return true;
}

boarder[row, col] = '.';
colUsed[col, i] = rowUsed[row, i] = squareUsed[squareId, i] = false;
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output

cmd
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]