leetcode 37 - Sudoku Solver

https://leetcode.com/problems/sudoku-solver/
https://leetcode.com/problems/sudoku-solver/discuss/15853/Simple-and-Clean-Solution-C%2B%2B

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 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
dfs(board, 0, 0);
}

bool dfs(vector<vector<char>>& board, int r, int c) {
if (r == 9) return true;
if (c == 9) return dfs(board, r+1, 0);

if (board[r][c] != '.')
return dfs(board, r, c+1);

for (int v = 1; v <= 9; v++) {
if (isValidSudoku(board, r, c, v+'0')) {
board[r][c] = v + '0';
if (dfs(board, r, c+1))
return true;
}
}

board[r][c] = '.';
return false;
}

bool isValidSudoku(vector<vector<char>>& board, int r, int c, char v) {
for (int col = 0; col < 9; col++)
if (board[r][col] == v)
return false;

for (int row = 0; row < 9; row++)
if (board[row][c] == v)
return false;

r = r / 3 * 3;
c = c / 3 * 3;

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[r+i][c+j] == v)
return false;

return true;
}
};