Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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>
- #include <fstream>
- 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;
- //std::ofstream couteuueuh { "sortie.txt" };
- 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++)
- {
- //couteuueuh << 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
- //couteuueuh << "finded ! ";
- /*
- for(int i = 0; i < isHere.size(); i++)
- {
- couteuueuh << std::boolalpha << isHere[i] << " ";
- } */
- //couteuueuh << nbrTest << " " << nbrCase << " " << iFind
- // << " " << jFind << std::endl;
- //coutLittleNbrInGrid(couteuueuh);
- for(int i = 0; i < listNbr.size(); i++)
- {
- int caseFind = (i / 3) * 3 + (jFind / 3);
- //couteuueuh << caseFind << " " << i << std::endl;
- //couteuueuh << listNbr[i][jFind] << std::endl;
- if(caseFind != nbrCase && !listNbr[i][jFind].isValid()
- && isInVect(nbrTest, listNbr[i][jFind].getVec()))
- {
- //couteuueuh << "..." << std::endl;
- listNbr[i][jFind].putOffLitteNbr(nbrTest);
- }
- }
- //couteuueuh << "it's nit here" << std::endl;
- }
- }
- }
- // a partir de la c la merde
- 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; y < nbrCase / 3 + 3; y++)
- {
- //couteuueuh << 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(couteuueuh);
- for(int j = 0; j < listNbr.size(); j++)
- {
- int caseFind = (iFind / 3) * 3 + (j / 3);
- std::cout << nbrTest << " " <<caseFind << " " << nbrCase << " " << iFind << " " << j << std::endl;
- std::cout << listNbr[iFind][j] << std::endl;
- if(caseFind != nbrCase && !listNbr[iFind][j].isValid()
- && isInVect(nbrTest, listNbr[iFind][j].getVec()))
- {
- std::cout << "this one" << std::endl;
- //couteuueuh << "..." << std::endl;
- listNbr[iFind][j].putOffLitteNbr(nbrTest);
- }
- }
- //couteuueuh << "it's nit here" << std::endl;
- }
- }
- }
- //couteuueuh << "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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement