dgh

/*
Suduko Solver
by someone

examples of sudoku available at http://magictour.free.fr/top1465
*/

#include <iostream>
#include <string>
//#include <array>
#include <algorithm>
#include <exception>
#include <cctype>
#include <vector>
#include <memory>

class InitNbrSudokuError : public std::runtime_error
{
public :

    InitNbrSudokuError(std::string str) : std::runtime_error(str) {}

    enum TypeErr
    {
        err_alloc
    };

    TypeErr getErrType()
    {
        return err_alloc;
    }
};

class NbrSudoku
{
public :

    NbrSudoku();
    void init(int val);

    NbrSudoku(const NbrSudoku& val);

    int getNbr() const;
    std::vector<int>& getVec() const;

    bool isValid() const;

    void addLittleNbr(int val);

    void putOffLitteNbr(int val);

    void set(int val);

    void setIfOnlyOne();

private :

    int nbr;

    std::unique_ptr<std::vector<int>> listInt;
};

std::ostream& operator<<(std::ostream& outuput, NbrSudoku a);
//external overloading lul

NbrSudoku::NbrSudoku()
{
    listInt = nullptr;
}

NbrSudoku::NbrSudoku(const NbrSudoku& val)
{
    nbr = val.nbr;

    try
    {
        listInt = std::unique_ptr<std::vector<int>>(new std::vector<int> {val.getVec()});
    }
    catch (const InitNbrSudokuError& e)
    {
        listInt = std::unique_ptr<std::vector<int>>(new std::vector<int> {});
    }
}

void NbrSudoku::addLittleNbr(int val)
{
    listInt->push_back(val);
}

int NbrSudoku::getNbr() const
{
    return nbr;
}

bool NbrSudoku::isValid() const
{
    if(nbr == 0)
    {
        return false; //the vector is used
    }
    else
    {
        return true;
    }
}

std::vector<int>& NbrSudoku::getVec() const
{
    if(listInt != nullptr)
    {
        return *listInt;
    }
    else
    {
        throw InitNbrSudokuError("There aren't any vector to give here, sorry");
    }
}

void NbrSudoku::init(int val)
{
    nbr = val;

    if(nbr == 0) //if the case is empty
    {
        listInt = std::unique_ptr<std::vector<int>>(new std::vector<int> {}) ;
    }
}

std::ostream& operator<<(std::ostream& outuput, NbrSudoku a)
{
    if(a.isValid())
    {
        outuput << a.getNbr();
    }
    else
    {
        for(unsigned int i = 0; i < a.getVec().size() ; i++)
        {
            outuput << a.getVec()[i] << " ";
        }
    }

    return outuput;
}

void NbrSudoku::putOffLitteNbr(int val)
{
    std::vector<int>::iterator listVirer {std::find_if(listInt->begin(), listInt->end(), [val](int val_) -> bool {return val == val_;})};

    if(listVirer != listInt->end())
    {
        listInt->erase(listVirer);
    }
}

void NbrSudoku::set(int val)
{
    if(val >= 0 && val <= 10)
    {
        nbr = val;
    }
}

class Sudoku
{
public :

    Sudoku(std::string sentence);

    std::string toString();

    bool isValid();

    void addLittleNbrEveywhere();
    void addLittleNbrForOne(int x, int y);

    void addBigNbr(int x, int y, int val);

    std::ostream& coutLittleNbr(std::ostream& prut);
    std::ostream& coutLittleNbrInGrid(std::ostream& prut);
    std::ostream& coutOneLittleNbrInGrid(std::ostream& prut, int nbr);

    void solve(); //c'est si symple que ça

    bool setIfOnlyOne();
    bool setIfOnlyOneOnThisBloc();
    bool setIfOnlyOneLineRowCase();

private :

    std::vector<std::vector<NbrSudoku>> listNbr;
    //Wide spaces are saved into 0
};

Sudoku::Sudoku(std::string sentence)
{
    listNbr  = std::vector<std::vector<NbrSudoku>>
                {9, std::vector<NbrSudoku>
                    {9, NbrSudoku {/* default constructor */}   }  };

    if(sentence.size() != 81 ||
        !std::any_of(sentence.begin(), sentence.end(), [](char a) -> bool
            {
                if(!isdigit(a) || a != '.')
                {
                    return true;
                }

                return false;
            }) )
    {
        throw std::runtime_error("This isn't a valid input");
    }

    for(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        for(unsigned int j = 0; j < listNbr[i].size() ; j++)
        {
            char nbr = sentence[i * 9 + j];

            if(isdigit(nbr))
            {
                listNbr[i][j].init(nbr - '0');
            }
            else if(nbr == '.')
            {
                listNbr[i][j].init(0);
            }
            else
            {
                throw std::runtime_error("Something went wrong");
            }
        }
    }
}

