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 };

Loading Disqus comments...
Table of Contents