Download Now :- Sudoku_completer

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int Sudoku[9][9][10]; //the actual sudoku
int backupSudoku[9][9][10]; //used for making a copy of the actual sudoku




//prototypes
bool remove_region_duplicates();
bool remove_row_duplicates();
bool remove_col_duplicates();
bool check_for_row_unique();
bool check_for_col_unique();
void check_depth();
void print_sudoku();
bool check_completed();
void guess_number(int &row, int &col, int &num);
void backup_sudoku();
void restore_sudoku();

/*********************************
Function Name: main()
Parameters: None
Description: This function calls all the other functions
Returns: int
**********************************/
int main()
{

/* First of all, I think I should explain the fundamentals
  as to how this program works.

  Well, firstly, you will notice that the sudoku array is 3 dimensional...
  why is that if a sudoku is only a 9x9 table (2D)?

  The reason for this is because the first (0) element of the 3rd dimension
  is used to store the actual value of the Sudoku.
  The other 9 elements of the 3rd dimension (1-9) are used to store "possible values".

  So lets look at an example:

  These are the values in the 0 element of the 3rd dimension for all the squares


  0|8|0|0|0|3|0|0|6
  0|4|0|2|8|0|1|0|0
  0|0|0|4|5|0|0|0|2
  0|0|6|0|0|0|3|4|0
  0|0|4|0|0|0|2|0|0
  0|1|3|0|0|0|6|0|0
  5|0|0|0|1|4|0|0|0
  0|0|1|0|2|7|0|6|0
  4|0|0|6|0|0|0|9|1

  if a square has the number 0, then it is empty.

  the 2nd element of the 3rd dimension (1) holds only 1's
  the 3rd element of the 3rd dimension (2) holds only 2's
  the 4th element of the 3rd dimension (3) holds only 3's
  etc......

  so, the looking at the 2nd element of all the squares:

    1|0|1|1|1|0|1|1|0
  1|0|1|0|0|1|0|1|1
  1|1|1|0|0|1|1|1|0
  1|1|0|1|1|1|0|0|1
  1|1|0|1|1|1|0|1|1
  1|0|0|1|1|1|0|1|1
  0|1|1|1|0|0|1|1|1
  1|1|0|1|0|0|1|0|1
  0|1|1|0|1|1|1|0|0

  Now, for the 2nd (1) to the 10th (9) elements for each sqaure, a 0 means that
  the 1st element (0) of the square already has value.. and therefore does not have
  any "possible values".

  You will notice that on the 2nd line down, there are ones... which is not possible
  because there is a 1 in the "actual values" (check the top sudoku example).
  But, we dont need to worry about that, the remove_region_duplicates, remove_row_duplicates
  and remove_col_duplicates will remove these "impossible values".

  And very quickly, incase anyone might not understand how this works still,
  I shall show you the 3rd element of the 3rd dimension (2)

       2|0|2|2|2|0|2|2|0
  2|0|2|0|0|2|0|2|2
  2|2|2|0|0|2|2|2|0
  2|2|0|2|2|2|0|0|2
  2|2|0|2|2|2|0|2|2
  2|0|0|2|2|2|0|2|2
  0|2|2|2|0|0|2|2|2
  2|2|0|2|0|0|2|0|2
  0|2|2|0|2|2|2|0|0

  The same thing applies (about duplicate values and such).

  For those of you that may not have a great deal of experience with arrays,
  I will show you how the values are stored in relation to the 3D array:

  Sudoku[row number][col number][3rd dimension]

//first row
  Sudoku[0][0][0] //0
  Sudoku[0][1][0] //8
  Sudoku[0][2][0] //0
  Sudoku[0][3][0] //0
  Sudoku[0][4][0] //0
  Sudoku[0][5][0] //3
       Sudoku[0][6][0] //0
  Sudoku[0][7][0] //0
  Sudoku[0][8][0] //6

//2nd row
  Sudoku[1][0][0] //0
  Sudoku[1][1][0] //4
  Sudoku[1][2][0] //0
  Sudoku[1][3][0] //2
  Sudoku[1][4][0] //8
  Sudoku[1][5][0] //0
       Sudoku[1][6][0] //1
  Sudoku[1][7][0] //0
  Sudoku[1][8][0] //0

etc.

//first row
  Sudoku[0][0][1] //1
  Sudoku[0][1][1] //0
  Sudoku[0][2][1] //1
  Sudoku[0][3][1] //1
  Sudoku[0][4][1] //1
  Sudoku[0][5][1] //0
       Sudoku[0][6][1] //1
  Sudoku[0][7][1] //1
  Sudoku[0][8][1] //0

//2nd row
  Sudoku[1][0][1] //1
  Sudoku[1][1][1] //0
  Sudoku[1][2][1] //1
  Sudoku[1][3][1] //0
  Sudoku[1][4][1] //0
  Sudoku[1][5][1] //1
       Sudoku[1][6][1] //0
  Sudoku[1][7][1] //1
  Sudoku[1][8][1] //1

etc.

  so... Sudoku[row][col][2] will only store 2's etc

  Note how the 3rd dimension works like a "set" e.g. sudoku[row][col]={0123456789}

  The module I have written this for says to use sets, so I shall upload the STL set
  version when it is complete.

*/

int strsubpos=0;
bool backup_is_empty=true;
bool doublefound=false;
int currentrow=0, currentcol=0, currentnum=1;
bool itchanged=true;
bool start_to_guess=false;

//this string stores all the values for the sudoku
string cellvalues="080003006040280100000450002006000340004000200013000600500014000001027060400600091";

//initalize by setting values of cells to the values in the string
for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
Sudoku[row][col][0]=atoi(cellvalues.substr(strsubpos,1).c_str());

for(int depth=1; depth<=9; depth++)
{
Sudoku[row][col][depth]=0;
}
//move to the next number in the string
strsubpos++;
}
}

