#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <numeric>
#include <string>
#include <string_view>
#include <vector>

#include "SudokuSolver.h"

int main()
{
    std::string testSudoku1 =
    {
        "080090030030000069902063158020804590851907046394605870563040987200000015010050020" //MEDIUM SUDOKU
    };
    std::string testSudoku2 =
    {
        "001700806070000215000020000307040008000080000800060709000010000298000060706005300" //EASY SUDOKU
    };
    std::string testSudoku3 =
    {
        "075001002000000009090027040000094300000000000003810000030760010900000000600400580" //MEDIUM SUDOKU
    };
    std::string testSudoku4 =
    {
        "506000700010300000700050800000000020000070608000102040800090006030004000065000000" //EXTREME
    };
    std::string testSudoku5 =
    {
        "900784500700000930000001000080000006079030480300000070000200000065000004007468003" //EXTREME
    };
    std::string testSudoku6 =
    {
        "907000003000807000005003700040902050090060080010408020004200800000306000300000206" //EXTREME
    };
    std::string testSudoku7 =
    {
        "927000003000807000005003700040902050090060080010408020004200800000306000300000206" //INVALID BOARD
    };
    std::string testSudoku8 =
    {
        "0000000000000000"        //4x4 EMPTY SUDOKU
    };

    std::string testSudoku9 =
    {
        "000000010002000034000051000000006500070300080003000000000080000580000900690000000"        //HYPERSUDOKU SUDOKU
    };
    std::vector<std::vector<short>> areasHyper(4, std::vector<short>(9));  //HYPERSUDOKU AREAS
    areasHyper[0] = { 10, 11, 12, 19, 20, 21, 28, 29, 30 };
    areasHyper[1] = { 14, 15, 16, 23, 24, 25, 32, 33, 34 };
    areasHyper[2] = { 46, 47, 48, 55, 56, 57, 64, 65, 66 };
    areasHyper[3] = { 50, 51, 52, 59, 60, 61, 68, 69, 70 };

    std::string testSudoku10 =
    {
        "300000004002060100010908020005000600020000010009000800080304060004010900500000007"        //NONOMINO SUDOKU
    };
    std::vector<std::vector<short>> areasN(9, std::vector<short>(9));  //NONOMINO AREAS, DISABLE BOXES WHEN SOLVING
    areasN[0] = { 0, 1, 2, 9, 10, 11, 18, 27, 28 };
    areasN[1] = { 3, 12, 13, 14, 23, 24, 25, 34, 35 };
    areasN[2] = { 4, 5, 6, 7, 8, 15, 16, 17, 26 };
    areasN[3] = { 19, 20, 21, 22, 29, 36, 37, 38, 39 };
    areasN[4] = { 30, 31, 32, 33, 40,  47, 48, 49, 50 };
    areasN[5] = { 41, 42, 43, 44, 51, 58, 59, 60, 61 };
    areasN[6] = { 45, 46, 55, 56, 57, 66, 67, 68, 77 };
    areasN[7] = { 54, 63, 64, 65, 72, 73, 74, 75, 76 };
    areasN[8] = { 52, 53, 62, 69, 70, 71, 78, 79, 80 };

    std::string testSudoku11 =
    {
        "400805200000000000080070000000208907000000004105300000000000010000000000001007006"        //X SUDOKU
    };

    std::vector<std::vector<short>> areasX(2, std::vector<short>(9)); //X AREAS

    areasX[0] = { 0, 10, 20, 30, 40, 50, 60, 70, 80 };
    areasX[1] = { 8, 16, 24, 32, 40, 48, 56, 64, 72 };

    /*std::string sudoku; //TO GET A SUDOKU FROM INPUT

    std::cout << "For empty cells type 0, without spaces" << std::endl;
    std::cout << "Input row 1 : ";
    std::cin >> sudoku;

    int nRows = sudoku.length();

    for (int i = 1; i < nRows; i++)
    {
        std::string row;

        std::cout << "Input row " << i + 1 << " : ";
        std::cin >> row;
        sudoku += row;
    }

    SudokuSolver solver(sudoku); */

    SudokuSolver solver(testSudoku4);  //SOLVE A TEST SUDOKU

    int status = solver.solve();
    if (status == 1)
    {
        std::cout << "SOLVED" << std::endl;
    }
    else if (status == 0)
    {
        std::cout << "ERROR ON THE BOARD" << std::endl;
    }

    std::cout << std::endl << solver << std::endl;

    /*int nSolves = 1000;  BENCHMARKING CODE

    auto t0 = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < nSolves; i++)
    {
        solver.solve();
    }

    auto t1 = std::chrono::high_resolution_clock::now();

    auto time = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();

    std::cout << "Solving took " << time << " microsecs" << std::endl;
    std::cout << "Average solving time : " << (time) / nSolves << " microsecs" << std::endl;*/

    return 0;
}

