Takuzu puzzle solver

takuzu.cpp

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

enum Square { Zero, One, Nothing };

Square inverse(Square s) {
	return s == Zero ? One : Zero;
}

bool verify(std::vector<std::vector<Square>> &d);
bool recursive_solve(std::vector<std::vector<Square>> &d);

class Takuzu {
    std::vector<std::vector<Square>> data;
    size_t N;

    bool check_double();
    bool check_number();
    bool check_repeat();
 public:
    std::vector<Square> getRow(int n) const;
    std::vector<Square> getColumn(int n) const;
    std::vector<std::vector<Square>> getData() const;
    size_t getSize() const;

    void setRow(std::vector<Square> row, int n);
    void setColumn(std::vector<Square> column, int n);

    Takuzu(std::vector<std::string> s);
    Takuzu(std::vector<std::vector<Square>> d);

    bool solve();
    bool solveBF();
    bool isSolved() const;
    bool verify() const;

    friend std::ostream &operator<<(std::ostream &os, const Takuzu &tk);
};


int main() {
	std::vector<std::string> d;
	std::string t;
	std::cin >> t;
	d.push_back(t);

	for (size_t i = 0; i < t.length() - 1; ++i) {
		std::cin >> t;
		d.push_back(t);
	}

	Takuzu tak(d);
	tak.solve();
	std::cout << tak;

	return 0;
}

bool Takuzu::solve() {
	bool changed = true;
	while (changed) {
		changed = check_double() || check_number() || check_repeat();
	}

	if (!isSolved())
		solveBF();
	return verify();
}

bool Takuzu::isSolved() const {
	for (auto row: data)
		for (auto sq: row)
			if (sq == Nothing)
				return false;
	return true;
}

bool Takuzu::check_double() {
	bool changed = false;
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getRow(i);
		for (size_t j = 0; j < N - 2; ++j) {
			if (res[j] == res[j + 1] && res[j] != Nothing && res[j + 2] == Nothing) {
				res[j + 2] = inverse(res[j]);
				changed = true;
			}

			else if (res[j] == res[j + 2] && res[j] != Nothing && res[j + 1] == Nothing) {
				res[j + 1] = inverse(res[j]);
				changed = true;
			}
		}
		for (size_t j = N - 1; j > 1; --j)
			if (res[j] == res[j - 1] && res[j] != Nothing && res[j - 2] == Nothing) {
				res[j - 2] = inverse(res[j]);
				changed = true;
			}

		if (changed)
			setRow(res, i);
	}

	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getColumn(i);
		for (size_t j = 0; j < N - 2; ++j) {
			if (res[j] == res[j + 1] && res[j] != Nothing && res[j + 2] == Nothing) {
				res[j + 2] = inverse(res[j]);
				changed = true;
			}

			else if (res[j] == res[j + 2] && res[j] != Nothing && res[j + 1] == Nothing) {
				res[j + 1] = inverse(res[j]);
				changed = true;
			}
		}
		for (size_t j = N - 1; j > 1; --j)
			if (res[j] == res[j - 1] && res[j] != Nothing && res[j - 2] == Nothing) {
				res[j - 2] = inverse(res[j]);
				changed = true;
			}

		if (changed)
			setColumn(res, i);
	}
	return changed;
}

bool Takuzu::check_number() {
	bool changed = false;
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getRow(i);
		if (std::count(res.begin(), res.end(), Zero) == N / 2 && std::count(res.begin(), res.end(), One) != N / 2) {
			for (auto &sq : res)
				if (sq == Nothing) {
					sq = One;
					changed = true;
				}
		}
		if (std::count(res.begin(), res.end(), One) == N / 2 && std::count(res.begin(), res.end(), Zero) != N / 2) {
			for (auto &sq : res)
				if (sq == Nothing) {
					sq = Zero;
					changed = true;
				}
		}
		if (changed)
			setRow(res, i);
	}

	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getColumn(i);

		if (std::count(res.begin(), res.end(), Zero) == N / 2 && std::count(res.begin(), res.end(), One) != N / 2) {
			for (auto &sq : res)
				if (sq == Nothing) {
					sq = One;
					changed = true;
				}
		}
		if (std::count(res.begin(), res.end(), One) == N / 2 && std::count(res.begin(), res.end(), Zero) != N / 2) {
			for (auto &sq : res)
				if (sq == Nothing) {
					sq = Zero;
					changed = true;
				}
		}
		if (changed)
			setColumn(res, i);
	}
	return changed;
}

