LeetCode

Valid Sudoku

2013.12.15 02:59

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Solution:

　　For introduction of Sudoku game, please see Sudoku here.

　　If you like, I'd recommend this game "Funny Sudoku" to you.

　　For a valid 9X9 Sudoku, there will never be duplicate numbers in the same row, column or 3X3 subsquare.

　　Just check if the data given conforms to the rule.

　　Time complexity is O(n^2), where n is the number of rows/columns of the Sudoku. Space complexity is O(n^2), actually the space needed is only O(n)...

Accepted code:

 1 // 1WA, 1AC, carefully coding is important, think twice before you submit!
 2 #include <cmath>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     bool isValidSudoku(vector<vector<char> > &board) {
 8         // IMPORTANT: Please reset any member data you declared, as
 9         // the same Solution instance will be reused for each test case.
10         int n, n2;
11         int i, j;
12         
13         n2 = board.size();
14         if(n2 <= 0){
15             return true;
16         }
17         
18         tag = new bool*[n2];
19         for(i = 0; i < n2; ++i){
20             tag[i] = new bool[n2];
21         }
22         
23         bool res = true;
24         n = (int)sqrt(1.0 * n2);
25         
26         // check row
27         for(i = 0; i < n2; ++i){
28             for(j = 0; j < n2; ++j){
29                 tag[i][j] = false;
30             }
31         }
32         for(i = 0; res && i < n2; ++i){
33             for(j = 0; res && j < n2; ++j){
34                 if(board[i][j] >= '1' && board[i][j] <= '9'){
35                     if(tag[i][board[i][j] - '1']){
36                         res = false;
37                     }else{
38                         tag[i][board[i][j] - '1'] = true;
39                     }
40                 }
41             }
42         }
43         
44         // check column
45         for(i = 0; i < n2; ++i){
46             for(j = 0; j < n2; ++j){
47                 tag[i][j] = false;
48             }
49         }
50         for(i = 0; res && i < n2; ++i){
51             for(j = 0; res && j < n2; ++j){
52                 if(board[j][i] >= '1' && board[j][i] <= '9'){
53                     if(tag[i][board[j][i] - '1']){
54                         res = false;
55                     }else{
56                         tag[i][board[j][i] - '1'] = true;
57                     }
58                 }
59             }
60         }
61 
62         // check block
63         for(i = 0; i < n2; ++i){
64             for(j = 0; j < n2; ++j){
65                 tag[i][j] = false;
66             }
67         }
68         for(i = 0; res && i < n2; ++i){
69             for(j = 0; res && j < n2; ++j){
70                 if(board[i / n * n + j / n][i % n * n + j % n] >= '1' && board[i / n * n + j / n][i % n * n + j % n] <= '9'){
71                     if(tag[i][board[i / n * n + j / n][i % n * n + j % n] - '1']){
72                         res = false;
73                     }else{
74                         // 1WA here, this else brach is missing!!
75                         tag[i][board[i / n * n + j / n][i % n * n + j % n] - '1'] = true;
76                     }
77                 }
78             }
79         }
80         
81         for(i = 0; i < n2; ++i){
82             delete[] tag[i];
83         }
84         delete[] tag;
85         
86         return res;
87     }
88 private:
89     bool **tag;
90 };