## Sudoku Solver

• Time:NP-Complete
• Space:O(1)

## C++

``````class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board, 0);
}

private:
bool solve(vector<vector<char>>& board, int s) {
if (s == 81)
return true;

const int i = s / 9;
const int j = s % 9;

if (board[i][j] != '.')
return solve(board, s + 1);

for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board, s + 1))
return true;
board[i][j] = '.';
}

return false;
}

bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
};
``````

## JAVA

``````class Solution {
public void solveSudoku(char[][] board) {
dfs(board, 0);
}

private boolean dfs(char[][] board, int s) {
if (s == 81)
return true;

final int i = s / 9;
final int j = s % 9;

if (board[i][j] != '.')
return dfs(board, s + 1);

for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (dfs(board, s + 1))
return true;
board[i][j] = '.';
}

return false;
}

private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
}
``````

## Python

``````class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def isValid(row: int, col: int, c: chr) -> bool:
for i in range(9):
if board[i][col] == c or \
board[row][i] == c or \
board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
return False
return True

def solve(s: int) -> bool:
if s == 81:
return True

i = s // 9
j = s % 9

if board[i][j] != '.':
return solve(s + 1)

for c in string.digits[1:]:
if isValid(i, j, c):
board[i][j] = c
if solve(s + 1):
return True
board[i][j] = '.'

return False

solve(0)
``````