SUDOKU SOLVER

/*

• move from left to right and top to down.
• In the empty cell try 1 to 9 and chose the first one that fit i.e chosen no. should not conflict with any entry in the same row and column.
• In a 9x9 sudoku there are 9 small(3x3) matrix, the chosen number should be unique in this smaller(3x3) matrix.
• Now move on to next cell and repeat the same procedure.
• If no number fits in this cell then backtrack(return false) to the previous made decision and change it to next higher value that fit.
• If no value fits in this cell backtrack to next higher level.

*/

#include<iostream.h>

#include<conio.h>

int sudoku[9][9]={{0,0,4,3,0,2,1,0,0},{0,6,0,0,0,0,0,2,0},{9,0,0,0,0,0,0,0,7},

                  {0,0,1,0,3,0,2,0,0},{2,0,0,9,0,6,0,0,1},{0,0,9,0,5,0,4,0,0},

                  {7,0,0,0,0,0,0,0,3},{0,1,0,0,0,0,0,4,0},{0,0,8,5,0,3,9,0,0}};

                 

bool findunassignedcell(int &r, int &c)

{

     for(int i=0;i<9;i++)

     {

             for(int j=0;j<9;j++)

             {

                     if(sudoku[i][j]==0)

                     {

                                        r=i;

                                        c=j;

                                        return true;

                     }

             }

     }

     return false;

}

void displaysudoku()

{

     cout<<"\n\n";

     for(int i=0;i<9;i++)

     {

              cout<<"\n";

              for(int j=0;j<9;j++)

                      cout<<"  "<<sudoku[i][j];

     }

}

bool noconflict(int r,int c,int n)

{

   bool flag=true;

   for(int i=0;i<9;i++)

   {

           if(sudoku[i][c]==n && i!=r)

                              flag=false;

   }

   for(int j=0;j<9;j++)

   {

           if(sudoku[r][j]==n && j!=c)

                              flag=false;

   }

  

   int rstart=r-r%3,cstart=c-c%3;

   int rend=rstart+2,cend=cstart+2;

  

   for(int p=rstart;p<=rend;p++)

   {

           for(int q=cstart;q<=cend;q++)

           {

                   if(sudoku[p][q]==n && (p!=r && q!=c))

                                      flag=false;

           }

   }

   return flag;

}

            

bool solvesudoku()

{

     int row,col;

     if(!findunassignedcell(row,col))

     {

                                     displaysudoku();

                                     return true;

     }

     for(int num=1;num<=9;num++)

     {

             if(noconflict(row,col,num))

             {

                                      sudoku[row][col]=num;//assign

             }

             else

                 continue;

             if(solvesudoku())

                              return true;

            

              sudoku[row][col]=0;  //unassign

     }

     return false;

}

int main()

{

    cout<<"INTITIAL \n";

    displaysudoku();

    cout<<"\n\nSOLVED \n\n";

    solvesudoku();

    getch();

    return 0;

}