summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--solve_bt_bfs.cpp51
1 files changed, 37 insertions, 14 deletions
diff --git a/solve_bt_bfs.cpp b/solve_bt_bfs.cpp
index bf14218..672b167 100644
--- a/solve_bt_bfs.cpp
+++ b/solve_bt_bfs.cpp
@@ -70,52 +70,75 @@ static ostream& operator<<(ostream &os, const Sudoku &su) {
return os;
}
+template <bool checkPoss>
static bool isValid(const Sudoku &su) {
for (int y = 0; y < 9; y++) {
int i = 9 * y;
- uint8_t seen[9];
- memset(seen, 0, 9);
+
+ uint16_t seen = 0;
+ uint16_t seenPoss = 0;
+
for (int x = 0; x < 9; x++, i++) {
int v = su[i];
if (v != -1) {
- if (seen[v]) return false;
- else seen[v] = 1;
+ if (seen & (1<<v)) return false;
+ else seen |= 1<<v;
+ } else {
+ if (checkPoss) seenPoss |= su.poss[i];
}
}
+
+ if (checkPoss) {
+ if ((seenPoss | seen) != 0x1ff) return false;
+ }
}
for (int x = 0; x < 9; x++) {
int i = x;
- uint8_t seen[9];
- memset(seen, 0, 9);
+
+ uint16_t seen = 0;
+ uint16_t seenPoss = 0;
+
for (int y = 0; y < 9; y++, i += 9) {
int v = su[i];
if (v != -1) {
- if (seen[v]) return false;
- else seen[v] = 1;
+ if (seen & (1<<v)) return false;
+ else seen |= 1<<v;
+ } else {
+ if (checkPoss) seenPoss |= su.poss[i];
}
}
+
+ if (checkPoss) {
+ if ((seenPoss | seen) != 0x1ff) return false;
+ }
}
int i = 0;
for (int by = 0; by < 9; by += 3) {
for (int bx = 0; bx < 9; bx += 3) {
- uint8_t seen[9];
- memset(seen, 0, 9);
+ uint16_t seen = 0;
+ uint16_t seenPoss = 0;
int j = i;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
int v = su[j];
if (v != -1) {
- if (seen[v]) return false;
- else seen[v] = 1;
+ if (seen & (1<<v)) return false;
+ else seen |= 1<<v;
+ } else {
+ if (checkPoss) seenPoss |= su.poss[j];
}
j++;
}
j += 6;
}
+ if (checkPoss) {
+ if ((seenPoss | seen) != 0x1ff) return false;
+ }
+
i += 3;
}
i += 18;
@@ -301,7 +324,7 @@ static Resolution solve(const Sudoku &su) {
item.su[i] = v;
scratchAround(item.su, i);
- if (isValid(item.su)) {
+ if (isValid<true>(item.su)) {
// item.maxposs = calcMaxposs(item.su);
item.init = {i, v};
qu.push_back(move(item));
@@ -335,7 +358,7 @@ static Resolution solve(const Sudoku &su) {
item.su[i] = v;
scratchAround(item.su, i);
- if (isValid(item.su)) {
+ if (isValid<true>(item.su)) {
// item.maxposs = calcMaxposs(item.su);
qu.push_back(move(item));