summaryrefslogtreecommitdiff
path: root/solve2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'solve2.cpp')
-rw-r--r--solve2.cpp209
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;
+}