diff options
| -rw-r--r-- | solve_bt_bfs.cpp | 51 |
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)); |