Code Archive: Sudoku Puzzle solver

Code Archive: Sudoku puzzle solver.

The following code is published under GNU public license:

The documentation explaining this can be found here: http://www.codeproject.com/Articles/1032477/Sudoku-puzzle-Solver

Author's contact: sreramk@outlook.com

/**
        File Name: main.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

       License: GNU General Public License, version 3 (GPL-3.0)
*/

#include <iostream>
#include <ctime>
#include "Sudoku.h"
#include "coreSolution.h"
#include <stdlib.h>
int main()
{
    clock_t begin, end;
    int i, j;
    std::cout <<"\n              Su-do-ku solver V1.1                "
              <<"\n--------------------------------------------------"
              <<"\ncopyright (c) 2015  K Sreram"
              <<"\napplication developers: K Sreram.\n";
    BoardGrid Grid;

   std::cout <<"\n\n\n enter the puzzle";
   for(i=0; i < 9; ++i)
        for(j=0; j<9; ++j)
            std::cin>> Grid[i][j];
    Sudoku S(Grid);
    Solver solve;

    Solver::initializeGP();
    solve.SetCurPuzzle(S);
    std::cout << " \n the original puzzle:\n";
    for (i = 0; i<9; ++i)
    {
        for (j = 0; j<9; ++j)
        {
            if((*S.RetGrid())[i][j]  == 0)
                std::cout <<" ? ";
            else
                std::cout <<" "<< (*S.RetGrid())[i][j] << " ";

        }
        std::cout<<"\n";
        //std::cout << "\n";
    }
    std::cout << "\n\n";
    begin = clock();
    solve.RecrussiveSolve();
    end = clock();
    std::cout << "\nThe solution :\n";
    if(Solver::IsSolutionSet)
    {
        for(i=0; i<9; ++i)
        {
            for(j=0; j<9; ++j)
            {
                std::cout<< (*Solver::SudokuSolution.RetGrid())[i][j] <<"  ";
            }
            std::cout << "\n";
        }
    }
    else
    {
        std::cout << "no solution found";
    }

    std::cout << "\n\ntime elapsed = " << (double)(end - begin) / CLOCKS_PER_SEC;
    std::cout << "\n Number of iterations :" <<Solver::Count << "\n";
    system("pause");
    return 0;
}

/**
        File Name: Sudoku.h
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#ifndef SUDOKU_H
#define SUDOKU_H
#include "inverseCountSum.h"
#include "basicDeff.h"
class Sudoku
{
    // shows if there is a possibility for zero to be present in the possibilities variable
    bool ZeroPossibilities;

    BoardGrid Grid; // shows one sudoku board; (x, y) represents the position and the value
                    // field represents the value
        BoardGrid possibilities;
        BoardGrid possibilityCount;
        InversePossibility possibilityCountI; // inverse count (this serves as the exact inverse of the
                                          // possibilityCount.
        InvCount PossibCount;

                    /// only for debug purpose
                #ifdef DEBUG_TESTS
                        Waights weight_values; // holds the weights
                #endif // DEBUG_TESTS
    //BoardGrid possibilityCount;
    public:

                     PriorityUnit TempPUnit;

        Sudoku();
        Sudoku (BoardGrid grid);
        void SetGrid(BoardGrid grid);
        // this is the basic operation involved in converting the sudoku puzzle into a different sequence.
        void SwitchNumbers(int Value1, int Value2); // interchanges the values without making
                                                                // any mistakes by violating the fundamental rules
        bool ScreenPossibility(int pos_x, int pos_y); // screens the possibility of numbers that can fit.
        bool ScreenPossibilityL2(int pos_x, int pos_y);
        static bool CheckLegal(BoardGrid); // same as IsLegal(), but takes the board as the input
        bool IsLegal(); // checks if the current board is legal (or correctly follows the rules)
        static bool DeleteValue(int Value, int &field); // deletes the bit field (making it zero) which is at the position "value".
                                                        // "field" is a bit-vice set, holding the possibilities the cell can hold.
        void DeleteCommonElements(int Value_set, int& field );
        static int BitValue(int Value);
        BoardGrid* RetGrid();
        BoardGrid* RetPoss();
        static bool SinglePossibilityElement(int possib);
        static int NoOfElements(int value);
        bool Solve();

        void GeneratePossibilityCount();
        void GenerateInversePossibilityCount();
        void SetPossibilityCount();
        void GenerateWaightValues(InvCount& inv, WaightQueue& Q,  int pos_x, int pos_y);
        WaightQueue GenerateWaightValues();
        void reinitializepos();

        bool IsSolved();
        bool FullPossibility();

};



#endif // SUDOKU_H

/**
        File Name:Sudoku.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram.

       License: GNU General Public License, version 3 (GPL-3.0)
*/
#include "Sudoku.h"
#include <iostream>
Sudoku::Sudoku()
{
    // this defines a free grid without any values
    int i, j;
    for(i=0; i < 9; ++i)
        for(j=0; j < 9; ++j)
            {
                Grid[i][j] = 0;
                possibilities[i][j] = POS_ALL;
//                possibilityCount[i][j] = 9;
            }
    ZeroPossibilities = false;
}


