# 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;
4     int rmark;
5     int smark;
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 };``````

Loading Disqus comments...
Table of Contents