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
| bool helper(vector<vector<char>>& A, vector<int>& row, vector<int>& col, vector<int>& cell, int p) {
if(p == 81) return true;
else {
int y = p / 9, x = p % 9;
if(A[y][x] != '.') return helper(A,row,col,cell,p+1);
else {
for(int i = 0; i < 9; i++) {
if(row[y] & (1<<i)) continue;
if(col[x] & (1<<i)) continue;
if(cell[y/3*3 + x/3] & (1<<i)) continue;
row[y] ^= (1<<i);
col[x] ^= (1<<i);
cell[y/3*3 + x/3] ^= (1<<i);
A[y][x] = '1' + i;
if(helper(A,row,col,cell,p+1)) return true;
A[y][x] = '.';
row[y] ^= (1<<i);
col[x] ^= (1<<i);
cell[y/3*3 + x/3] ^= (1<<i);
}
return false;
}
}
}
void Solution::solveSudoku(vector<vector<char> > &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;
row[i] |= (1<<(A[i][j]-'1'));
col[j] |= (1<<(A[i][j]-'1'));
cell[i/3*3 + j/3] |= (1<<(A[i][j]-'1'));
}
}
helper(A,row,col,cell,0);
}
|
