path: root/solve_bt_bfs.cpp

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

template <bool checkPoss>
static bool isValid(const Sudoku &su) {
	for (int y = 0; y < 9; y++) {
		int i = 9 * y;

		uint16_t seen = 0;
		uint16_t seenPoss = 0;

		for (int x = 0; x < 9; x++, i++) {
			int v = su[i];
			if (v != -1) {
				if (seen & (1<<v)) return false;
				else seen |= 1<<v;
			} else {
				if (checkPoss) seenPoss |= su.poss[i];
			}
		}

		if (checkPoss) {
			if ((seenPoss | seen) != 0x1ff) return false;
		}
	}

	for (int x = 0; x < 9; x++) {
		int i = x;

		uint16_t seen = 0;
		uint16_t seenPoss = 0;

		for (int y = 0; y < 9; y++, i += 9) {
			int v = su[i];
			if (v != -1) {
				if (seen & (1<<v)) return false;
				else seen |= 1<<v;
			} else {
				if (checkPoss) seenPoss |= su.poss[i];
			}
		}

		if (checkPoss) {
			if ((seenPoss | seen) != 0x1ff) return false;
		}
	}

	int i = 0;
	for (int by = 0; by < 9; by += 3) {
		for (int bx = 0; bx < 9; bx += 3) {
			uint16_t seen = 0;
			uint16_t seenPoss = 0;

			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 & (1<<v)) return false;
						else seen |= 1<<v;
					} else {
						if (checkPoss) seenPoss |= su.poss[j];
					}
					j++;
				}
				j += 6;
			}

			if (checkPoss) {
				if ((seenPoss | seen) != 0x1ff) return false;
			}

			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<true>(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<true>(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;
}