//any square that does not have a value (except for 0.. which is a
//used to tell the program the square is empty), fill the
//3rd dimension [row][col][1] to [row][col][9] with the values 1-9
//ready for the functions to start deducing the actual values.
for(int combonumber=1; combonumber<=9; combonumber++)
{
for(row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
if(Sudoku[row][col][0]==0)
{
Sudoku[row][col][combonumber]=combonumber;
}
}
}
}

cout << "Incomplete Sudoku:" << endl << endl;
//display the sudoku as it is before anything changes it
//useful if you are cheating at an online sudoku ;)
//and you want to make sure that you have entered the data correctly
print_sudoku();

/*******************************
for full explinations of these
functions, check the function definisions below
*******************************/

//while the sudoku is not completed
while(!check_completed())
{
//guessing only starts when the while() loop below has finished
if(start_to_guess)
{
//insert a number from the possible values into
//a square, then start the while() loop below again.
guess_number(currentrow, currentcol, currentnum);
itchanged=true;
}

//while there changes have been made to the sudoku
while(itchanged)
{
itchanged=false;

//remove any duplicate values from all the regions
while(remove_region_duplicates())
{
//put any values on their own into the [0] element of the array
check_depth();
itchanged=true;
}
//remove any duplicate values from all the rows
while(remove_row_duplicates())
{
//put any values on their own into the [0] element of the array
check_depth();
itchanged=true;
}
//insert any unique values in a row into the [0] element of the array
while(check_for_row_unique())
{
//put any values on their own into the [0] element of the array
check_depth();
itchanged=true;
}
//remove any duplicate values from all the cols
while(remove_col_duplicates())
{
//put any values on their own into the [0] element of the array
check_depth();
itchanged=true;
}
//insert any unique values in a row into the [0] element of the array
while(check_for_col_unique())
{
//put any values on their own into the [0] element of the array
check_depth();
itchanged=true;
}
}

//this part is called if the deduction loop (above)
//cannot deduce any more numbers.

//if no backup has been performed
if(backup_is_empty)
{
//backup the sudoku
backup_sudoku();
backup_is_empty=false;
}

//tell this loop to start guessing numbers
start_to_guess=true;
}

cout << "The solution to this Sudoku:" << endl << endl;

//display the completed sudoku
print_sudoku();

return 0;

}

