0

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);
}
1
Contributor
1
Reply
2
Views
6 Years
Discussion Span
Last Post by Despairy
0

Well, i dont know how to delete this post or move it ,
but i did submit it on code snippets sub forum.
not sure why its on unsolved :o (it works :o)
sorry ^^

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.