1
class Solution {
2
 public:
3
  bool issafe(vector<vector<char>> &board, int row, int col, char c) {
4
    for (int i = 0; i < 9; i++) {
5
      if (board[row][i] == c) return 0;
6
      if (board[i][col] == c) return 0;
7
      if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return 0;
8
    }
9
    return 1;
10
  }
11

12
  bool solve(vector<vector<char>> &board) {
13
    for (int i = 0; i < 9; i++) {
14
      for (int j = 0; j < 9; j++) {
15
        if (board[i][j] == '.') {
16
          for (char c = '1'; c <= '9'; c++) {
17
            if (issafe(board, i, j, c)) {
18
              board[i][j] = c;
19
              if (solve(board) == 1)
20
                return 1;
21
              else
22
                board[i][j] = '.';
23
            }
24
          }
25
          return 0;
26
        }
27
      }
28
    }
29
    return 1;
30
  }
31

32
  void solveSudoku(vector<vector<char>> &board) {
33
    solve(board);
34
  }
35
};