Haskell solver that uses rules

1 files changed, 209 insertions, 0 deletions

diff --git a/solve2.cpp b/solve2.cpp
new file mode 100644
index 0000000..84ab2a1
--- /dev/null
+++ b/solve2.cpp
@@ -0,0 +1,209 @@
+#include <iostream>
+#include <iomanip>
+#include <string>
+#include <cassert>
+
+using namespace std;
+
+
+struct Sudoku {
+	int bd[81];
+	bool poss[81][9];
+
+	int& operator[](int i) {return bd[i];}
+	const int& operator[](int i) const {return bd[i];}
+
+	int nposs(int i) const {
+		int t = 0;
+		for (int j = 0; j < 9; j++) {
+			t += poss[i][j];
+		}
+		return t;
+	}
+};
+
+istream& operator>>(istream &in, Sudoku &su) {
+	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';
+		}
+
+		for (int j = 0; j < 9; j++) {
+			su.poss[i][j] = true;
+		}
+	}
+	return in;
+}
+
+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 << ' ';
+			}
+			int v = su[9 * y + x];
+			if (v == -1) os << '.';
+			else os << v + 1;
+			string s;
+			for (int i = 0; i < 9; i++) {
+				if (su.poss[9 * y + x][i]) s += '1' + i;
+			}
+			// os << '(' << setw(9) << s << ')';
+		}
+	}
+
+	return os;
+}
+
+void cleanPossBase(Sudoku &su, bool print=true) {
+	for (int y = 0; y < 9; y++)
+	for (int x = 0; x < 9; x++) {
+		if (su[9 * y + x] != -1) {
+			for (int i = 0; i < 9; i++) {
+				su.poss[9 * y + x][i] = false;
+			}
+			continue;
+		}
+
+		for (int i = 0; i < 9; i++) {
+			if (i != x && su[9 * y + i] != -1 && su.poss[9 * y + x][su[9 * y + i]]) {
+				if (print) cerr << "Removed poss " << su[9 * y + i]+1 << " at " << i << " because same number in row" << endl;
+				su.poss[9 * y + x][su[9 * y + i]] = false;
+			}
+			if (i != y && su[9 * i + x] != -1 && su.poss[9 * y + x][su[9 * i + x]]) {
+				if (print) cerr << "Removed poss " << su[9 * i + x]+1 << " at " << i << " because same number in column" << endl;
+				su.poss[9 * y + x][su[9 * i + x]] = false;
+			}
+			int bx = x / 3 * 3 + i % 3;
+			int by = y / 3 * 3 + i / 3;
+			if ((bx != x || by != y) && su[9 * by + bx] != -1 && su.poss[9 * y + x][su[9 * by + bx]]) {
+				if (print) cerr << "Removed poss " << su[9 * by + bx]+1 << " at " << i << " because same number in block" << endl;
+				su.poss[9 * y + x][su[9 * by + bx]] = false;
+			}
+		}
+	}
+}
+
+void cleanPossIndirectRC(Sudoku &su) {
+	for (int n = 0; n < 9; n++) {
+		for (int bi = 0; bi < 9; bi++) {
+			bool haveR[3] = {false, false, false};
+			bool haveC[3] = {false, false, false};
+			int bx = bi % 3 * 3, by = bi / 3 * 3;
+
+			for (int y = by; y < by + 3; y++) {
+				for (int x = bx; x < bx + 3; x++) {
+					if (su.poss[9 * y + x][n]) {
+						haveR[y - by] = true;
+						haveC[x - bx] = true;
+					}
+				}
+			}
+
+			if (haveR[0] + haveR[1] + haveR[2] == 1) {
+				int y = by + 0 * haveR[0] + 1 * haveR[1] + 2 * haveR[2];
+				for (int x = 0; x < 9; x++) {
+					if (su.poss[9 * y + x][n]) {
+						cerr << "Removed poss " << n+1 << " at " << 9*y+x << " because row-local numbers in block " << bi << endl;
+						su.poss[9 * y + x][n] = false;
+					}
+				}
+			}
+
+			if (haveC[0] + haveC[1] + haveC[2] == 1) {
+				int x = bx + 0 * haveC[0] + 1 * haveC[1] + 2 * haveC[2];
+				for (int y = 0; y < 9; y++) {
+					if (by <= y && y < by + 3) continue;
+					if (su.poss[9 * y + x][n]) {
+						cerr << "Removed poss " << n+1 << " at " << 9*y+x << " because row-local numbers in block " << bi << endl;
+						su.poss[9 * y + x][n] = false;
+					}
+				}
+			}
+		}
+	}
+}
+
+bool applySingles(Sudoku &su) {
+	for (int i = 0; i < 81; i++) {
+		if (su.nposs(i) == 1) {
+			for (int j = 0; j < 9; j++) {
+				if (su.poss[i][j]) {
+					cerr << "Set " << i << " to " << j+1 << " since nposs=1" << endl;
+					su[i] = j;
+					return true;
+				}
+			}
+		}
+	}
+
+	return false;
+}
+
+bool applyOnlysB(Sudoku &su) {
+	for (int n = 0; n < 9; n++) {
+		for (int bi = 0; bi < 9; bi++) {
+			int bx = bi % 3 * 3, by = bi / 3 * 3;
+
+			int idx = -1;
+			for (int y = by; y < by + 3; y++) {
+				for (int x = bx; x < bx + 3; x++) {
+					if (su.poss[9 * y + x][n]) {
+						if (idx == -1) idx = 9 * y + x;
+						else goto nope_next;
+					}
+				}
+			}
+
+			if (idx != -1) {
+				cerr << "Set " << idx << " to " << n+1 << " since only there in block" << endl;
+				su[idx] = n;
+				return true;
+			}
+
+		nope_next: ;
+		}
+	}
+
+	return false;
+}
+
+bool performStep(Sudoku &su) {
+	cleanPossBase(su);
+	cleanPossIndirectRC(su);
+
+	if (applySingles(su)) return true;
+	if (applyOnlysB(su)) return true;
+
+	return false;
+}
+
+void solve(Sudoku &su) {
+	cleanPossBase(su, false);
+	while (performStep(su)) {
+		cout << su << endl << endl;
+	}
+}
+
+int main() {
+	cout << "This solver is incorrect. On suvh.txt, it gives a 5 on x=0 y=3, while that should be an 8." << endl;
+	return 1;
+
+	Sudoku su;
+	cin >> su;
+
+	solve(su);
+
+	cout << su << endl;
+}