/*********************************
Function Name: remove_region_duplicates
Parameters: None
Description: remove any duplicate values from all the regions.
Returns: bool (false=no changes, true=changed made)
**********************************/
bool remove_region_duplicates()
{
/* EXAMPLE

region 1:

sudoku[0][0][0]=0 sudoku[0][0][2]=2
sudoku[0][1][0]=2 sudoku[0][1][2]=0
sudoku[0][2][0]=5 sudoku[0][2][2]=0
sudoku[1][0][0]=6 sudoku[1][0][2]=0
sudoku[1][1][0]=8 sudoku[1][1][2]=0
sudoku[1][2][0]=9 sudoku[1][2][2]=0
sudoku[2][0][0]=7 sudoku[2][0][2]=0
sudoku[2][1][0]=4 sudoku[2][1][2]=0
sudoku[2][2][0]=3 sudoku[2][2][2]=0

     0|2|5 The number 2 is in the 3rd dimension
 -----             this is not a possible value, because
 6|8|9 it is already being used in the region
 ----- (in a displayable square)
 7|4|3 so this function will remove it.

*/

int currentnum=0;
int cmax=2, rmax=2, rindex=0, cindex=0;
int checkrow=0, checkcol=0;
bool rowchanged=false;

//the counting has to go:
//row 0-2 col 0-2 //region 1
//row 0-2 col 3-5 //region 2
//row 0-2 col 6-8 //region 3
//row 3-5 col 0-2 //region 4
//etc.....
for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{

//this is for the counting system (shown above)
if(row==3 || row==6)
{
if(rindex!=row)
{
rindex+=3;
rmax+=3;
}
}

//get currennumber
currentnum=Sudoku[row][col][0];

//if current number is not 0
if(currentnum!=0)
{
//check for a duplicated in each region
for(checkrow=rindex; checkrow<=rmax; checkrow++)
{
for(checkcol=cindex; checkcol<=cmax; checkcol++)
{
//if the current number being checked
//is found in the 3rd dimension of a square...
if(Sudoku[checkrow][checkcol][currentnum]!=0)
{
//remove the number from the 3rd dimension
Sudoku[checkrow][checkcol][currentnum]=0;
rowchanged=true;
}
}
}
}

//this is for the counting system (shown above)
if(col==2 || col==5)
{
cindex=cindex+3;
cmax=cmax+3;
}
if(col==8)
{
cindex=0;
cmax=2;
}
}

}
return rowchanged;
}

/*********************************
Function Name: remove_row_duplicates
Parameters: None
Description: remove any duplicate values from all rows.
Returns: bool (false=no changes, true=changed made)
**********************************/
bool remove_row_duplicates()
{
/* EXAMPLE

[row][col][0]:   0|2|3|9|5|6|4|7|8
[row][col][2]: 2|0|0|0|0|0|0|0|0


the number 2 is in the possible values (the 3rd dimension)
which is not possible as the number 2 is already being used.
So this function will remove it.

*/

bool rowchanged =false;
int currentnum=0;

for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
//if the current square being checked have a value that is not 0
if(Sudoku[row][col][0]!=0)
{
//store the number in the square being checked
currentnum=Sudoku[row][col][0];

//go across the row checking if this number exists
//(a duplicate)
for(int checkcol=0; checkcol<=8; checkcol++)
{
//if the 3rd dimension (of the current square being checked)
//is not empty, the remove it.
if(Sudoku[row][checkcol][currentnum]!=0)
{
Sudoku[row][checkcol][currentnum]=0;
rowchanged=true;
}
}
}
}
}
return rowchanged;
}

/*********************************
Function Name: remove_col_duplicates
Parameters: None
Description: remove any duplicate values from all coloumns.
Returns: bool (false=no changes, true=changed made)
**********************************/
bool remove_col_duplicates()
{
/* EXAMPLE

[row][col][0]:   [row][col][2]

0| 2
2| 0
3| 0
9| 0
5| 0
6| 0
4| 0
7| 0
8| 0

the number 2 is in the possible values (the 3rd dimension)
which is not possible as the number 2 is already being used.
So this function will remove it.

*/

bool colchanged=false;
int currentnum=0;

for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
//if the current square being checked have a value that is not 0
if(Sudoku[row][col][0]!=0)
{
//store the number in the square being checked
currentnum=Sudoku[row][col][0];

//go down the column checking if this number exists
//(a duplicate)
for(int checkrow=0; checkrow<=8; checkrow++)
{
//if the 3rd dimension (of the current square being checked)
//is not empty, the remove it.
if(Sudoku[checkrow][col][currentnum]!=0)
{
Sudoku[checkrow][col][currentnum]=0;
colchanged=true;
}
}
}
}
}
return colchanged;
}