std::string Sudoku::toString()
{
    std::string output;

    for(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        if(i % 3 == 0)
        {
            output += "+ - - - + - - - + - - - +\n";
        }

        for(unsigned int j = 0 ; j < listNbr.size() ; j++)
        {
            if(j % 3 == 0)
            {
                output += "| ";
            }

            if(listNbr[i][j].getNbr() == 0)
            {
                output += ".";
            }
            else
            {
                output += std::to_string(listNbr[i][j].getNbr());
            }

            output += " ";
        }
        output += "|\n";
    }

    output += "+ - - - + - - - + - - - +\n";

    return output;
}

bool Sudoku::isValid()
{


    //try for each ligne
    for(unsigned int i = 0 ; i < listNbr.size() ; i++)
    {
        std::vector<int> listFind;

        for(unsigned int j = 0 ; j < listNbr[i].size() ; j++)
        {
            int val = listNbr[i][j].getNbr();

            listFind.push_back(val);

            if(any_of(listFind.begin(), listFind.end(),
                [val](int nbrTest) -> bool
                {
                    return nbrTest == val;
                }))
            {
                //the "pitu" come back
                std::cout << "pitu" << std::endl;

                return false;
            }
        }

        if(listFind.size() != 9)
        {
            return false;
        }
    }

    //try for each row
    for(unsigned int i = 0 ; i < listNbr[0].size() ; i++)
    {
        std::vector<int> listFind;

        for(unsigned int j = 0 ; j < listNbr.size() ; j++)
        {
            int val {listNbr[j][i].getNbr()};

            listFind.push_back(val);

            if(std::any_of(listFind.begin(), listFind.end(),
                [val](int nbrTest) -> bool
                {
                    return nbrTest == val;
                }))
            {
                std::cout << "pruti" << std::endl;
                return false; //salut ca va
            }
        }

        if(listFind.size() != 9)
        {
            return false;
        }
    }

    //the hard part : the cases
    for(unsigned int nbrCase = 0; nbrCase < 9 ; nbrCase++)
    {
        std::vector<int> listFind;
        for(unsigned int i = nbrCase % 3 * 3; i < (nbrCase) % 3 * 3 + 3; i++)
        {
            std::vector<int> listFind;

            for(unsigned int j = nbrCase / 3 * 3; j < (nbrCase) / 3 * 3 + 3; j++)
            {
                int val {listNbr[j][i].getNbr()};

                listFind.push_back(val);

                if(std::any_of(listFind.begin(), listFind.end(),
                    [val](int nbrTest) -> bool
                    {
                        return nbrTest == val;
                    }))
                {
                    std::cout << "pruti" << std::endl;
                    return false; //salut ca va
                }
            }
        }
    }

    return true;
}

bool ifIsNotInVect(int valTest, std::vector<int> v)
{
    return !isInVect(valTest, v);
}

bool isInVect(int valTest, std::vector<int> v)
{
    return std::find(v.begin(), v.end(), valTest) != v.end();
}

void Sudoku::addLittleNbrForOne(int x, int y)
{
    std::vector<int> nbrFind;

    for(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        if(listNbr[i][y].getNbr() != 0 && ifIsNotInVect(listNbr[i][y].getNbr(), nbrFind) )
        {
            nbrFind.push_back(listNbr[i][y].getNbr());
        }
    }

    //for each line
    for(unsigned int j = 0; j < listNbr[x].size() ; j++)
    {
        if(listNbr[x][j].getNbr() != 0 && ifIsNotInVect(listNbr[x][j].getNbr(), nbrFind))
        {
            nbrFind.push_back(listNbr[x][j].getNbr());
        }
    }

    //for each case
    int nbrCase = (x / 3) * 3 + (y / 3);

    std::cout << nbrCase << " " << x << " " << y <<  " " << listNbr[x][y].getNbr() << std::endl;

    for(unsigned int i = nbrCase % 3 * 3; i < (nbrCase) % 3 * 3 + 3; i++)
    {
        std::vector<int> listFind;

        for(unsigned int j = nbrCase / 3 * 3; j < (nbrCase) / 3 * 3 + 3; j++)
        {
            if(listNbr[j][i].getNbr() != 0 && ifIsNotInVect(listNbr[j][i].getNbr(), nbrFind))
            {
                nbrFind.push_back(listNbr[j][i].getNbr());
            }

            //std::cout << listNbr[j][i].getNbr() << " ";
        }
    }

    std::cout << std::endl;

    for(int i = 1; i <= 9; i++)
    {
        if(std::count(nbrFind.begin(), nbrFind.end(), i) == 0)
        {
            listNbr[x][y].addLittleNbr(i);
        }
    }
}

void Sudoku::addLittleNbrEveywhere()
{
    for(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        for(unsigned int j = 0; j < listNbr[i].size() ; j++)
        {
            if(listNbr[i][j].getNbr() == 0)
            {
                addLittleNbrForOne(i, j);
            }
        }
    }
}