bool Takuzu::check_repeat() {
	bool changed = false;
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getRow(i);
		if (std::count(res.begin(), res.end(), Nothing) == 2) {
			auto n1 = std::find(res.begin(), res.end(), Nothing), n2 = std::find(n1 + 1, res.end(), Nothing);
			size_t in1 = n1 - res.begin(), in2 = n2 - res.begin();
			for (size_t j = 0; j < N; ++j) {

				std::vector<Square> res2 = getRow(j);
				if (std::count(res2.begin(), res2.end(), Nothing) != 0)
					continue;
				bool same = true;
				for (size_t k = 0; k < N; ++k)
					if (res[k] != res2[k] && k != in1 && k != in2) {
						same = false;
						break;
					}
				if (!same)
					continue;
				res[in1] = inverse(res2[in1]);
				res[in2] = inverse(res2[in2]);
				changed = true;
				break;
			}
			if (changed)
				setRow(res, i);
		}
	}

	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getColumn(i);
		if (std::count(res.begin(), res.end(), Nothing) == 2) {
			auto n1 = std::find(res.begin(), res.end(), Nothing), n2 = std::find(n1 + 1, res.end(), Nothing);
			size_t in1 = n1 - res.begin(), in2 = n2 - res.begin();
			for (size_t j = 0; j < N; ++j) {

				std::vector<Square> res2 = getRow(j);
				if (std::count(res.begin(), res.end(), Nothing) != 0)
					continue;
				bool same = true;
				for (size_t k = 0; k < N; ++k)
					if (res[k] != res2[k] && k != in1 && k != in2) {
						same = false;
						break;
					}
				if (!same)
					continue;
				res[in1] = inverse(res2[in1]);
				res[in2] = inverse(res2[in2]);
				changed = true;
				break;
			}
		}

		if (changed)
			setColumn(res, i);
	}
	return changed;
}

bool Takuzu::solveBF() {
	std::vector<std::vector<Square>> sol = data;
	bool x = recursive_solve(sol);
	data = sol;
	return x;
}

bool Takuzu::verify() const {
	if (!isSolved())
		return false;
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getRow(i);
		if (std::count(res.begin(), res.end(), One) != N / 2 || std::count(res.begin(), res.end(), Zero) != N / 2)
			return false;
		for (size_t j = 0; j < N - 2; ++j)
			if (res[j] == res[j + 1] && res[j] == res[j + 2])
				return false;

		for (size_t j = i + 1; j < N; ++j)
			if (getRow(j) == res)
				return false;
	}
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = getColumn(i);
		if (std::count(res.begin(), res.end(), One) != N / 2 || std::count(res.begin(), res.end(), Zero) != N / 2)
			return false;
		for (size_t j = 0; j < N - 2; ++j)
			if (res[j] == res[j + 1] && res[j] == res[j + 2])
				return false;

		for (size_t j = i + 1; j < N; ++j)
			if (getColumn(j) == res)
				return false;
	}
	return true;
}

Takuzu::Takuzu(std::vector<std::string> s) {
	for (size_t i = 0; i < s.size(); ++i) {
		data.push_back(std::vector<Square>());
		for (size_t j = 0; j < s[i].length(); ++j)
			data[i].push_back(s[i][j] == '.' ? Nothing : s[i][j] == '0' ? Zero : One);
	}
	N = data.size();
}

Takuzu::Takuzu(std::vector<std::vector<Square>> d) {
	data = d;
	N = data.size();
}

std::vector<Square> Takuzu::getRow(int n) const {
	return data[n];
}

std::vector<Square> Takuzu::getColumn(int n) const {
	std::vector<Square> res;
	for (size_t i = 0; i < N; ++i)
		res.push_back(data[i][n]);
	return res;
}

size_t Takuzu::getSize() const {
	return N;
}

std::vector<std::vector<Square>> Takuzu::getData() const {
	return data;
}

void Takuzu::setRow(std::vector<Square> row, int n) {
	data[n] = row;
}

void Takuzu::setColumn(std::vector<Square> column, int n) {
	for (size_t i = 0; i < N; ++i)
		data[i][n] = column[i];
}

std::ostream &operator<<(std::ostream &os, const Takuzu &tk) {
	size_t N = tk.getSize();
	for (size_t i = 0; i < N; ++i) {
		std::vector<Square> res = tk.getRow(i);
		for (size_t j = 0; j < N; ++j)
			if (res[j] == Nothing)
				os << ".";
			else
				os << res[j];
		os << std::endl;
	}
	return os;
}

bool verify(std::vector<std::vector<Square>> &d) {
	return Takuzu(d).verify();
}

bool recursive_solve(std::vector<std::vector<Square>> &d) {
	if (verify(d))
		return true;
	std::vector<Square>::iterator next;
	for (size_t i = 0; i < d.size(); ++i) {
		next = std::find(d[i].begin(), d[i].end(), Nothing);
		if (next != d[i].end())
			break;
	}
	if (next == d[d.size() - 1].end())
		return false;
	*next = Zero;
	Takuzu tmp(d);
	if (tmp.solve()) {
		d = tmp.getData();
		return true;
	}

	*next = One;
	tmp = Takuzu(d);
	if (tmp.solve()) {
		d = tmp.getData();
		return true;
	}

	*next = Nothing;
	return false;
}