we had an assigment a few months ago to build a sodoku solver recursively
so here it is.... i hope noone was bored enough to build one already.
//////////////////////////INCLUDES//////////////////////////////////
#include <iostream>
#include <cstdlib>
//////////////////////////////////INFO//////////////////////////////
/*
*/
//////////////////////////////USING/////////////////////////////////
using std::cout;
using std::cin;
using std::endl;
const int N=2;
//////////////////////////////////PROS//////////////////////////////
int sodoku(int array[N*N][N*N], bool &completed);
void placer(int array[N*N][N*N],int i,int j,bool &completed );
bool row_ok(int array[]); // checks if the row is soduku legit
bool col_ok(int array[][N*N] ,int col); // checks if the collum is soduku legit
bool square_ok(int array[][N*N] ,int row, int col); // checks the squares
bool all_ok(int array[][N*N]); // checks if all the functions returns true
void is_done(int array[N*N][N*N], bool &completed);
void read_board(int array[N*N][N*N]);
void print_board(int array[N*N][N*N]);
////////////////////////////////MAIN////////////////////////////////
int main()
{
int array[N*N][N*N]={0};
bool END=false;
read_board(array);
sodoku(array,END);
print_board(array);
}
////////////////////////////////FUNCTIONS////////////////////////////
int sodoku(int array[N*N][N*N], bool &completed)
{
for (int i=0;i<N*N ,!completed;i++)
for(int j=0;j<N*N,!completed;j++)
{
if (array[i][j]==0)
{
placer(array,i,j,completed);
if (array[i][j]==0)
return(EXIT_SUCCESS);
is_done(array,completed);
if (!completed)
array[i][j]=0;
}
is_done(array,completed);
}
}
void is_done(int array[N*N][N*N], bool &completed)
{
bool full=true;
for (int i=0;i<N*N ;i++)
for(int j=0;j<N*N;j++)
if (array[i][j]==0)
full=false;
completed=full;
if (!all_ok(array))
completed=false;
}
void placer(int array[N*N][N*N],int i,int j,bool &completed )
{
for (int num=1; num!=N*N+1 , !completed;num++)
{
if (num>N*N)
break;
array[i][j]=num;
if (all_ok(array))
sodoku(array,completed);
}
if (!completed)
array[i][j]=0;
}
void read_board(int array[N*N][N*N])
{ //read the starting board assuming legit input .
int row,col,value;
cin >> row;
while( row!=-1)
{
cin >> col>> value;
array[row][col]=value;
cin >> row;
}
}
void print_board(int array[N*N][N*N])
{
for (int k=0;k<N*N;k++)
{
cout<< endl;
for (int l=0;l<N*N;l++)
cout << array[k][l]<< " " ;
}
cout << endl;
}
bool all_ok(int array[][N*N])
{
bool isrow, iscol,issqr;
for (int i=0; i<N*N;i++)
{
isrow= row_ok(array[i]);
if (!isrow)
break;
}
for (int colc=0; colc<N*N;colc++)
{
iscol= (col_ok(array, colc));
if (!iscol)
break;
}
for (int sqrrow=0; sqrrow<N*N; sqrrow+=N) // checks all the squares
{ // by sending 0,0 0,0+N... etc
for (int sqrcol=0;sqrcol<N*N; sqrcol+=N)
{
issqr=(square_ok(array , sqrrow , sqrcol));
if (!issqr)
break;
}
if (!issqr)
break;
}
if (issqr && iscol && isrow) // returns 1 if all conditions apply
return(true);
else
return(false);
}
// function that checks if every row is fine for a soduku game
bool row_ok(int array[])
{
for (int col=0; col<N*N-1; col++)
{
for (int colhelp=col+1; colhelp<N*N; colhelp++)
{
if (array[col]==array[colhelp] && array[colhelp]!=0)
return(false);
}
}
return(true);
}
// function that checks if every col is fine for a soduku game
bool col_ok(int array[][N*N] ,int col)
{
for (int row=0; row<N*N-1; row++)
{
for (int rowhelp=row+1; rowhelp<N*N; rowhelp++)
{
if (array[row][col]==array[rowhelp][col] && array[row][col]!=0)
return(false);
}
}
return(true);
}
// function that checks if the soduku squares are legit
bool square_ok(int array[][N*N] ,int row, int col)
{
for (int rowh=row; rowh<row+N; rowh++)
{
for (int colh=col; colh<col+N; colh++)
{
for (int rowhelp=row+1; rowhelp<row+N ;rowhelp++)
for (int colhelp=col; colhelp<col+N ;colhelp++)
{
if (array[rowh][colh]==array[rowhelp][colhelp] &&
array[rowh][colh]!=0 && (rowh!=rowhelp || colh!=colhelp))
return(false);
}
}
}
return(true);
}