void Sudoku::addBigNbr(int x, int y, int val)
{
    listNbr[x][y].set(val);

    for(int i = 0; i < listNbr.size() ; i++)
    {
        listNbr[i][y].putOffLitteNbr(val);
    }

    for(int j = 0; j < listNbr[x].size(); j++)
    {
        listNbr[x][j].putOffLitteNbr(val);
    }

    int nbrCase = (x / 3) * 3 + (y / 3);

    for(int i = nbrCase % 3 * 3; i < (nbrCase) % 3 * 3 + 3; i++)
    {
        for(int j = (nbrCase) / 3 * 3; j < (nbrCase) / 3 * 3 + 3; j++)
        {
            listNbr[j][i].putOffLitteNbr(val);
        }
    }
}

std::ostream& Sudoku::coutLittleNbr(std::ostream& prut)
{
    for(unsigned int i = 0 ; i < listNbr.size() ; i++)
    {
        for(unsigned int j = 0 ; j < listNbr[i].size() ; j++)
        {
            prut << listNbr[i][j] << std::endl;
        }
        prut << std::endl;
    }
    return prut;
}

void Sudoku::solve()
{
    bool haveAChange {true};

    while(haveAChange)
    {
        haveAChange = false;

        haveAChange = setIfOnlyOne();

        haveAChange = setIfOnlyOneLineRowCase()
    }
}

bool Sudoku::setIfOnlyOne()
{
    bool haveAChange {false};

    for(int i = 0; i < listNbr.size(); i++)
    {
        for(int j = 0 ; j < listNbr[i].size(); j++)
        {
            if(listNbr[i][j].isValid() && listNbr[i][j].getVec().size() == 1)
            {
                addBigNbr(i, j, listNbr[i][j].getVec().front());
                haveAChange = true;
            }
        }
    }

    return haveAChange;
}

bool Sudoku::setIfOnlyOneLineRowCase()
{
    bool haveAChange {false};

    for(int nbrTest = 1; nbrTest <= 9; nbrTest++)
    {
        for(int i = 0; i < listNbr.size(); i++)
        {
            int find = 0;

            for(int j = 0; j < listNbr[i].size(); j++)
            {
                if(isInVect(nbrTest, listNbr[i][j].getVec()) )
                {
                    find++;
                }
            }

            if(find == 1)
            {
                for(int j = 0; j < listNbr[i].size(); j++)
                {
                    if(isInVect(nbrTest, listNbr[i][j].getVec()) )
                    {
                        addBigNbr(i, j, nbrTest);
                    }
                }
            }
        }
    }
}

bool Sudoku::setIfOnlyOneOnThisBloc()
{
    int nbreLittleCase = 0;

    for(int nbrCase = 0; nbrCase < 9; nbrCase++)
    {
        std::vector<int> listPossibility {9, 0};

        nbreLittleCase++;

        for(int i = nbrCase % 3 * 3; i < (nbrCase) % 3 * 3 + 3; i++)
        {
            for(int j = (nbrCase) / 3 * 3; j < (nbrCase) / 3 * 3 + 3; j++)
            {
                if(listNbr[j][i].isValid())
                {
                    listPossibility[listNbr[j][i].getNbr()]++;
                }
                else
                {
                    for(int k = 0; k < listNbr[j][i].getVec().size(); k++)
                    {
                        listPossibility[listNbr[j][i].getVec()[k]]++;
                    }
                }
            }
        }


    }
}


std::ostream& Sudoku::coutLittleNbrInGrid(std::ostream& prut)
{
    for(int i = 1; i <= 9; i++)
    {
        coutOneLittleNbrInGrid(prut, i);
        prut << std::endl << std::endl;
    }
}

std::ostream& Sudoku::coutOneLittleNbrInGrid(std::ostream& output, int nbr)
{
    for(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        if(i % 3 == 0)
        {
            output << "+ - - - + - - - + - - - +" << std::endl;
        }

        for(unsigned int j = 0 ; j < listNbr.size() ; j++)
        {
            if(j % 3 == 0)
            {
                if(j != 0)
                {
                    output << " ";
                }

                output << "|";
            }

            if(listNbr[i][j].isValid() && listNbr[i][j].getNbr() == nbr)
            {
                output << "*" << listNbr[i][j].getNbr();
            }
            else if(std::count(listNbr[i][j].getVec().begin(), listNbr[i][j].getVec().end(), nbr))
            {
                output << " " << nbr;
            }
            else
            {
                output << " .";
            }
        }
        output << " |" << std::endl;
    }

    output << "+ - - - + - - - + - - - +" << std::endl;

    return output;
}

std::ostream& operator<<(std::ostream& output, Sudoku s)
{
    output << s.toString();
    return output;
}

int main()
{
    try
    {
        Sudoku a("4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........");
        std::cout << a << std::endl;
        std::cout << a.isValid() << std::endl << std::endl;

        a.coutLittleNbrInGrid(std::cout);

        a.addLittleNbrEveywhere();

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

        //a.coutLittleNbr(std::cout);
        //std::cout << std::endl;
        // ui c la flemme de surcharger l'operateur << une deusième fois

        std::cout << a << std::endl;

        //a.solve();

        //std::cout << a << std::endl;

        a.coutLittleNbrInGrid(std::cout);
    }
    catch (const std::exception& e)
    {
        std::cout << "error : " << e.what() << std::endl;
    }

    return 0;
}