# Soduku Solver

## Soduku Solver

### Brute force got TLE

This is a DFS problem. Every time, we could go through the board. Find an empty place, try every condition. When there is no empty space, return the result. But, this got TLE.

### Better way

In the way before, we waste a lot of time in finding position. So, this time, we go through the board at first and record every empty space in a vector. Each time in DFS, we get an empty place in the vector, then enumerate every condition.

```
1 class Solution {
2 private:
3 int cmark[9][10];
4 int rmark[9][10];
5 int smark[9][10];
6 vector<int > v;
7 public:
8 void solveSudoku(vector<vector<char> > &board) {
9 memset(cmark,0,sizeof(cmark));
10 memset(rmark,0,sizeof(rmark));
11 memset(smark,0,sizeof(smark));
12 v.clear();
13 for ( int i = 0; i < 9; ++i ) {
14 for ( int j = 0; j < 9; ++j ) {
15 if ( board[i][j] == '.' ) {
16 v.push_back(i*10+j);
17 } else {
18 rmark[i][board[i][j]-'0'] = 1;
19 cmark[j][board[i][j]-'0'] = 1;
20 smark[i/3*3+j/3][board[i][j]-'0'] = 1;
21 }
22 }
23 }
24 dfs(board,0);
25 }
26
27 bool dfs( vector<vector<char> > &board, int x ) {
28 if ( x == v.size() ) {
29 return true;
30 }
31 int i = v[x]/10;
32 int j = v[x]%10;
33 for ( int k = 1; k <= 9; ++k ) {
34 if ( rmark[i][k] == 0 && cmark[j][k] == 0 && smark[i/3*3+j/3][k] == 0 ) {
35 board[i][j] = k+'0';
36 rmark[i][k] = 1;
37 cmark[j][k] = 1;
38 smark[i/3*3+j/3][k] = 1;
39 if ( dfs(board,x+1) ) {
40 return true;
41 }
42 rmark[i][k] = 0;
43 cmark[j][k] = 0;
44 smark[i/3*3+j/3][k] = 0;
45 board[i][j] = '.';
46 }
47 }
48 return false;
49 }
50 };
```