1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| bool helper(const vector<string>& A, vector<int>& row, vector<int>& col, vector<int>& cell, int now) {
if(now == 81) return true;
else {
int y = now / 9, x = now % 9;
if(A[y][x] != '.') return helper(A,row,col,cell,now+1);
int& rrow = row[y];
int& ccol = col[x];
int& ccell = cell[y/3 * 3 + x/3];
for(int i = 1; i <= 9; i++) {
if(rrow & (1<<i)) continue;
if(ccol & (1<<i)) continue;
if(ccell & (1<<i)) continue;
rrow ^= (1<<i);
ccol ^= (1<<i);
ccell ^= (1<<i);
if(helper(A,row,col,cell,now+1)) return true;
rrow ^= (1<<i);
ccol ^= (1<<i);
ccell ^= (1<<i);
}
return false;
}
}
int Solution::isValidSudoku(const vector<string> &A) {
vector<int> row(9), col(9), cell(9);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(A[i][j] == '.') continue;
int now = A[i][j] & 0b1111;
if(row[i] & (1<<now)) return false;
row[i] |= (1<<now);
if(col[j] & (1<<now)) return false;
col[j] |= (1<<now);
if(cell[i/3 * 3 + j/3] & (1<<now)) return false;
cell[i/3 * 3 + j/3] |= (1<<now);
}
}
return helper(A,row,col,cell,0);
}
|
