//
//  Gecode-SudokuSolver - Solves any 9x9 sudoku-board.
//
#include <iostream>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <gecode/search.hh>
#include <fstream>
#include <iomanip>      // std::setw
#include <random>
std::random_device rd;
std::default_random_engine gen(rd());
std::uniform_int_distribution<int> dist(1, 81);

using namespace Gecode;
int board[81];

void readFromFile() {       // Load sudoku from file into board.

    std::ifstream innfil;
    innfil.open("SolvedSudoku.txt");

    if (innfil.is_open()) {
        while (!innfil.eof()) {
            for (int i = 0; i < 81; i++) {
                innfil >> board[i];
            }
        }
    }
    innfil.close();
}


class Sudoku : public Space {
protected:
    IntVarArray l;

public:
    Sudoku(void) : l(*this, 81, 1, 9) {


    }

    void fill() {
        // Read sudoku from board
        for (int i = 0; i < 81; i++) {
            if (board[i] != 0) {                        // Copy if value is not zero
                rel(*this, l[i], IRT_EQ, board[i]);
            }
        }
        this->printBoard();
    }

    void deleteOne() {
        int r = dist(gen);
        std::cout << r << std::endl;
        IntVar i(*this, 1, 9);
        rel(*this, l[r], IRT_EQ, i);

        this->printBoard();
    }

    void checkUnique() {
        // Checks for "uniqueness" in the 9x9 grid, for each value in the row and column
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                for (int k = 0; k < 9; k++) {
                    rel(*this, l[i + 9 * k] != l[j + 9 * k]); // check rows
                    rel(*this, l[9 * i + k] != l[9 * j + k]); // check columns
                }
            }
        }

        // Checks the smaller 3*3 grids within the sudoku board
        for (int x = 0; x < 3; x++) {
            for (int y = x + 1; y < 3; y++) {
                for (int z = 0; z < 3; z++) {  // Check only current part of board
                    rel(*this, l[x + 3 * z] != l[y + 3 * z]);   // check rows
                    rel(*this, l[3 * x + z] != l[3 * y + z]);   // check collumns
                }
            }
        }

        branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
    }

    Sudoku(Sudoku& s) : Space(s) {
        l.update(*this, s.l);
    }

    virtual Space* copy() {
        return new Sudoku(*this);
    }

    void print(void) const {
        for (int i = 0; i < 81; i++) {
            if (!(i % 9)) {
                std::cout << std::endl;
            }
            std::cout << std::setw(13) << l[i] << " ";

        }
    }

    void printBoard(void) const {
        for (int i = 0; i < 81; i++) {
            if (!(i % 9)) {
                std::cout << std::endl;
            }
            std::cout << l[i] << " ";
        }
        std::cout << std::endl;
    }

};




int main(int argc, char* argv[])
{
    readFromFile();

    try {
        Sudoku* m = new Sudoku;
        std::cout << "The contents of the sudokuboard before search begins:" << std::endl;
        m->printBoard();

        // DFS = depth first search
        DFS<Sudoku> e(m);
        delete m;

        // We loop through all solutions to the constraint problem
        int count = 0;
        while (Sudoku* s = e.next()) {
            s->fill();
            s->deleteOne();

            s->checkUnique();
            //std::cout << std::endl << std::endl << "The contents of the sodukoboard after search is finished:" << std::endl;
            //s->printBoard();
            count++;
            delete s;
        }
        if (count == 0) {
            std::cout << std::endl << "The puzzle has no solutions" << std::endl;
        }
        else if (count == 1) {
            std::cout << std::endl << "The puzzle has one solution" << std::endl;
        }
        else if (count > 1) {
            std::cout << std::endl << "The puzzle has " << count << " solutions" << std::endl;
        }
    }
    catch (Exception e) {
        std::cerr << "Gecode Exception: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}