Sudoku::Sudoku(BoardGrid grid)
{
    int i, j;
    for(i=0; i < 9; ++i)
        for(j=0; j < 9; ++j)
            {
                Grid[i][j] = grid[i][j];
                if(grid[i][j] == 0)
                    possibilities[i][j] = POS_ALL;
                else
                    possibilities[i][j] = 0x1 << (grid[i][j]-1);
//                possibilityCount[i][j] = 9;
            }
}

void Sudoku::SwitchNumbers( int Value1, int Value2)
{
    int i, j;
    for(i=0; i < 9; ++i)
        for(j=0; j < 9; ++j)
            {
                if(Grid[i][j] == Value1)
                    Grid[i][j] = Value2;
                else if(Grid[i][j] == Value2)
                    Grid[i][j] = Value1;
                //else do nothing
            }
}


bool Sudoku::DeleteValue(int Value, int& field)
{
    bool mod = ( (field & ((0x1 << (Value-1) ))) != 0);
    if(Value != 0)
        {
            field = field & (~(0x1 << (Value-1) ));
        }
    return mod;
}

void Sudoku::DeleteCommonElements(int Value_set, int& field)
{
    if(Value_set != 0)
        {
            field = field & (~Value_set );
        }
}

int Sudoku::BitValue(int Value) // returns the value that is present in the set Value
{
    int val;
    if(Value == 0) return 0;
    for(val = 0; val < 9; ++val)
    {
        if (((0x1<<val) & Value) != 0)
            return val+1;
    }
    return 0;
}

bool Sudoku::SinglePossibilityElement(int possib)
{
    return
    (
            possib == POS1 ||
            possib == POS2 ||
            possib == POS3 ||
            possib == POS4 ||
            possib == POS5 ||
            possib == POS6 ||
            possib == POS7 ||
            possib == POS8 ||
            possib == POS9
    );
}

bool Sudoku::ScreenPossibility(int pos_x, int pos_y)
{
    bool Modification = false;
    GridLimits Lim;
    int i,j;
    Lim.SetLimits(pos_x, pos_y);
    int possib = possibilities[pos_y-1][pos_x-1];
    //int possib = POS_ALL;
    // for variation in +ve x
    for(i= pos_y - 1, j = pos_x - 1; j < 9; ++j  )
        if(DeleteValue(Grid[i][j], possib))  Modification = true;

    // for variation in -ve x
    for(i= pos_y - 1, j = pos_x - 1; j >= 0; --j )
        if(DeleteValue(Grid[i][j], possib))  Modification = true;

    // for variation in +ve y
    for(i= pos_y - 1, j = pos_x - 1; i < 9; ++i  )
        if(DeleteValue(Grid[i][j], possib))  Modification = true;

    // for variation in -ve y
    for(i= pos_y - 1, j = pos_x - 1; i >= 0; --i )
        if(DeleteValue(Grid[i][j], possib))  Modification = true;

    for(i = Lim.Y_Top; i  <= Lim.Y_End; ++i  )
        for(j = Lim.X_Top; j  <= Lim.X_End; ++j  )
                DeleteValue(Grid[i][j], possib);

    possibilities[pos_y-1][pos_x-1] = possib;

    if (possib == 0x0) // sets the trigger for zero possibilities
        ZeroPossibilities = true;
    //(possibilityCount[pos_y - 1][pos_x -1] -= count);
    //std::cout<<possibilityCount[pos_y - 1][pos_x -1];
    if(SinglePossibilityElement(possib))
        {
            Grid[pos_y-1][pos_x-1] = BitValue(possibilities[pos_y - 1][pos_x -1]);
            //std::cout<<"\n\n Got You!" <<  possibilities[pos_y - 1][pos_x -1]<<"\n";
        }
    return Modification;
}

