summaryrefslogtreecommitdiff
path: root/solve_bt_bfs.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'solve_bt_bfs.cpp')
-rw-r--r--solve_bt_bfs.cpp373
1 files changed, 373 insertions, 0 deletions
diff --git a/solve_bt_bfs.cpp b/solve_bt_bfs.cpp
new file mode 100644
index 0000000..bf14218
--- /dev/null
+++ b/solve_bt_bfs.cpp
@@ -0,0 +1,373 @@
+#include <iostream>
+#include <iomanip>
+#include <string>
+#include <vector>
+#include <deque>
+#include <cstring>
+#include <cstdint>
+#include <cassert>
+
+using namespace std;
+
+
+struct Sudoku {
+ int8_t bd[81];
+ uint16_t poss[81];
+ int nfull = 0;
+
+ Sudoku() {
+ for (int i = 0; i < 81; i++) {
+ poss[i] = 0x1ff;
+ }
+ }
+
+ inline int8_t& operator[](int8_t i) {return bd[i];}
+ inline const int8_t& operator[](int8_t i) const {return bd[i];}
+};
+
+static istream& operator>>(istream &in, Sudoku &su) {
+ su.nfull = 0;
+
+ for (int i = 0; i < 81; i++) {
+ char c;
+ in >> c;
+ if (c == '.') {
+ su[i] = -1;
+ } else {
+ assert('1' <= c && c <= '9');
+ su[i] = c - '1';
+ su.nfull++;
+ }
+ }
+
+ return in;
+}
+
+__attribute__((unused))
+static ostream& operator<<(ostream &os, const Sudoku &su) {
+ for (int y = 0; y < 9; y++) {
+ if (y != 0) {
+ os << endl;
+ if (y % 3 == 0) os << endl;
+ }
+
+ for (int x = 0; x < 9; x++) {
+ if (x != 0) {
+ os << ' ';
+ if (x % 3 == 0) os << ' ';
+ }
+ int8_t v = su[9 * y + x];
+ if (v == -1) os << '.';
+ else os << (int)v + 1;
+ // string s;
+ // for (int i = 0; i < 9; i++) {
+ // if (su.poss[9 * y + x] & (1<<i)) s += '1' + i;
+ // }
+ // os << '(' << setw(9) << s << ')';
+ }
+ }
+
+ return os;
+}
+
+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);
+ for (int x = 0; x < 9; x++, i++) {
+ int v = su[i];
+ if (v != -1) {
+ if (seen[v]) return false;
+ else seen[v] = 1;
+ }
+ }
+ }
+
+ for (int x = 0; x < 9; x++) {
+ int i = x;
+ uint8_t seen[9];
+ memset(seen, 0, 9);
+ 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;
+ }
+ }
+ }
+
+ 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);
+
+ 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;
+ }
+ j++;
+ }
+ j += 6;
+ }
+
+ i += 3;
+ }
+ i += 18;
+ }
+
+ return true;
+}
+
+static void scratchAround(Sudoku &su, int idx, int x, int y) {
+ uint16_t mask = 0x1ff & ~(1 << su[idx]);
+
+ for (int i = 0; i < 9; i++) {
+ su.poss[9 * y + i] &= mask;
+ su.poss[9 * i + x] &= mask;
+ }
+
+ int bx = x / 3 * 3, by = y / 3 * 3;
+ for (int yi = 0; yi < 3; yi++) {
+ for (int xi = 0; xi < 3; xi++) {
+ su.poss[9 * (by + yi) + bx + xi] &= mask;
+ }
+ }
+}
+
+static void scratchAround(Sudoku &su, int idx) {
+ scratchAround(su, idx, idx % 9, idx / 9);
+}
+
+static void scratchAround(Sudoku &su, int x, int y) {
+ scratchAround(su, 9 * y + x, x, y);
+}
+
+#if 0
+struct Resolution {
+ bool ok; // false if the given sudoku cannot be made valid at all
+ int index, value;
+
+ Resolution() : ok(false) {}
+ Resolution(int index, int value) : ok(true), index(index), value(value) {}
+};
+
+static Resolution solveDestructive(Sudoku &su) {
+ // cerr << "solveDestructive(" << su.nfull << ")" << endl;
+
+ // for (int y = 0, i = 0; y < 9; y++) {
+ // for (int x = 0; x < 9; x++, i++) {
+ // if (su[i] != -1) continue;
+
+ // if (__builtin_popcount(su.poss[i]) == 1) {
+ // int value = __builtin_ctz(su.poss[i]);
+ // su[i] = value;
+ // scratchAround(su, i);
+ // }
+ // }
+ // }
+
+ if (su.nfull == 81) {
+ if (isValid(su)) {
+ return Resolution(-1, -1);
+ } else {
+ return Resolution();
+ }
+ }
+
+ vector<pair<int, int>> options; // pair(index, count)
+
+ for (int y = 0, i = 0; y < 9; y++) {
+ for (int x = 0; x < 9; x++, i++) {
+ if (su[i] != -1) continue;
+
+ int count = __builtin_popcount((uint32_t)su.poss[i]);
+ options.emplace_back(i, count);
+ }
+ }
+
+ sort(options.begin(), options.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
+ return a.second < b.second;
+ });
+
+ if (options[0].second == 0) {
+ // invalid
+ return Resolution();
+ }
+
+ for (const pair<int, int> &p : options) {
+ int index = p.first;
+
+ vector<int> okValues;
+
+ for (int v = 0; v < 9; v++) {
+ if ((su.poss[index] & (1 << v)) == 0) continue;
+
+ Sudoku su2 = su;
+ su2[index] = v;
+ su2.nfull++;
+ // cerr << "try " << v << endl;
+ if (!isValid(su2)) {
+ // cerr << " invalid" << endl;
+ continue;
+ }
+
+ scratchAround(su2, index);
+ if (solveDestructive(su2).ok) {
+ okValues.push_back(v);
+ }
+ }
+
+ if (okValues.size() == 0) {
+ // invalid
+ return Resolution();
+ }
+
+ if (okValues.size() == 1) {
+ return Resolution(index, okValues[0]);
+ }
+ }
+
+ assert(false);
+}
+#endif
+
+struct Resolution {
+ int index, value;
+
+ Resolution(int index, int value) : index(index), value(value) {}
+ Resolution() : index(-1), value(-1) {}
+};
+
+static bool operator==(const Resolution &a, const Resolution &b) {
+ return a.index == b.index && a.value == b.value;
+}
+
+static bool operator!=(const Resolution &a, const Resolution &b) {
+ return !(a == b);
+}
+
+static int calcMaxposs(const Sudoku &su) {
+ int mx = 0;
+ for (int i = 0; i < 81; i++) {
+ mx = max(mx, __builtin_popcount((unsigned)su.poss[i]));
+ }
+ return mx;
+}
+
+struct Item {
+ Sudoku su;
+ int maxposs;
+ Resolution init;
+ int depth;
+};
+
+static Resolution singularQueue(const deque<Item> &qu) {
+ assert(qu.size() > 0);
+
+ int values[81];
+ memset(values, 0xff, 81 * sizeof(int));
+
+ for (const Item &item : qu) {
+ if (values[item.init.index] == -1) {
+ values[item.init.index] = item.init.value;
+ } else {
+ values[item.init.index] = -2;
+ }
+ }
+
+ for (int i = 0; i < 81; i++) {
+ if (values[i] >= 0) return Resolution(i, values[i]);
+ }
+
+ return Resolution();
+}
+
+static Resolution solve(const Sudoku &su) {
+ // Sudoku su2 = su;
+ // return solveDestructive(su2);
+
+ deque<Item> qu;
+ for (int i = 0; i < 81; i++) {
+ if (su[i] != -1) continue;
+
+ for (int v = 0; v < 9; v++) {
+ Item item = {su, 0, {0, 0}, 1};
+ item.su[i] = v;
+ scratchAround(item.su, i);
+
+ if (isValid(item.su)) {
+ // item.maxposs = calcMaxposs(item.su);
+ item.init = {i, v};
+ qu.push_back(move(item));
+ }
+ }
+ }
+
+ int lastdepth = -1;
+
+ while (qu.size() > 0) {
+ Resolution res = singularQueue(qu);
+ if (res.index != -1) {
+ return res;
+ }
+
+ Item current = move(qu.front());
+ qu.pop_front();
+
+ if (current.depth != lastdepth) {
+ cout << "depth = " << current.depth << " current: " << current.init.index << " " << current.init.value + 1 << endl;
+ lastdepth = current.depth;
+ }
+
+ bool anyvalid = false;
+
+ for (int i = 0; i < 81; i++) {
+ if (current.su[i] != -1) continue;
+
+ for (int v = 0; v < 9; v++) {
+ Item item = {current.su, 0, current.init, current.depth + 1};
+ item.su[i] = v;
+ scratchAround(item.su, i);
+
+ if (isValid(item.su)) {
+ // item.maxposs = calcMaxposs(item.su);
+ qu.push_back(move(item));
+
+ anyvalid = true;
+ }
+ }
+ }
+
+ if (current.depth == 1 && !anyvalid) {
+ cout << "discarded " << current.init.index << " " << current.init.value << " at depth=1" << endl;
+ }
+ }
+
+ return Resolution();
+}
+
+
+static void cleanPoss(Sudoku &su) {
+ for (int i = 0; i < 81; i++) su.poss[i] = 0x1ff;
+
+ for (int y = 0; y < 9; y++) {
+ for (int x = 0; x < 9; x++) {
+ scratchAround(su, x, y);
+ }
+ }
+}
+
+int main() {
+ Sudoku su;
+ cin >> su;
+
+ cleanPoss(su);
+ Resolution res = solve(su);
+ cout << "resolution: " << res.index << " " << res.value + 1 << endl;
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-22 06:41:07 +0100