This problem was quite frustrating.
At first I misunderstood the problem and thought it was asking whether a Sudoku puzzle has a valid solution – enumeration? Brute force.
I wrote a version using set collections that kept timing out:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| struct PointOfBoard {
set<int>set_p;
bool IsExist;
int val;
PointOfBoard():IsExist(false),val(-1){set_p.clear();}
};
class Solution {
public:
PointOfBoard POB[9][9];
int x[81];
int y[81];
int index;
bool result;
int GetRegionOfBoard(int x,int y) {
if(x>= 0 && x < 3) {
if(y >= 0 && y < 3)return 0;
if(y >= 3 && y < 6)return 1;
if(y >= 6 && y < 9)return 2;
}
if(x >= 3 && x < 6) {
if(y >= 0 && y < 3)return 3;
if(y >= 3 && y < 6)return 4;
if(y >= 6 && y < 9)return 5;
}
if(x >= 6 && x < 9) {
if(y >= 0 && y < 3)return 6;
if(y >= 3 && y < 6)return 7;
if(y >= 6 && y < 9)return 8;
}
}
bool GetSetOfPOB(int x,int y){
set<int>set_tmp;
set_tmp.clear();
for(int i = 0;i < 9;i++) {
if(POB[x][i].IsExist) {
int val = POB[x][i].val;
if(set_tmp.find(val) == set_tmp.end())
set_tmp.insert(val);
}
if(POB[i][y].IsExist) {
int val = POB[i][y].val;
if(set_tmp.find(val) == set_tmp.end())
set_tmp.insert(val);
}
}
int region = GetRegionOfBoard(x,y);
int x_r = (region / 3 + 1)*3;
int y_r = (region % 3 + 1)*3;
for(int i = x_r-3;i < x_r;i++) {
for(int j = y_r-3;j < y_r;j++) {
if(POB[i][j].IsExist) {
int val = POB[i][j].val;
if(set_tmp.find(val) != set_tmp.end())
set_tmp.insert(val);
}
}
}
if(set_tmp.size() == 9)return false;
set<int>::iterator it;
for(int i = 1;i <= 9;i++) {
if(set_tmp.find(i) == set_tmp.end())POB[x][y].set_p.insert(i);
}
if(POB[x][y].set_p.size() <= 0)return false;
return true;
}
void Move(int step) {
if(step >= index) {
result = true;
return;
}
else {
if(result == true)return;
int pi = x[step];
int pj = y[step];
set<int>::iterator it;
for(it = POB[pi][pj].set_p.begin();it != POB[pi][pj].set_p.end();it++) {
if(result == true)return;
int val = (int)(*it);
POB[pi][pj].val = val;
int xtmp[81];
int ytmp[81];
int indextmp = 0;
for(int i = step+1;i < index;i++) {
int xi = x[i];
int yi = y[i];
if(xi == pi || yi == pj || GetRegionOfBoard(xi,yi) == GetRegionOfBoard(pi,pj)) {
if(POB[xi][yi].set_p.find(val) != POB[xi][yi].set_p.end()) {
xtmp[indextmp] = xi;
ytmp[indextmp++] = yi;
POB[xi][yi].set_p.erase(val);
}
}
}
Move(step+1);
for(int i = 0;i < indextmp;i++) {
int xi = xtmp[i];
int yi = ytmp[i];
POB[xi][yi].set_p.insert(val);
}
POB[pi][pj].val = -1;
}
}
}
bool isValidSudoku(vector<vector<char>> &board) {
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(board[i][j] == '.') {
POB[i][j].IsExist = false;
}
else {
POB[i][j].IsExist = true;
POB[i][j].val = board[i][j] - '0';
}
}
}
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(POB[i][j].IsExist == false) {
if(GetSetOfPOB(i,j) == false)return false;
}
}
}
index = 0;
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(POB[i][j].IsExist == false) {
x[index] = i;
y[index++] = j;
}
}
}
result = false;
Move(0);
return result;
}
};
|
Later I saw someone else’s code using binary int representation, so I wrote another version:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
| struct Pointxy {
int x;
int y;
int val;
};
int cmp(Pointxy a,Pointxy b) {
return a.val < b.val;
}
class Solution {
public:
int bitarray[9];
int map[9][9];
bool result;
int CountOnes(int v)
{
int number = 0;
while(v)
{
v &= (v-1);
number++;
}
return number;
}
int GetRegionOfBoard(int x,int y) {
if(x>= 0 && x < 3) {
if(y >= 0 && y < 3)return 0;
if(y >= 3 && y < 6)return 1;
if(y >= 6 && y < 9)return 2;
}
if(x >= 3 && x < 6) {
if(y >= 0 && y < 3)return 3;
if(y >= 3 && y < 6)return 4;
if(y >= 6 && y < 9)return 5;
}
if(x >= 6 && x < 9) {
if(y >= 0 && y < 3)return 6;
if(y >= 3 && y < 6)return 7;
if(y >= 6 && y < 9)return 8;
}
}
bool RefeshMap(int x,int y){
int set_tmp = 0;
for(int i = 0;i < 9;i++) {
if(CountOnes(map[x][i]) == 1) {
set_tmp = set_tmp | map[x][i];
}
if(CountOnes(map[i][y]) == 1) {
set_tmp = set_tmp | map[x][i];
}
}
int region = GetRegionOfBoard(x,y);
int x_r = (region / 3 + 1)*3;
int y_r = (region % 3 + 1)*3;
for(int i = x_r-3;i < x_r;i++) {
for(int j = y_r-3;j < y_r;j++) {
if(CountOnes(map[i][j]) == 1) {
set_tmp = set_tmp | map[i][j];
}
}
}
if(set_tmp == 511)return false;
map[x][y] = 511 - set_tmp;
return true;
}
void Move(Pointxy pxy[81],int index) {
if(result == true)return;
if(index <= 0) {
result = true;
return;
}
else {
sort(pxy,pxy+index,cmp);
int pi = pxy[0].x;
int pj = pxy[0].y;
for(int ibit = 0;ibit < 9;ibit++) {
if(result == true)return;
if(map[pi][pj] & bitarray[ibit]) {
map[pi][pj] -= bitarray[ibit];
int xtmp[81];
int ytmp[81];
int indextmp = 0;
for(int i = 1;i < index;i++) {
int xi = pxy[i].x;
int yi = pxy[i].y;
if(xi == pi || yi == pj || GetRegionOfBoard(xi,yi) == GetRegionOfBoard(pi,pj)) {
if(map[xi][yi] & bitarray[ibit]) {
xtmp[indextmp] = xi;
ytmp[indextmp++] = yi;
map[xi][yi] -= bitarray[ibit];
}
}
}
Pointxy pxyt[81];
int indext = 0;
for(int i = 1;i < index;i++) {
pxyt[indext].x = pxy[i].x;
pxyt[indext].y = pxy[i].y;
pxyt[indext++].val = CountOnes(map[pxyt[indext].x][pxyt[indext].y]);
}
Move(pxyt,indext);
for(int i = 0;i < indextmp;i++) {
int xi = xtmp[i];
int yi = ytmp[i];
map[xi][yi] += bitarray[ibit];
}
map[pi][pj] += bitarray[ibit];
}
}
}
}
bool isValidSudoku(vector<vector<char>> &board) {
for(int i = 0;i < 9;i++) {
bitarray[i] = (int)pow(2.0,i);
}
int count = 0;
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(board[i][j] == '.') {
map[i][j] = 511;
}
else {
map[i][j] = bitarray[board[i][j] - '0'-1];
count++;
}
}
}
if(count < 17)return false;
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(map[i][j] == 511) {
if(RefeshMap(i,j) == false)return false;
}
}
}
Pointxy pxy[81];
int index = 0;
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(CountOnes(map[i][j]) != 1) {
pxy[index].x = i;
pxy[index].y = j;
pxy[index].val = CountOnes(map[i][j]);
}
}
}
result = false;
Move(pxy,index);
return result;
}
};
|
WA??? That doesn’t make sense???
The final WA was on a case that was obviously unsolvable.
With no other option, I looked at other people’s code. Turns out the problem only asks to validate whether the current state of the Sudoku board satisfies the rules – the problem is so much simpler!
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| class Solution {
public:
int bitarray[9];
int map[9][9];
bool result;
int GetRegionOfBoard(int x,int y) {
if(x>= 0 && x < 3) {
if(y >= 0 && y < 3)return 0;
if(y >= 3 && y < 6)return 1;
if(y >= 6 && y < 9)return 2;
}
if(x >= 3 && x < 6) {
if(y >= 0 && y < 3)return 3;
if(y >= 3 && y < 6)return 4;
if(y >= 6 && y < 9)return 5;
}
if(x >= 6 && x < 9) {
if(y >= 0 && y < 3)return 6;
if(y >= 3 && y < 6)return 7;
if(y >= 6 && y < 9)return 8;
}
}
bool CheckRows() {
for(int i = 0;i < 9;i++) {
int tmp = 0;
for(int j = 0;j < 9;j++) {
if(tmp & map[i][j])return false;
tmp |= map[i][j];
}
}
return true;
}
bool CheckCols() {
for(int j = 0;j < 9;j++) {
int tmp = 0;
for(int i = 0;i < 9;i++) {
if(tmp & map[i][j])return false;
tmp |= map[i][j];
}
}
return true;
}
bool CheckRegion() {
for(int region = 0;region < 9;region++) {
int x_r = (region / 3 + 1)*3;
int y_r = (region % 3 + 1)*3;
int tmp = 0;
for(int i = x_r-3;i < x_r;i++) {
for(int j = y_r-3;j < y_r;j++) {
if(tmp & map[i][j])return false;
tmp = tmp | map[i][j];
}
}
}
return true;
}
bool isValidSudoku(vector<vector<char>> &board) {
for(int i = 0;i < 9;i++) {
bitarray[i] = (int)pow(2.0,i);
}
for(int i = 0;i < 9;i++) {
for(int j = 0;j < 9;j++) {
if(board[i][j] == '.') {
map[i][j] = 0;
}
else {
map[i][j] = bitarray[board[i][j] - '0'-1];
}
}
}
return CheckRows() && CheckCols() && CheckRegion();
}
};
|