bool Sudoku::FullPossibility() // returns false if the possibility has zero in it
{
        return ZeroPossibilities; // only works if the Solve() is called
}
bool Sudoku::Solve()
{
    ZeroPossibilities = false;
    bool ret = false;
    //bool ret2 = false;
    for(int i=0; i<9; ++i)
        for(int j=0; j<9; ++j)
    {
        if (Grid[i][j] == 0)
        {
            if (ScreenPossibility(j + 1, i + 1))
                ret = true;
        }
        else
            possibilities[i][j] = 1;

    }
    return ret;
}

BoardGrid* Sudoku::RetGrid()
{
    return &Grid;
}

BoardGrid* Sudoku::RetPoss()
{
    return &possibilities;
}

void Sudoku::SetGrid(BoardGrid grid)
{
    (*this) = Sudoku(grid);
}


bool Sudoku::CheckLegal(BoardGrid b) // this is used for checking only complete solutions
{
    int x, y;
    Sudoku Temp (b);
    for(y = 1; y <= 9; ++y)
        for(x= 1; x <= 9; ++x)
            {
                Temp.ScreenPossibility(x, y); // screens all the possibilities
                if(!Temp.FullPossibility())
                    return false;
                /*if(!SinglePossibilityElement((*Temp.RetPoss())[y-1][x-1]))
                    return false;
                    */
            }
    return true;
}


bool Sudoku::IsLegal()
{
    return CheckLegal(Grid);
}


void Sudoku::SetPossibilityCount()
{
    PossibCount.SetValues(possibilityCountI);
}

bool Sudoku::IsSolved()
{
    for(int i=0; i<9; ++i)
        for(int j=0; j<9; ++j)
            if(Grid[i][j] == 0)
                return false;
    return true;

}

void Sudoku::reinitializepos()
{
    int i, j;
    for (i = 0; i < 9; ++i)
        for (j = 0; j < 9; ++j)
        {
            possibilities[i][j] = POS_ALL;
            //                possibilityCount[i][j] = 9;
        }

}

/**
        File Name: InverseCount.h
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#ifndef INVERSECOUNT_H
#define INVERSECOUNT_H
#include "basicDeff.h"
#include <vector>
const int Row  = 0;
const int Col  = 1;
const int Cell = 2;
class InvCount
{
public:

    float Count[3][9];
    void SetValues(InversePossibility& a);
    float Reterive(int Type, int pos);

};

extern const int Row;
extern const int Col;
extern const int Cell;
#endif // INVERSECOUNT_H

/**
        File Name: InverseCountSum.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#include <iostream>
#include "inverseCountSum.h"


void InvCount::SetValues(InversePossibility& a)
{
    int i,j, k;//, c = 0;
    for(i= 0; i <9; ++i)
    {
        Count[Row][i] = 0.0;
        for(j=0; j<9; ++j)
            {
               // if(a[i][j] == 1)
                 //   c++;
                Count[Row][i] += a[i][j];
            }
        //Count[Row][i] = Count[Row][i]/c;

    }
    //c= 0;
    for(i= 0; i <9; ++i)
    {
        Count[Col][i] = 0.0;
        for(j=0; j<9; ++j)
            {
      //          if(a[j][i] == 1)
       //             ++c;
                Count[Col][i] += a[j][i];
            }
       // Count[Col][i] = Count[Col][i]/c;
    }
    //c = 0;
    for(k=0; k<9; ++k)
    {
        Count[Cell][k] = 0.0;
        for(i= (((int)(k/3)*3) ); i < (((int)(k/3)*3)) + 3; ++i)
            for(j= ((k*3) % 9); j < ((k*3) % 9) + 3; ++j)
            {
      //          if(a[j][i] == 1)
      //              ++c;
                Count[Cell][k] += a[i][j];
                //std::cout<<"  "<<Count[Cell][k]<<"asasasd";
            }
        //Count[Cell][k] = Count[Cell][k]/c;
    }
}

float InvCount::Reterive(int Type, int pos)
{
    //std::cout<<"  "<<Count[Row][pos]<<" ";
    switch (Type)
    {
    case Row:
        return Count[Row][pos];
        break;
    case Col:
        return Count[Col][pos];
        break;
    case Cell:
        return Count[Cell][pos];
        break;
    default:
        return 0; // do nothing
    }
}

/**
        File Name: CoreSolution.h
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#ifndef CORE_SOLUTION_
#define CORE_SOLUTION_

#include "basicDeff.h"
#include "Sudoku.h"

#include <stack>
class Solver;
typedef std::stack <Solver> SudokuStack;
class Solver
{
    WaightQueue Q;

public:
    Sudoku CurPuzzle;
    static Sudoku SudokuSolution;
    static bool IsSolutionSet;
    static int Count;
    static int GlobalPossibilities[9][9];
    static void initializeGP();
    void SetCurPuzzle(Sudoku P);
    bool RecrussiveSolve (); // this starts the main solution iteration process
};


#endif // CORE_SOLUTION_

/**
        File Name: basicDeff.h
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/

#ifndef BASICDFF_H
#define BASICDFF_H

#include <queue>
#include <deque>


class ErrorLogs{
public:
    unsigned int error;
};


enum POSSIB
        {
            POS1 = 0x1,
            POS2 = 0x1<<1,
            POS3 = 0x1<<2,
            POS4 = 0x1<<3,
            POS5 = 0x1<<4,
            POS6 = 0x1<<5,
            POS7 = 0x1<<6,
            POS8 = 0x1<<7,
            POS9 = 0x1<<8,
            POS_ALL = POS1 | POS2 | POS3 | POS4 |
                      POS5 | POS6 | POS7 | POS8 |
                      POS9
        };



int possibilityGen(int Value); // a value from 1 to 9

typedef int BoardGrid[9][9];
typedef int possibilitySet[9][9];
typedef float InversePossibility[9][9];

#ifdef DEBUG_TESTS
                    typedef float Waights[9][9];
#endif // DEBUG_TESTS

struct PriorityUnit{ /// this is a structure that shows the location of the cell
                       /// along with it's priority.
        float PriorityValue;
        int x; int y; // represents the location of the element
};

class Sudoku;
class Compare{
public:
     bool operator () (PriorityUnit a, PriorityUnit b);
};
struct GridLimits{
    int GridNo;
    int X_Top, Y_Top;
    int X_End, Y_End;
    void SetLimits(int pos_x, int pos_y);
};



typedef std::priority_queue<PriorityUnit, std::deque<PriorityUnit>, Compare> WaightQueue;

#endif // BASICDFF_H

/**
        basicDeff.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram.         License: GNU General Public License, version 3 (GPL-3.0)
*/
#include "basicDeff.h"

