bon il marche pas trop trop masi au moins il core cumped plu

/*
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>
#include <utility>

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 setIfOnlyOneLineRowCase();
    bool putOffLittleNbrIfOnlyInLine();
    bool putOffLittleNbrIfOnlyInCase();

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 line
    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 isInVect(int valTest, std::vector<int> v)
{
    return std::find(v.begin(), v.end(), valTest) != v.end();
}

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

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
    //std::cout <<  " " << listNbr[x][y].getNbr() << std::endl;

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

        for(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(unsigned int i = 0; i < listNbr.size() ; i++)
    {
        listNbr[i][y].putOffLitteNbr(val);
    }

    for(unsigned 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;

        if(setIfOnlyOne() || setIfOnlyOneLineRowCase() ||
            putOffLittleNbrIfOnlyInLine() || putOffLittleNbrIfOnlyInCase())
        {
            haveAChange = true;
        }
    }
}

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

    for(unsigned int i = 0; i < listNbr.size(); i++)
    {
        for(unsigned 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(unsigned int i = 0; i < listNbr.size(); i++)
        {
            int find = 0;

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

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

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

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

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

        for(int nbrCase = 0; nbrCase < 9; nbrCase++)
        {
            int find = 0;

            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(isInVect(nbrTest, listNbr[j][i].getVec()))
                    {
                        find++;
                    }
                }
            }

            if(find == 1)
            {
                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(isInVect(nbrTest, listNbr[j][i].getVec()))
                        {
                            addBigNbr(j, i, nbrTest);
                            haveAChange = true;
                        }
                    }
                }
            }
        }
    }

    return haveAChange;
}

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

    return prut;
}

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(listNbr[i][j].isValid())
            {
                output << " _";
            }
            else if(isInVect(nbr, listNbr[i][j].getVec()) && !listNbr[i][j].isValid())
            {
                output << " " << nbr;
            }
            else
            {
                output << " .";
            }
        }
        output << " |" << std::endl;
    }

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

    return output;
}

/*
Generic function to find an element in vector and also its position.
It returns a pair of bool & int i.e.

bool : Represents if element is present in vector or not.
int : Represents the index of element in vector if its found else -1

*/

template < typename T>
std::pair<bool, int > findInVector(const std::vector<T>  & vecOfElements, const T  & element)
{
    std::pair<bool, int > result;

    // Find given element in vector
    auto it = std::find(vecOfElements.begin(), vecOfElements.end(), element);

    if (it != vecOfElements.end())
    {
        result.second = distance(vecOfElements.begin(), it);
        result.first = true;
    }
    else
    {
        result.first = false;
        result.second = -1;
    }

    return result;
}