/*********************************
Function Name: check_for_row_unique
Parameters: None
Description: check each row to see if the is one possible
// value in the 3rd dimension on its own.
Returns: bool (false=no changes, true=changed made)
**********************************/
bool check_for_row_unique()
{
/* EXAMPLE:

    Sudoku[1][0][1]=0
    Sudoku[1][1][1]=0
    Sudoku[1][2][1]=0
Sudoku[1][3][1]=1
Sudoku[1][4][1]=0
Sudoku[1][5][1]=0
Sudoku[1][6][1]=0
Sudoku[1][7][1]=0
Sudoku[1][8][1]=0
Sudoku[1][9][1]=0

In this coloumn, there is only one square which has the
possible value of 1, so therefore '1' must be the value for this square

    */

bool rowchanged=false;
int numofduplicates=0;
int numcolpos=0;
int numrowpos=0;

//search through the 3rd dimension (all possible values)
for(int currentnumber=1; currentnumber<=9; currentnumber++)
{
for(int row=0; row<=8; row++)
{
numofduplicates=0;

for(int col=0; col<=8; col++)
{
//if the 3rd dimension square being checked actually
//has a number in it
if(Sudoku[row][col][currentnumber]!=0)
{
//store the possition of the number, and increase the count
//of this number by one.
numofduplicates++;
numrowpos=row;
numcolpos=col;
}
}
//if the count value is 1, then the number
//must be unique.
if(numofduplicates==1)
{
//remove all the values from the 3rd dimension of the square
//that holds this unique number
for(int removedepth=1; removedepth<=9; removedepth++)
{
//if the number is not equal to the unique number,
//remove is from the 3rd dimension
if(removedepth!=currentnumber)
Sudoku[numrowpos][numcolpos][removedepth]=0;

//we want to tell the while() loop that a change
//has been made
rowchanged=true;

}
//store the unique number in the displayable square
//of the sudoku
Sudoku[numrowpos][numcolpos][0]=currentnumber;
//remove the unique number from the 3rd dimension
Sudoku[numrowpos][numcolpos][currentnumber]=0;
}
}
}
return rowchanged;
}

/*********************************
Function Name: check_for_col_unique
Parameters: None
Description: check each coloumn to see if the is one possible
// value in the 3rd dimension on its own.
Returns: bool (false=no changes, true=changed made)
**********************************/
bool check_for_col_unique()
{

/* EXAMPLE:

    Sudoku[0][3][2]=0
    Sudoku[1][3][2]=0
    Sudoku[2][3][2]=0
Sudoku[3][3][2]=2
Sudoku[4][3][2]=0
Sudoku[5][3][2]=0
Sudoku[6][3][2]=0
Sudoku[7][3][2]=0
Sudoku[8][3][2]=0
Sudoku[9][3][2]=0

In this coloumn, there is only one square which has the
possible value of 2, so therefore '2' must be the value for this square

    */

bool colchanged=false;
int numofduplicates=0;
int numcolpos=0;
int numrowpos=0;

//search through the 3rd dimension (all possible values)
for(int currentnumber=1; currentnumber<=9; currentnumber++)
{
for(int col=0; col<=8; col++)
{
numofduplicates=0;

for(int row=0; row<=8; row++)
{
//if the 3rd dimension square being checked actually
//has a number in it
if(Sudoku[row][col][currentnumber]!=0)
{
//store the possition of the number, and increase the count
//of this number by one.
numofduplicates++;
numrowpos=row;
numcolpos=col;
}
}
//if the count value is 1, then the number
//must be unique.
if(numofduplicates==1)
{
//remove all the values from the 3rd dimension of the square
//that holds this unique number
for(int removedepth=1; removedepth<=9; removedepth++)
{
//if the number is not equal to the unique number,
//remove is from the 3rd dimension
if(removedepth!=currentnumber)
Sudoku[numrowpos][numcolpos][removedepth]=0;

//we want to tell the while() loop that a change
//has been made
colchanged=true;
}
//store the unique number in the displayable square
//of the sudoku
Sudoku[numrowpos][numcolpos][0]=currentnumber;
//remove the unique number from the 3rd dimension
Sudoku[numrowpos][numcolpos][currentnumber]=0;
}
}
}
return colchanged;
}