void GridLimits::SetLimits(int pos_x, int pos_y)
{
    if(pos_x > 9 || pos_y > 9 || pos_x <= 0 || pos_y <=0)
    {
        return;
    }
    X_Top =  ( (int)((pos_x-1)/3) )*3;
    Y_Top =  ( (int)((pos_y-1)/3) )*3;
    X_End =  X_Top + 2; // +2 because, the starting position is denoted by X_top and crossing 2 units reaches the
                        // cell's end making it 3 steps in total (including the one at X_Top)
    Y_End =  Y_Top + 2;

    // GridNo = (Y_Top/3)*3 + X_top/3 + 1; Is same as,
     GridNo = Y_Top + X_Top/3 + 1;
}


bool Compare::operator () (PriorityUnit a, PriorityUnit b)
{
    return(a.PriorityValue < b.PriorityValue);
}

/**
        File Name: coreSolution.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#include <iostream>
//#include <stdlib.h>
#include "coreSolution.h"
#include "Sudoku.h"
#include "basicDeff.h"

#ifdef _GENERATOR_V1
    #include <stdlib.h>
    #include <time.h>
#endif // _GENERATOR_V1

Sudoku Solver::SudokuSolution;
bool Solver::IsSolutionSet = false;
int Solver::Count = 0;
int Solver::GlobalPossibilities[9][9];
void Solver::initializeGP()
{
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            GlobalPossibilities[i][j] = POS_ALL;
}
void Solver::SetCurPuzzle(Sudoku P)
{
    int i, j;
    for (i = 0; i < 9; ++i)
        for (j = 0; j < 9; ++j)
            (*CurPuzzle.RetGrid())[i][j] = (*P.RetGrid())[i][j];
}


bool Solver::RecrussiveSolve()
{
    //----------------------------------------
    Solver::Count++;
    //---------------------------------------
    PriorityUnit Unit;
    Solver solve;
    #ifndef _GENERATOR_V1
        int temp_pos, temp;
    #else
        int temp_pos;
        int temp[9];
    #endif // _GENERATOR_V1
    int i;
    int size;
    CurPuzzle.reinitializepos();
    while (CurPuzzle.Solve());
    //-------------------------------------------------------------------------------
    if (Solver::Count % 10000000 == 0)
    {
        for (int i = 0; i<9; ++i)
        {
            for (int j = 0; j<9; ++j)
            {
                std::cout << (*CurPuzzle.RetGrid())[i][j] << "  ";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
        //system("pause");
    }
    //-------------------------------------------------------------------------------
    if (CurPuzzle.FullPossibility())  return false;
    //else
        //std::cout << "got you!";
    CurPuzzle.GeneratePossibilityCount();
    CurPuzzle.GenerateInversePossibilityCount();
    CurPuzzle.SetPossibilityCount();
    Q = CurPuzzle.GenerateWaightValues();
    if (CurPuzzle.IsSolved())
    {
        if (CurPuzzle.IsLegal() )
        {
            Solver::SudokuSolution = CurPuzzle;
            Solver::IsSolutionSet = true;
            return true;
        }
        else
            return false;
    }

    solve.SetCurPuzzle(CurPuzzle);
    //while (!Q.empty())
    //{
        Unit = Q.top();
        temp_pos = (*CurPuzzle.RetPoss())[Unit.y][Unit.x];
        //temp_pos = temp_pos & Solver::GlobalPossibilities[Unit.y][Unit.x];
        size = Sudoku::NoOfElements(temp_pos);
            #ifdef _GENERATOR_V1
                int j, T;
                for(i=0; i<size; ++i)
                {
                    temp[i] = Sudoku::BitValue(temp_pos);
                    Sudoku::DeleteValue(temp[i], temp_pos);
                }
                srand(time(NULL));
                for(i=0; i<size; ++i)
                {
                    j = (rand() % size);
                    T = temp[j];
                    temp[j] = temp[i];
                    temp[i] = T;
                }
            #endif // _GENERATOR_V1
            for (i = 0; i < size; ++i)
            {
                #ifndef _GENERATOR_V1
                    temp = (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = Sudoku::BitValue(temp_pos);
                    Sudoku::DeleteValue(temp, temp_pos);
                #else // _GENERATOR_V1
                        (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = temp[i];
                #endif
                if (solve.RecrussiveSolve())
                    return true;
                // it is obvious that 'false' is returned. So this value should not (never ever ever!!!) be
                // checked again. Or else, we would be wasting a lot of time!!!!
                //Sudoku::DeleteValue(temp, Solver::GlobalPossibilities[Unit.y][Unit.x]);
                solve.SetCurPuzzle(CurPuzzle);
            }
        (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = 0;
        Q.pop();
    //}
    return false;
}

/**
        File Name: generator.cpp
        Su-do-ku solver V1.1
        copyright (c) 2015 K Sreram
        program author: K Sreram

        License: GNU General Public License, version 3 (GPL-3.0)
*/
#include <iostream>
#include "Sudoku.h"
#include "inverseCountSum.h"
int Sudoku::NoOfElements(int value)
{

    int tcount = 0;
    if( (value & POS1) != 0) ++tcount;
    if( (value & POS2) != 0) ++tcount;
    if( (value & POS3) != 0) ++tcount;
    if( (value & POS4) != 0) ++tcount;
    if( (value & POS5) != 0) ++tcount;
    if( (value & POS6) != 0) ++tcount;
    if( (value & POS7) != 0) ++tcount;
    if( (value & POS8) != 0) ++tcount;
    if( (value & POS9) != 0) ++tcount;
    return tcount;
}