bool Sudoku::putOffLittleNbrIfOnlyInLine()
{
    bool haveAChange = false;

    for(int nbrTest = 1; nbrTest <= 9; nbrTest++) //THIS IS FOR THE LINES
    {
        for(int i = 0; i < listNbr.size(); i++)
        {
            std::vector<bool> isHere {false, false, false};

            for(int j = 0; j < listNbr[i].size(); j++)
            {
                if(isInVect(nbrTest, listNbr[i][j].getVec())
                            && !listNbr[i][j].isValid())
                {
                    isHere[j / 3] = true;
                    //std::cout << i << " " << j << std::endl;
                }
            }

            if(std::count(isHere.begin(), isHere.end(), true) == 1)
            {
                std::pair<bool, int> result = findInVector<bool>(isHere, true);

                //then find and put off the useless little numbers

                int caseFind = (i / 3) * 3 + result.second;

                /*
                std::cout << "finded ! ";

                for(int i = 0; i < isHere.size(); i++)
                {
                    std::cout << std::boolalpha << isHere[i] << " ";
                }
                std::cout << nbrTest << " " << caseFind;
                std::cout << std::endl;

                coutLittleNbrInGrid(std::cout); */

                for(int x = caseFind / 3 * 3; x < caseFind / 3 * 3 + 3; x++)
                {
                    for(int y = caseFind % 3 * 3; y < caseFind % 3 * 3 + 3; y++)
                    {
                        if(x != i && isInVect(nbrTest, listNbr[x][y].getVec()))
                        {
                            listNbr[x][y].putOffLitteNbr(nbrTest);
                            haveAChange = true;
                        }
                    }
                }
                //yes it's ugly but easier
            }

            //so if std::count(isHere.begin(), isHere.end(), nbrTest) == 1 is true


        }
    }

    for(int nbrTest = 1; nbrTest <= 9; nbrTest++) //THIS IS FOR THE ROWS
    {
        for(int j = 0; j < listNbr.size(); j++)
        {
            std::vector<bool> isHere {false, false, false};

            int iFind;

            for(int i = 0; i < listNbr[j].size(); i++)
            {
                if(isInVect(nbrTest, listNbr[i][j].getVec())
                        && !listNbr[i][j].isValid())
                {
                    isHere[i / 3] = true;

                    iFind = i;
                    //std::cout << i << " " << j << std::endl;
                }
            }

            if(std::count(isHere.begin(), isHere.end(), true) == 1)
            {
                std::pair<bool, int> result = findInVector<bool>(isHere, true);

                //then find and put off the useless little numbers

                int caseFind = (iFind / 3) * 3 + (j / 3);

                /*
                std::cout << "finded ! ";

                for(int i = 0; i < isHere.size(); i++)
                {
                    std::cout << std::boolalpha << isHere[i] << " ";
                }
                std::cout << nbrTest << " " << caseFind << " " << iFind << " " << j;
                std::cout << std::endl;

                coutLittleNbrInGrid(std::cout); */

                for(int x = caseFind / 3 * 3; x < caseFind / 3 * 3 + 3; x++)
                {
                    for(int y = caseFind % 3 * 3; y < caseFind % 3 * 3 + 3; y++)
                    {
                        if(y != j && isInVect(nbrTest, listNbr[x][y].getVec()))
                        {
                            listNbr[x][y].putOffLitteNbr(nbrTest);
                            haveAChange = true;
                        }
                    }
                }
                //yes it's ugly but easier
            }
        }
    }

    return haveAChange;
}

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

bool Sudoku::putOffLittleNbrIfOnlyInCase()
{
    bool haveAChange = false;

    for(int nbrTest = 1; nbrTest <= 9; nbrTest++)
    {
        for(int nbrCase = 0; nbrCase < 9; nbrCase++)
        {
            std::vector<bool> isHere {false, false, false};

            int iFind;
            int jFind;

            for(int x = nbrCase / 3 * 3; x < nbrCase / 3 * 3 + 3; x++)
            {
                for(int y = nbrCase % 3 * 3; y < nbrCase % 3 * 3 + 3; y++)
                {
                    //std::cout << x << " " << y << " " << nbrCase << std::endl;

                    if(isInVect(nbrTest, listNbr[x][y].getVec())
                            && !listNbr[x][y].isValid())
                    {
                        isHere[y % 3] = true;

                        iFind = x;
                        jFind = y;
                    }
                }
            }

            if(std::count(isHere.begin(), isHere.end(), true) == 1)
            { //Then delete the bad things

                std::cout << "finded ! ";

                for(int i = 0; i < isHere.size(); i++)
                {
                    std::cout << std::boolalpha << isHere[i] << " ";
                }
                std::cout << nbrTest << " " << nbrCase << " " << iFind
                            << " " << jFind << std::endl;

                coutLittleNbrInGrid(std::cout);

                for(int i = 0; i < listNbr.size(); i++)
                {
                    int caseFind = (i / 3) * 3 + (jFind / 3);

                    //std::cout << caseFind << " " << i << std::endl;
                    //std::cout << listNbr[i][jFind] << std::endl;

                    if(caseFind != nbrCase && listNbr[i][jFind].isValid()
                        && isInVect(nbrTest, listNbr[i][jFind].getVec()))
                    {
                        listNbr[i][jFind].putOffLitteNbr(nbrTest);
                    }
                }
                //std::cout << "it's nit here" << std::endl;
            }
        }
    }

    //std::cout << "i'm (may be) a bit safe" << std::endl;

    return haveAChange;
}

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

        a.coutLittleNbrInGrid(std::cout);

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

        a.solve();

        std::cout << a << "THE PROCESS HAS ENDED" << std::endl;

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

    return 0;
}