Results 1 to 6 of 6

Thread: Sudoku Solver..

  1. #1
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default Sudoku Solver..

    So.. After creating this, I no longer find sudoku as fun as it used to be =(
    It solves 39 puzzles out of 50 from Project Euler and the daily newspaper.

    I never got the stupid HiddenPairs algorithm working but then again I never put much effort into it. It reads:

    http://projecteuler.net/project/sudoku.txt

    And solves almost all of them. Zipped Source: SudokuSolver.zip

    Enjoy.

    Screenies (At random that shows solved and un-solved puzzles):


    View-able Source:

    PuzzleInfo.hpp:
    C++ Code:
    #ifndef PUZZLEINFO_HPP_INCLUDED
    #define PUZZLEINFO_HPP_INCLUDED

    #include <windows.h>
    #include <iostream>
    #include <vector>
    #include <fstream>
    #include "Manipulation.hpp"

    void Move(short X, short Y);

    void FormatPuzzle(std::string FilePath, std::string CurrentDelimiter, std::string PuzzleDelimiter);

    void CreatePuzzles(std::string ProjectEulerFile, std::string PuzzleFolder);

    void ReadPuzzle(const std::string &FilePath, std::string Delimiter, int Matrix[9][9]);

    bool PuzzleSolved(int PuzzleMatrix[9][9]);

    void ReadRowLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9]);

    void ReadColumnLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9]);

    void ReadRow(int Index, int PuzzleMatrix[9][9], int RowMatrix[3][9]);

    void ReadColumn(int Index, int PuzzleMatrix[9][9], int ColumnMatrix[9][3]);

    void ReadBox(int RowIndex, int ColumnIndex, int PuzzleMatrix[9][9], int Box[3][3]);

    void PrintPuzzle(int Matrix[9][9], char BlankCharacter = '.');

    void PrintRowLine(int RowLine[9], char BlankCharacter = '.');

    void PrintColumnLine(int ColumnLine[9], char BlankCharacter = '.');

    void PrintRowMatrix(int RowMatrix[3][9], char BlankCharacter = '.');

    void PrintColumnMatrix(int ColumnMatrix[9][3], char BlankCharacter = '.');

    void PrintBoxMatrix(int BoxMatrix[3][3], char BlankCharacter = '.');

    #endif // PUZZLEINFO_HPP_INCLUDED

    PuzzleInfo.cpp:
    C++ Code:
    #include "PuzzleInfo.hpp"

    void Move(short X, short Y)
    {
        SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), COORD{X, Y});
    }

    void FormatPuzzle(std::string FilePath, std::string CurrentDelimiter, std::string PuzzleDelimiter)
    {
        std::string Line = std::string();
        std::vector<std::string> Lines;
        std::fstream File(FilePath.c_str(), std::ios::in);

        while(std::getline(File, Line))
        {
            if (Line.find(", ") == std::string::npos)
            {
                Lines.push_back(JoinStrings(SplitString(Line, CurrentDelimiter), PuzzleDelimiter) + "\n");
            }
        }
        File.close();

        if (!Lines.empty())
        {
            File.open(FilePath.c_str(), std::ios::out);
            for (auto it = Lines.begin(); it != Lines.end(); ++it)
            {
                File.write(it->c_str(), it->size());
            }
            File.close();
        }
    }

    void CreatePuzzles(std::string ProjectEulerFile, std::string PuzzleFolder)
    {
        std::fstream File(ProjectEulerFile.c_str(), std::ios::in);
        if (File.is_open())
        {
            int I = 0, J = 10;
            std::string Line;
            std::vector<std::string> Lines;

            while (std::getline(File, Line))
            {
                if (--J == 0)
                {
                    Lines.push_back(Line);
                    std::fstream Output(PuzzleFolder + "/" + ToString(++I) + ".hpp", std::ios::out);
                    if (Output.is_open())
                    {
                        for (auto it = Lines.begin(); it != Lines.end(); ++it)
                            Output.write(it->c_str(), it->size());
                        Output.close();
                    }
                    Lines.clear();
                    J = 10;
                }
                else if (J != 9)
                    Lines.push_back(Line + "\n");
            }
            File.close();
        }
    }

    void ReadPuzzle(const std::string &FilePath, std::string Delimiter, int Matrix[9][9])
    {
        std::string Line = std::string();
        std::vector<std::vector<std::string>> Lines;
        std::fstream File(FilePath.c_str(), std::ios::in);

        while(std::getline(File, Line))
        {
            Lines.push_back(SplitString(Line, Delimiter));
        }
        File.close();

        for (int I = 0; I < 9; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                Matrix[J][I] = ToNumber<int>(Lines[I][J]);
            }
        }
    }

    bool PuzzleSolved(int PuzzleMatrix[9][9])
    {
        for (int I = 0; I < 9; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                if (PuzzleMatrix[J][I] == 0)
                    return false;
            }
        }
        return true;
    }

    void ReadRowLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9])
    {
        for (int I = 0; I < 9; ++I)
        {
            LineMatrix[I] = PuzzleMatrix[I][Index];
        }
    }

    void ReadColumnLine(int Index, int PuzzleMatrix[9][9], int LineMatrix[9])
    {
        for (int I = 0; I < 9; ++I)
        {
            LineMatrix[I] = PuzzleMatrix[Index][I];
        }
    }

    void ReadRow(int Index, int PuzzleMatrix[9][9], int RowMatrix[3][9])
    {
        Index *= 3;

        for (int I = Index; I < Index + 3; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                RowMatrix[J][I] = PuzzleMatrix[J][I];
            }
        }
    }

    void ReadColumn(int Index, int PuzzleMatrix[9][9], int ColumnMatrix[9][3])
    {
        Index *= 3;

        for (int I = 0; I < 9; ++I)
        {
            for (int J = Index; J < Index + 3; ++J)
            {
                ColumnMatrix[J][I] = PuzzleMatrix[J][I];
            }
        }
    }

    void ReadBox(int RowIndex, int ColumnIndex, int PuzzleMatrix[9][9], int Box[3][3])
    {
        RowIndex *= 3;
        ColumnIndex *= 3;

        for (int C = 0, I = ColumnIndex; I < ColumnIndex + 3; ++C, ++I)
        {
            for (int R = 0, J = RowIndex; J < RowIndex + 3; ++R, ++J)
            {
                Box[R][C] = PuzzleMatrix[J][I];
            }
        }
    }

    void PrintPuzzle(int Matrix[9][9], char BlankCharacter)
    {
        for (int I = 0; I < 9; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                if (J == 3 || J == 6)
                {
                    std::cout<<"|  ";
                }

                if (Matrix[J][I] == 0)
                    std::cout<<BlankCharacter<<"  ";
                else
                    std::cout<<Matrix[J][I]<<"  ";
            }

            std::cout<<std::endl;
            if (I != 8)
            {
                std::cout<<"\t |\t     |\n";
            }

            if (I == 2 || I == 5)
            {
                std::cout<<"--------- ----------- ---------";
                std::cout<<std::endl;
                std::cout<<"\t |\t     |\n";
            }
        }
    }

    void PrintRowLine(int RowLine[9], char BlankCharacter)
    {
        for (int I = 0; I < 9; ++I)
        {
            if (RowLine[I] == 0)
                std::cout<<BlankCharacter<<' ';
            else
                std::cout<<RowLine[I]<<' ';
        }
    }

    void PrintColumnLine(int ColumnLine[9], char BlankCharacter)
    {
        for (int I = 0; I < 9; ++I)
        {
            if (ColumnLine[I] == 0)
                std::cout<<BlankCharacter<<std::endl;
            else
                std::cout<<ColumnLine[I]<<std::endl;
        }
    }

    void PrintRowMatrix(int RowMatrix[3][9], char BlankCharacter)
    {
        for (int I = 0; I < 3; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                if (RowMatrix[J][I] == 0)
                    std::cout<<BlankCharacter<<" ";
                else
                    std::cout<<RowMatrix[J][I]<<" ";
            }
            std::cout<<std::endl;
        }
    }

    void PrintColumnMatrix(int ColumnMatrix[9][3], char BlankCharacter)
    {
        for (int I = 0; I < 9; ++I)
        {
            for (int J = 0; J < 3; ++J)
            {
                if (ColumnMatrix[J][I] == 0)
                    std::cout<<BlankCharacter<<' ';
                else
                    std::cout<<ColumnMatrix[J][I]<<' ';
            }
            std::cout<<std::endl;
        }
    }

    void PrintBoxMatrix(int BoxMatrix[3][3], char BlankCharacter)
    {
        for (int I = 0; I < 3; ++I)
        {
            for (int J = 0; J < 3; ++J)
            {
                if (BoxMatrix[J][I] == 0)
                    std::cout<<BlankCharacter<<' ';
                else
                    std::cout<<BoxMatrix[J][I]<<' ';
            }
            std::cout<<std::endl;
        }
    }

    PuzzleAlgorithms.hpp:
    C++ Code:
    #ifndef PUZZLEALGORITHMS_HPP_INCLUDED
    #define PUZZLEALGORITHMS_HPP_INCLUDED

    #include <vector>
    #include <algorithm>
    #include "PuzzleInfo.hpp"

    template<typename T>
    inline bool InRange(T LowerBound, T UpperBound, T Value) {return ((LowerBound < Value) && (Value < UpperBound));}

    void GetBoxIndex(int RowX, int RowY, int &BoxXIndex, int &BoxYIndex);

    void GetCellPossibilities(int X, int Y, int PuzzleMatrix[9][9], std::vector<int> &CellInfo);

    void FillUniqueCells(int PuzzleMatrix[9][9]);

    void FillHiddenSingles(int Index, int PuzzleMatrix[9][9], bool Rows);

    #endif // PUZZLEALGORITHMS_HPP_INCLUDED

    PuzzleAlgorithms.cpp:
    C++ Code:
    #include "PuzzleAlgorithms.hpp"

    void GetBoxIndex(int RowX, int RowY, int &BoxXIndex, int &BoxYIndex)
    {
        if (RowX < 3) {BoxXIndex = 0;}
        else if (InRange(2, 6, RowX)) {BoxXIndex = 1;}
        else if (InRange(5, 9, RowX)) {BoxXIndex = 2;}

        if (RowY < 3) {BoxYIndex = 0;}
        else if (InRange(2, 6, RowY)) {BoxYIndex = 1;}
        else if (InRange(5, 9, RowY)) {BoxYIndex = 2;}
    }

    void GetCellPossibilities(int X, int Y, int PuzzleMatrix[9][9], std::vector<int> &CellInfo)
    {
        if (PuzzleMatrix[X][Y] != 0) return;

        std::vector<int> Data;
        int BoxMatrix[3][3] = {{0}};
        int RowLineMatrix[9] = {0};
        int ColumnLineMatrix[9] = {0};
        int RowBoxIndex = 0, ColumnBoxIndex = 0;
        GetBoxIndex(X, Y, RowBoxIndex, ColumnBoxIndex);

        ReadRowLine(Y, PuzzleMatrix, RowLineMatrix);
        ReadColumnLine(X, PuzzleMatrix, ColumnLineMatrix);
        ReadBox(RowBoxIndex, ColumnBoxIndex, PuzzleMatrix, BoxMatrix);

        for (int I = 0; I < 9; ++I)
        {
            if (BoxMatrix[I / 3][I % 3] != 0) Data.push_back(BoxMatrix[I / 3][I % 3]);
            if (RowLineMatrix[I] != 0) Data.push_back(RowLineMatrix[I]);
            if (ColumnLineMatrix[I] != 0) Data.push_back(ColumnLineMatrix[I]);
        }

        std::sort(Data.begin(), Data.end());
        Data.erase(std::unique(Data.begin(), Data.end()), Data.end());

        for (int I = 1, J = 0; I < 10; ++I, ++J)
        {
            if (std::find(Data.begin(), Data.end(), I) == Data.end())
            {
                CellInfo.push_back(I);
            }
        }
    }

    void FillUniqueCells(int PuzzleMatrix[9][9])
    {
        for (int I = 0; I < 9; ++I)
        {
            for (int J = 0; J < 9; ++J)
            {
                std::vector<int> CellInfo;
                GetCellPossibilities(J, I, PuzzleMatrix, CellInfo);

                if (CellInfo.size() == 1)
                {
                    PuzzleMatrix[J][I] = CellInfo[0];
                }
            }
        }
    }

    void FillHiddenSingles(int Index, int PuzzleMatrix[9][9], bool Rows)
    {
        std::vector<int> Data;
        std::vector<std::vector<int>> Possibilities;

        for (int I = 0; I < 9; ++I)
        {
            Possibilities.push_back(std::vector<int>());
            if (Rows)
            {
                GetCellPossibilities(I, Index, PuzzleMatrix, Possibilities.back());
            }
            else
            {
                GetCellPossibilities(Index, I, PuzzleMatrix, Possibilities.back());
            }
            Data.insert(Data.end(), Possibilities.back().begin(), Possibilities.back().end());
        }

        for (auto it = Data.begin(); it != Data.end(); ++it)
        {
            if (std::count(Data.begin(), Data.end(), *it) == 1)
            {
                int I = 0;
                for (auto jt = Possibilities.begin(); jt != Possibilities.end(); ++jt, ++I)
                {
                    if (std::find(jt->begin(), jt->end(), *it) != jt->end())
                    {
                        if (Rows)
                        {
                            PuzzleMatrix[I][Index] = *it;
                        }
                        else
                        {
                            PuzzleMatrix[Index][I] = *it;
                        }
                    }
                }
            }
        }
    }

    Manipulation.hpp:
    C++ Code:
    #ifndef MANIPULATION_HPP_INCLUDED
    #define MANIPULATION_HPP_INCLUDED

    #include <vector>
    #include <sstream>

    template <typename T>
    T ToNumber(const std::string &Text) {std::istringstream SS(Text); T Result; return (SS >> Result ? Result : 0);}

    template<typename T>
    inline std::string ToString(T Type){std::stringstream SS; SS<<Type; return SS.str();}

    template<typename T>
    std::ostream& operator << (std::ostream& Stream, const std::vector<T>& VectorToPrint)
    {
        if (VectorToPrint.size() > 1)
        {
            for (std::size_t I = 0; I < VectorToPrint.size() - 1; ++I)
            {
                Stream<<VectorToPrint[I]<<", ";
            }
        }

        if (!VectorToPrint.empty())
        {
            Stream<<VectorToPrint.back();
        }
        return Stream;
    }

    std::string JoinStrings(std::vector<std::string> StringsToJoin, std::string Delimiter);

    std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter);

    #endif // MANIPULATION_HPP_INCLUDED

    Manipulation.cpp
    C++ Code:
    #include "Manipulation.hpp"

    std::string JoinStrings(std::vector<std::string> StringsToJoin, std::string Delimiter)
    {
        std::string Result;
        for (std::size_t I = 0; I < StringsToJoin.size() - 1; ++I)
            Result += StringsToJoin[I] + Delimiter;

        Result += StringsToJoin[StringsToJoin.size() - 1];
        return Result;
    }

    std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
    {
        std::vector<std::string> Result;
        if (Delimiter == std::string())
        {
            for (std::string::iterator it = StringToSplit.begin(); it != StringToSplit.end(); ++it)
            {
                std::string Character = std::string();
                Character += *it;
                Result.push_back(Character);
            }
        }
        else
        {
            std::size_t Pos = StringToSplit.find_first_of(Delimiter);
            while(Pos != std::string::npos)
            {
                if(Pos > 0)
                {
                    Result.push_back(StringToSplit.substr(0, Pos));
                }
                StringToSplit = StringToSplit.substr(Pos + 1);
                Pos = StringToSplit.find_first_of(Delimiter);
            }

            if(StringToSplit.length() > 0)
            {
                Result.push_back(StringToSplit);
            }
        }
        return Result;
    }

    main.cpp:
    C++ Code:
    #include <windows.h>
    #include <iostream>
    #include "PuzzleInfo.hpp"
    #include "PuzzleAlgorithms.hpp"

    using namespace std;

    int Matrix[9][9];

    void Solve(int PuzzleMatrix[9][9])
    {
        FillUniqueCells(PuzzleMatrix);

        for (int I = 0; I < 9; ++I)
        {
            FillHiddenSingles(I, PuzzleMatrix, true);
        }

        for (int I = 0; I < 9; ++I)
        {
            FillHiddenSingles(I, PuzzleMatrix, false);
        }
    }

    void SolveAllPuzzles(std::string PuzzlePath)
    {
        int Count = 0;
        std::vector<int> Puzzles;
        for (int I = 1; I < 51; ++I)
        {
            std::cout<<"\n\nPuzzle: "<<I<<"\n\n";
            ReadPuzzle(PuzzlePath + ToString(I) + ".hpp", ", ", Matrix);

            for (int I = 0; I < 10; ++I)
                Solve(Matrix);

            PrintPuzzle(Matrix);
            if (PuzzleSolved(Matrix)) ++Count;
            else Puzzles.push_back(I);
        }

        std::cout<<"Failed: "<<Puzzles<<std::endl;
        std::cout<<"Solved: "<<Count<<" Puzzles!"<<std::endl;
    }

    int main()
    {
        CreatePuzzles("C:/Users/Brandon/Desktop/SudokuSolver/Sudoku.txt", "C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/");
        SolveAllPuzzles("C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/");
        return 0;

        /*ReadPuzzle("C:/Users/Brandon/Desktop/SudokuSolver/Puzzles/6.hpp", ", ", Matrix);

        for (int I = 0; I < 10 && !PuzzleSolved(Matrix); ++I)
        {
            Solve(Matrix);
        }

        PrintPuzzle(Matrix);

        //Move(0, 21);
        return 0;*/

    }
    Last edited by Brandon; 03-10-2013 at 07:32 PM.
    I am Ggzz..
    Hackintosher

  2. #2
    Join Date
    Sep 2010
    Posts
    5,762
    Mentioned
    136 Post(s)
    Quoted
    2739 Post(s)

    Default

    How long.. did this take?

  3. #3
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Took about some hours of straight coding.. No breaks lol.. I tried the hidden pairs which took a day or two but it failed.. My friend got hidden pairs working and it solves only 5 extra puzzles.. So his solves 44/50 puzzles while I'm stuck at 39.. :l

    Pretty interesting.. http://www.sudokuwiki.org/sudoku.htm shows around 30+ algorithms! None of which I tried yet.. Probably will update it with some of those since I can't think of any other ways other than hidden pairs.. The other algorithms I wouldn't even dream of being able to think about. Implementing them.. maybe.

    I was working on making it solve Image Sudoku puzzles too since I have image recognition code already but it'd take forever to put together..

    The printing stuff took the longest to code. I had already planned the algorithms on paper first. But the printing nicely, reading/formatting puzzles and stuff took so much debugging ahaha.
    Last edited by Brandon; 03-10-2013 at 07:44 PM.
    I am Ggzz..
    Hackintosher

  4. #4
    Join Date
    Nov 2011
    Location
    England
    Posts
    3,072
    Mentioned
    296 Post(s)
    Quoted
    1094 Post(s)

    Default

    I have no use for it but impressive to say the least.

  5. #5
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    A brute-force algorithm should work for the vast majority of cases (except for the one designed to be worse case, which can be defeated by permuting in a different direction).

    Does yours only do the algorithmic approach?
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  6. #6
    Join Date
    Jan 2012
    Posts
    369
    Mentioned
    6 Post(s)
    Quoted
    91 Post(s)

    Default

    As I am for having 100% reliability , brute force is wasting a lot of resources - I am pretty sure there is an algorithm just as efficient as brute forcing.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •