## Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

## Wednesday, 20 January 2016

### 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
program author: K Sreram
*/

#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--------------------------------------------------"
<<"\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
program author: K Sreram
*/
#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
program author: K Sreram.
*/
#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
program author: K Sreram
*/
#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
program author: K Sreram
*/
#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
program author: K Sreram
*/
#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
program author: K Sreram
*/

#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
program author: K Sreram.
*/
#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
program author: K Sreram
*/
#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
program author: K Sreram
*/
#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;