# SudokuΒΆ

#include <iostream>
#include <fstream>
#include <iterator>
#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
#include <string>
#include <cassert>

class Cell {
public:
Cell();
bool only_one() const;
int get_one() const;
bool valid() const;
bool eliminate(int i);
std::vector<int> get() const;
void set_value(int i);
bool has(int i) const;
int count() const;

private:
std::vector<int> values;
};

Cell::Cell() {
values = {1, 2, 3, 4, 5, 6, 7, 8, 9};
}

bool Cell::only_one() const {
return values.size() == 1;
}

int Cell::get_one() const {
if(!only_one()) {
throw std::runtime_error("get_one() called but multiple values exist");
}
return *values.begin();
}

bool Cell::valid() const {
return values.size() != 0;
}

int Cell::count() const {
return values.size();
}

bool Cell::eliminate(int i) {
values.erase(std::remove(values.begin(), values.end(), i), values.end());
return valid();
}

std::vector<int> Cell::get() const {
return values;
}

void Cell::set_value(int i) {
values.clear();
values.push_back(i);
}

bool Cell::has(int i) const {
return std::find(values.begin(), values.end(), i) != values.end();
}

class Puzzle {
public:
Puzzle(const std::vector<int> vec);
bool solved() const;
bool propagate(int i);
bool valid() const;
bool set_cell(int i, int value);
Puzzle search(bool& found) const;
void print() const;

private:
static std::vector<int> get_peers(int i);
static std::array<std::array<int, 9>, 3> get_units(int self);
static int get_index(int x, int y);
bool check_units(int index);
std::array<Cell, 81> cells;
};

Puzzle::Puzzle(const std::vector<int> vec) {
int i = 0;
for(const auto& v : vec) {
if(v >= 1 && v <= 9) {
bool ret = set_cell(i, v);
if(!ret) {
throw std::runtime_error("Invalid board");
}
i++;
} else {
i++;
}
if(i > 81) {
throw std::runtime_error("Too many values");
}
}
if(i != 81) {
throw std::runtime_error("Not enough values");
}
}

bool Puzzle::solved() const {
for(const auto& p : cells) {
if(!p.only_one()) {
return false;
}
}
return true;
}

bool Puzzle::set_cell(int i, int value) {
cells.at(i).set_value(value);
return propagate(i);
}

Puzzle Puzzle::search(bool& found) const {
std::vector<int> open;
if(solved()) {
found = true;
return *this;
}

for(int i = 0; i < 81; i++) {
if(!cells.at(i).valid()) {
found = false;
return *this;
}
if(!cells.at(i).only_one()) {
open.push_back(i);
}
}

std::sort(open.begin(), open.end(),
[&](int i1, int i2) {
return cells.at(i1).count() <
cells.at(i2).count();
});

auto o = open.at(0);
auto values = cells.at(o).get();
for(auto v : values) {
Puzzle alt = *this;
bool ret = alt.set_cell(o, v);
if(ret) {
bool alt_found;
alt = alt.search(alt_found);
if(alt_found) {
found = true;
return alt;
}
}
}
found = false;
return *this;
}

void Puzzle::print() const {
bool s = solved();
for(int i = 0; i < 81; i++) {
if(s) {
printf("%d", cells.at(i).get_one());
} else {
for(int v = 1; v <= 9; v++) {
if(cells.at(i).has(v)) {
printf("%d", v);
} else {
printf(" ");
}
}
printf(" ");
}
if(i % 9 == 8) {
printf("\n");
if(i % 27 == 26) {
printf("---\n");
}
} else if(i % 3 == 2) {
printf("|");
}
}
printf("\n");
}

bool Puzzle::propagate(int i) {
const auto& p = cells.at(i);

auto one = p.get_one();
auto peers = Puzzle::get_peers(i);
for(const auto& peer : peers) {
if(cells.at(peer).has(one)) {
bool still_valid = cells.at(peer).eliminate(one);
if(!still_valid)
return false;
bool has_one = cells.at(peer).only_one();
if(has_one) {
bool ret = propagate(peer);
if(!ret)
return false;
}
bool ret = check_units(peer);
if(!ret)
return false;
}
}
return true;
}

bool Puzzle::check_units(int index) {
auto units = get_units(index);
for(const auto& unit : units) {
for(int i = 1; i <= 9; i++) {
int found = -1;
for(auto peer : unit) {
if(cells[peer].has(i)) {
if(found != -1) {
found = -1;
break;
}
found = peer;
}
}
if(found != -1) {
bool ret = set_cell(found, i);
if(!ret)
return false;
}
}
}
return true;
}

std::array<std::array<int, 9>, 3> Puzzle::get_units(int self) {
std::array<std::array<int, 9>, 3> ret;

int col = self % 9;
for(int i = 0; i < 9; i++) {
int ind = Puzzle::get_index(col, i);
ret[0][i] = ind;
}

int row = self / 9;
for(int i = 0; i < 9; i++) {
int ind = Puzzle::get_index(i, row);
ret[1][i] = ind;
}

int xc = row / 3;
int yc = col / 3;
for(int j = 0; j < 3; j++) {
for(int i = 0; i < 3; i++) {
int ind = Puzzle::get_index(i + yc * 3, j + xc * 3);
ret[2][i * 3 + j] = ind;
}
}

return ret;
}

bool Puzzle::valid() const {
for(const auto& p : cells) {
if(!p.valid())
return false;
}
return true;
}

std::vector<int> Puzzle::get_peers(int self) {
std::vector<int> ret;
auto val = get_units(self);
for(auto& v : val) {
for(auto& i : v) {
ret.push_back(i);
}
}

ret.erase(std::remove(ret.begin(), ret.end(), self), ret.end());

return ret;
}

int Puzzle::get_index(int x, int y) {
assert(x < 9);
assert(y < 9);
return y * 9 + x;
}

int main(int argc, char** argv)
{
std::ifstream ifs(argv[1]);
std::string contents((std::istreambuf_iterator<char>(ifs)),
(std::istreambuf_iterator<char>()));

std::vector<Puzzle> puzzles;

int buf_location = 0;
std::vector<int> my_buf;
for(auto c : contents) {
if(c >= '1' && c <= '9') {
my_buf.push_back(c - '0');
buf_location++;
} else if(c == '.' || c == '0') {
my_buf.push_back(0);
buf_location++;
}
if(buf_location == 81) {
puzzles.push_back(Puzzle(my_buf));
my_buf.clear();
buf_location = 0;
}
}

for(auto& p : puzzles) {
if(!p.valid()) {
std::cerr << "Not valid\n";
} else {
bool found;
p = p.search(found);
std::cout << "Solved: " << found << "\n";
}
p.print();
}

return 0;
}