/*********************************
Function Name: check_depth
Parameters: None
Description: After removing impossible numbers from the 3rd dimension:
//           check if there is only one value left, if there is,
//           insert it into the displayable part of the sudoku
Returns: None
**********************************/
void check_depth()
{
int numbercount=0;
int depthpos=1;

for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
//go through the 3rd dimension
//(0 is the actual sudoku.. 1-9 hold the possible values)
for(int depth=1; depth<=9; depth++)
{
//if a value other than 0 is in the 3rd dimension
if(Sudoku[row][col][depth]!=0)
{
//count the number of values that are not 0
numbercount++;
//store the number, because if it is the only one left,
//it needs to be removed from the 3rd dimension and
//inserted into the displayable sudoku square.
depthpos=depth;
}
}
//if there are is 1 value that is > 0 in the 3rd dimension,
//remove it from the 3rd dimension and insert into the
//displayable square.
if(numbercount==1)
{
Sudoku[row][col][0]=Sudoku[row][col][depthpos];
Sudoku[row][col][depthpos]=0;
}
numbercount=0;
depthpos=0;
//if there are more that 1 values > 0, then dont do anything.
}
}

/* EXAMPLE:

Sudoku[1][5][1]=0
Sudoku[1][5][2]=0
Sudoku[1][5][3]=0
Sudoku[1][5][4]=0
Sudoku[1][5][5]=5
Sudoku[1][5][6]=0
Sudoku[1][5][7]=0
Sudoku[1][5][8]=0
Sudoku[1][5][9]=0

    5 is the only one in the 3rd dimension,
so remove it and insert it into Sudoku[1][5][0]

*/
}

/*********************************
Function Name: print_sudoku
Parameters: None
Description: Display the sudoku (can be called at any point
//           e.g. within the while(!check_completed()) so
// you can see the progress)
Returns: None
**********************************/
void print_sudoku()
{
for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
cout << "[" << Sudoku[row][col][0] << "]";
}
cout << endl;
}
cout << endl<<endl;
}

/*********************************
Function Name: check_completed
Parameters: None
Description: Check if the sudoku is complete
Returns: bool (false=not completed, true=completed)
**********************************/
bool check_completed()
{
int checkvalue=0;

//check if all the rows are complete
for(int row=0; row<=8; row++)
{
checkvalue=0;

for(int col=0; col<=8; col++)
{
//a very quick (not 100% acurate) method to check... just add up the numbers
//im so confident with this code :P that I dont think there is any
//other possible way for my code to display a line that gets 45
//(e.g. 1+1+3+4+5+6+7+9+9)
checkvalue+=Sudoku[row][col][0];
}
//if the value is not 45... its not complete
if(checkvalue!=45)
return false;
}

//check if all the cols are complete
for(int col=0; col<=8; col++)
{
checkvalue=0;

for(int row=0; row<=8; row++)
{
//same as above
checkvalue+=Sudoku[row][col][0];
}
if(checkvalue!=45)
return false;
}

return true;
}

/*********************************
Function Name: guess_number
Parameters: int &row, int &col, int &num
Description: 1. restore the sudoku from the backup
2. insert one of the possible numbers into an empty square
(once all possible numbers have been tried for that square,
 go to the next square)
Returns: None
**********************************/
void guess_number(int &row, int &col, int &num)
{
//retore the sudoku
restore_sudoku();

//if the current square is empty
if(Sudoku[row][col][0]==0)
{
//if the current index of the 3rd dimension of the array is not empty
if(Sudoku[row][col][num]!=0)
{
//insert the possible number into the cell
Sudoku[row][col][0]=Sudoku[row][col][num];
}
}

//because a loop cannot be used here, this function has to move to the
//next number to try... or the next cell to try (which is also why referencing
//is used for the row, col and num indexes (global variables are bad mmmkay).
//(after inserting the number to try,
//the program must call the remove_region_duplicate e.c.t. functions)
if(num++==10)
{
num=1;
if(col++==9)
{
col=0;
row++;
}
}
}

/*********************************
Function Name: backup_sudoku
Parameters: None
Description: copy the data from the Sudoku array to the backupSudoku array
Returns: None
**********************************/
void backup_sudoku()
{
for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
for(int depth=0; depth<=9; depth++)
{
backupSudoku[row][col][depth]=Sudoku[row][col][depth];
}
}
}
}

/*********************************
Function Name: restore_sudoku
Parameters: None
Description: copy the data from the backupSudoku array to the Sudoku array
Returns: None
**********************************/
void restore_sudoku()
{
for(int row=0; row<=8; row++)
{
for(int col=0; col<=8; col++)
{
for(int depth=0; depth<=9; depth++)
{
Sudoku[row][col][depth]=backupSudoku[row][col][depth];
}
}
}
}


Designed By Blogger Templates | Templatelib & Distributed By Blogspot Templates