enum class SudokuProgress : short
{
    PROGRESS,
    NO_PROGRESS,
    CONFLICT
};


class Cell
{
private:
    std::vector<short> candidates;

    short num;
public:
    Cell(short maxCand) : candidates(maxCand), num(0)
    {
        std::iota(candidates.begin(), candidates.end(), 1);
    }

    Cell(short n, short maxCand) : num(n) {}

    const auto& getCandidates() const //CALL ONLY IF NOT SOLVED
    {
        return candidates;
    }

    void resetCands()
    {
        candidates.clear();
    }

    void setNum(int n)
    {
        num = n;
    }

    short getNum() const
    {
        return num;
    }

    short candidatesCount() const //CALL ONLY IF NOT SOLVED
    {
        return candidates.size();
    }

    bool empty() const
    {
        return num == -1;
    }

    SudokuProgress removeCandidate(short n)
    {
        if (!solved())
        {
            if (auto it = std::find(candidates.begin(), candidates.end(), n); it != candidates.end())
            {
                std::iter_swap(it, candidates.end() - 1);
                candidates.pop_back();

                if (candidates.size() == 1)
                {
                    num = candidates[0];
                }

                return SudokuProgress::PROGRESS;
            }
        }
        else if (num == n)
        {
            num = -1;
            return SudokuProgress::CONFLICT;
        }

        return SudokuProgress::NO_PROGRESS;
    }

    bool solved() const
    {
        return num > 0;
    }

    friend std::ostream& operator<<(std::ostream& os, const Cell& cell)
    {
        os << cell.getNum();
        return os;
    }
};

#include "Cell.h"

typedef std::vector<Cell>::iterator cellIt;
typedef short cellIndex;

typedef short ContID;
typedef std::vector<short> uniqueContainer;

struct uniqueContainers : std::vector<uniqueContainer>
{
    const ContID id;

    uniqueContainers(const int& nConts, const int& contSize, const ContID& i) : std::vector<uniqueContainer>(nConts, uniqueContainer(contSize)), id(i) {}

    uniqueContainers(const int& nConts, const int& contSize) : uniqueContainers(nConts, contSize, -1) {}
};

class SudokuBoard : std::vector<Cell>
{
private:
    static std::vector<uniqueContainers> uniqueConts; //UNIQUE CONTAINERS(ROWS; COLUMNS AND BOXES)
    static short side;

    static std::vector<short> contIndices;

    short solvedCells;

    static void initUniqueConts(bool box = true)  //INITIALIZES DEFAULT UNIQUE CONTAINERS
    {
        uniqueConts.clear();

        uniqueConts.emplace_back(side, side, 0); //ROWS
        uniqueConts.emplace_back(side, side, 1); //COLUMNS
        if (box)
        {
            uniqueConts.emplace_back(side, side, 2); //BOXES
        }

        uniqueContainers& rows = uniqueConts[0];
        uniqueContainers& columns = uniqueConts[1];

        for (int i = 0; i < side; i++)
        {
            for (int j = 0; j < side; j++)
            {
                rows[i][j] = side * i + j;
                columns[j][i] = side * i + j;
            }
        }

        if (box)
        {
            uniqueContainers& boxes = uniqueConts[2];
            int boxSize = sqrt(side);

            for (int i = 0; i < side; i++)
            {
                for (int j = 0; j < boxSize; j++)
                {
                    const uniqueContainer& row = rows[(i / boxSize) * boxSize + j];

                    int rowOffset = i % boxSize * boxSize;

                    std::copy(row.begin() + rowOffset, row.begin() + (rowOffset + boxSize), boxes[i].begin() + j * boxSize);
                }
            }
        }
    }

