Add experimental BFS solver

3 files changed, 375 insertions, 1 deletions

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 <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;
+}