void Sudoku::GeneratePossibilityCount() // this is to be called only after calling the
{                                       // screen possibility function for all (x,y) coordinates
    int i,j;
    for(i=0; i<9; ++i)
        for(j=0; j<9; ++j)
            possibilityCount[i][j] = NoOfElements(possibilities[i][j]);
}

void Sudoku::GenerateInversePossibilityCount() // this is to be called after the GeneratePossibilityCount() is called
{
    int i,j;
    for(i=0; i<9; ++i)
        for(j=0; j<9; ++j)
            {
                possibilityCountI[i][j] = (float)(1/(float)possibilityCount[i][j]);
                //std::cout<<":: "<<possibilityCountI[i][j]<<" ";
            }
}


void Sudoku::GenerateWaightValues(InvCount& inv, WaightQueue& Q, int pos_x, int pos_y)
{
    GridLimits Lim;
    Lim.SetLimits(pos_x, pos_y);
    TempPUnit.PriorityValue = inv.Reterive(Row, pos_x - 1) +
        inv.Reterive(Col, pos_y - 1) +
        inv.Reterive(Cell, Lim.GridNo - 1)+
                                      10*possibilityCountI[pos_y-1][pos_x-1];
    TempPUnit.x = pos_x -1; // stored in C string indexing convention
    TempPUnit.y = pos_y -1;
    Q.push(TempPUnit);
}

WaightQueue Sudoku::GenerateWaightValues()
{
    WaightQueue Q;
    int i,j;
    for(i=1; i<=9; ++i)
        for(j=1; j<=9; ++j)
        {
            if (Grid[i-1][j-1] == 0)
                GenerateWaightValues(PossibCount, Q, j, i);
        }
        return Q;
}