    static void addUniqueConts(const uniqueContainers& unique)
    {
        uniqueConts.emplace_back(unique.size(), unique[0].size(), uniqueConts.back().id + 1);

        std::copy(unique.begin(), unique.end(), uniqueConts.back().begin());
    }
public:
    SudokuBoard() {}

    SudokuBoard(const SudokuBoard& other)
    {
        solvedCells = other.solvedCells;
        this->reserve(side*side);

        for (auto& cell : other)
        {
            if (cell.solved())
            {
                this->emplace_back(cell.getNum(), side);
            }
            else
            {
                this->push_back(cell);
            }
        }
    }

    SudokuBoard(SudokuBoard&& other) : std::vector<Cell>(std::move(other)), solvedCells(other.solvedCells) {}

    void initCells(std::string_view boardStr) //CALL ONLY AFTER INITIALIZING UNIQUE CONTAINERS
    {
        side = sqrt(boardStr.length());
        contIndices.resize(boardStr.length()*uniqueConts.size());

        std::fill(contIndices.begin(), contIndices.end(), -1);

        for (int i = 0; i < boardStr.length(); i++)
        {
            short n = boardStr[i] - '0';

            for (const uniqueContainers& uniqueCont : uniqueConts)
            {
                for (int j = 0; j < uniqueCont.size(); j++)
                {
                    if (std::find(uniqueCont[j].begin(), uniqueCont[j].end(), i) != uniqueCont[j].end())
                    {
                        contIndices[i + uniqueCont.id * boardStr.length()] = j;
                        break;
                    }
                }
            }

            if (n == 0)
            {
                this->emplace_back(side);
            }
            else
            {
                this->emplace_back(n, side);
                solvedCells++;
            }
        }
    }

    short& getContIndex(const cellIndex& cellIndex, const ContID& uniqueContIndex) const
    {
        return contIndices[cellIndex + uniqueContIndex * this->size()];
    }

    bool solved() const
    {
        return solvedCells == this->size();
    }

    friend std::ostream& operator<<(std::ostream& os, const SudokuBoard& board)
    {
        for (int i = 0; i < side; i++)
        {
            for (int j = 0; j < side; j++)
            {
                if (board[j + board.side * i].solved())
                {
                    os << board[j + side * i];
                }
                else
                {
                    os << '0';
                }

                os << " ";
            }

            if (i < side - 1)
                os << std::endl;
        }

        return os;
    }

    friend class SudokuSolver;
};


std::vector<short> SudokuBoard::contIndices;
std::vector<uniqueContainers> SudokuBoard::uniqueConts;
short SudokuBoard::side;

#include "SudokuBoard.h"

class SudokuSolver
{
private:
    SudokuBoard startBoard;

    int totalBoards;
    bool uniqueSol;

    std::vector<SudokuBoard> solutions;

    SudokuProgress removeCandidate(SudokuBoard& board, const int &eraser, const uniqueContainer& cont, std::vector<cellIndex>& nextCheck) //ERASER MUST BE A SOLVED CELL
    {
        SudokuProgress status = SudokuProgress::NO_PROGRESS;

        for (const cellIndex& cell : cont)
        {
            if (cell != eraser)
            {
                SudokuProgress progress = board[cell].removeCandidate(board[eraser].getNum());

                if (progress == SudokuProgress::PROGRESS) //removeCandidate(int) INSIDE CELL; NOT RECURSIVE
                {
                    if (board[cell].solved()) //CHECK FOR SOLVED CELLS
                    {
                        nextCheck.push_back(cell);
                        board.solvedCells++;

                        status = SudokuProgress::PROGRESS;
                    }
                }
                else if (progress == SudokuProgress::CONFLICT) //INVALID BOARD
                {
                    return SudokuProgress::CONFLICT;
                }
            }
        }

        return status;
    }

