From 5510daa27df1d1468718c10bbf45f0d3fa0950ae Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sat, 1 Sep 2018 21:47:40 +0200 Subject: Add experimental BFS solver --- .gitignore | 1 + Makefile | 2 +- solve_bt_bfs.cpp | 373 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 375 insertions(+), 1 deletion(-) create mode 100644 solve_bt_bfs.cpp diff --git a/.gitignore b/.gitignore index 0e0fdf2..e72c08f 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ solve solve2 solve_bt +solve_bt_bfs *.o *.dSYM .DS_Store diff --git a/Makefile b/Makefile index 5d17a4c..3033da1 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ CXX = g++ CXXFLAGS = -Wall -Wextra -std=c++11 -fwrapv -O2 -CXXTARGETS = solve solve2 solve_bt +CXXTARGETS = solve solve2 solve_bt solve_bt_bfs .PHONY: all clean remake 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 +#include +#include +#include +#include +#include +#include +#include + +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<> 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 &a, const pair &b) { + return a.second < b.second; + }); + + if (options[0].second == 0) { + // invalid + return Resolution(); + } + + for (const pair &p : options) { + int index = p.first; + + vector 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 &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 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; +} -- cgit v1.2.3-70-g09d2