diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | solve_bt_bfs.cpp | 373 |
3 files changed, 375 insertions, 1 deletions
@@ -1,6 +1,7 @@ solve solve2 solve_bt +solve_bt_bfs *.o *.dSYM .DS_Store @@ -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 <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; +} |