    SudokuProgress removeConflicts(SudokuBoard& board, std::vector<cellIndex>& toCheck) //REMOVE ILLEGAL CANDIDATES FROM CELLS
    {
        SudokuProgress status = SudokuProgress::NO_PROGRESS;

        std::vector<cellIndex> check(std::move(toCheck));
        toCheck.reserve(check.size());

        for (const uniqueContainers& uniqueConts : board.uniqueConts)
        {
            for (const cellIndex& cell : check)
            {
                int contIndex = board.getContIndex(cell, uniqueConts.id);

                if (contIndex != -1)
                {
                    SudokuProgress solvedCount = removeCandidate(board, cell, uniqueConts[contIndex], toCheck);

                    if (solvedCount == SudokuProgress::PROGRESS)
                    {
                        status = SudokuProgress::PROGRESS;
                    }
                    else if (solvedCount == SudokuProgress::CONFLICT)
                        return SudokuProgress::CONFLICT;
                }
            }
        }

        return status;
    }

    bool solve(SudokuBoard board, std::vector<cellIndex> toCheck)
    {
        bool solved = false;

        while (true)
        {
            SudokuProgress status = SudokuProgress::NO_PROGRESS;

            do
            {

                status = removeConflicts(board, toCheck);

            } while (status == SudokuProgress::PROGRESS);

            if (status == SudokuProgress::CONFLICT)
            {
                break;
            }

            if (board.solved())
            {
                solutions.emplace_back(std::move(board));

                return true;
            }
            else
            {
                cellIt leastCands = board.begin();

                for (auto cell = leastCands + 1; cell != board.end(); ++cell)
                {
                    if (!cell->solved())
                    {
                        if (cell->candidatesCount() < leastCands->candidatesCount() || leastCands->solved())
                        {
                            leastCands = cell;
                        }
                    }
                }

                toCheck.push_back(leastCands - board.begin()); //toCheck IS GUARANTEED TO BE EMPTY BEFORE THIS LINE

                board.solvedCells++;

                auto& cands = leastCands->getCandidates();

                for (auto cand = cands.begin(); cand != cands.end() - 1; ++cand)
                {
                    totalBoards++;

                    leastCands->setNum(*cand);

                    if (solve(board, toCheck))
                    {
                        solved = true;

                        if (uniqueSol)
                            return true;
                    }
                }

                leastCands->setNum(cands.back());
            }
        }

        return solved;
    }

public:
    SudokuSolver(std::string_view boardStr) : totalBoards(0)
    {
        SudokuBoard::side = sqrt(boardStr.length());
        SudokuBoard::initUniqueConts();

        startBoard.initCells(boardStr);
    }

    SudokuSolver(std::string_view boardStr, const std::vector<uniqueContainers>& areas, bool boxes = true) : totalBoards(0)
    {
        SudokuBoard::side = sqrt(boardStr.length());
        SudokuBoard::initUniqueConts(boxes);
        for (const auto& area : areas)
        {
            SudokuBoard::addUniqueConts(area);
        }

        startBoard.initCells(boardStr);
    }

    int solve(bool uniqueSolution = false)
    {
        uniqueSol = uniqueSolution;
        std::vector<cellIndex> toCheck;

        for (auto cell = startBoard.begin(); cell != startBoard.end(); ++cell)
        {
            if (cell->solved())
            {
                toCheck.push_back(cell - startBoard.begin());
            }
        }

        totalBoards++;
        return solve(startBoard, std::move(toCheck));
    }

    friend std::ostream& operator<<(std::ostream& os, const SudokuSolver& solver)
    {
        os << "TESTED " << solver.totalBoards << " BOARDS" << std::endl;

        if (solver.uniqueSol)
        {
            os << "FIRST SOLUTION FOUND" << std::endl;
        }
        else
        {
            os << solver.solutions.size() << " SOLUTIONS FOUND" << std::endl;
        }

        for (const auto& sol : solver.solutions)
            os << sol << std::endl << std::endl;

        os << "INITIAL BOARD " << std::endl << solver.startBoard << std::endl;

        return os;
    }
};