diff options
Diffstat (limited to 'solve2.cpp')
| -rw-r--r-- | solve2.cpp | 209 |
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; +} |