Monday, January 13, 2014

Soduku Solver An easy approach.

I can bet a coffee, you must have played this game for more about this game See here...
         How can we solve this puzzle through programming that's also seems a good task to do.This questions generally used to ask in interviews.This problem deal with the bactracking.

 

Approach:-An Empty position can be checked against a value (1 to 9) - Row-wise, Column-wise or In a small (3 by 3) matrix. if it satisfies go ahead and see the next position if not so, go back and change the previous value..... do this back and forth until all the cell gets filled.

see my code :- Easy to read
Important Note:- Things to check out before placing any value on empty(zeroth valued) position
1) Check the whole Row( of length 9) whether any similar value already exists or not if not go ahead and check other conditions.
2)Check the whole Column(of length 9) whether any similar value already exists or not if not go ahead and check next conditions.
3)Only Row and Column wise lookup against value is not enough, There are 9 small matrices of size 3 by 3 (which is named as sMatrixChecker in code), we have to check whether a similar value exists in small matrix against the value to be placed related to position of the value to be placed.
 Example:- See the middle 3 by 3 matrix which has values 6,0,7,9,4,0,2,0,5 (0 for empty) to fill any 0 valued position we have to check whether that value already exists in this matrix too or not.

/*By Atiqur Rahman for atiqwhiz.blogspot.in*/

    #include <iostream>
    #define N 9
    using namespace std;
    
    class Soduku
    {
    int arr[N][N];
    
    public:
    Soduku()
    { cout<<"Enter the initial position Rowise(1 to 9) if no +ve Integer put 0 there\n";
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
    cin>>arr[i][j];
    }
    void putSoduku()
    {
    for(int i=0;i<N;i++)
    {
    for(int j=0;j<N;j++)
    cout<<arr[i][j]<<" ";
    cout<<endl;
    }
    
    }
    bool sMatrixChecker(int value ,int row,int column);
    
    bool rowChecker(int value,int row,int column);
    
    bool columnChecker(int value,int row,int column);
    
    bool Solver(int ,int);
    };
    
    bool Soduku::sMatrixChecker(int value,int row,int column) //To check the small matrix of 3 by 3.
    {
    for(int i=row/3*3;i<row/3*3+3;i++)
    for(int j=column/3*3;j<column/3*3+3;j++)
    {
    if(arr[i][j]==value)
    return false;
    }
    return true;
    }
    //To solve row stability against value
    bool Soduku::rowChecker(int value,int row,int column)
    {
    for(int i=0;i<9;i++)
    {
    if(arr[row][i]==value)
    return false;
    }
    
    return true;
    }
    //To solve column stability against value.
    bool Soduku::columnChecker(int value,int row,int column)
    {
    for(int i=0;i<9;i++)
    {
    if(arr[i][column]==value)
    return false;
    }
    return true;
    }
    
                            //To solove the problem
bool Soduku::Solver(int n,int m)
{ int t,p;
     if(n==N)
     return true;
  for(int i=n;i<N;i++)
  {
    
    for(int j=m;j<N;j++)
    { int value=1;
       if(!arr[i][j])
       {
          while(value<10)
            {
               if(sMatrixChecker(value,i,j)&&rowChecker(value,i,j)&&columnChecker(value,i,j))
               {
                 arr[i][j]=value;    
                     t=i;p=j;
                    if((j+1)%N==0)
                    { t++;p=(j+1)%N;}
                    if(Solver(t,p))
                     return true;
               }
               else
               {
                arr[i][j]=0;
                value++;
               }
            }
          return false;   
       }
    
    }
   m=0;   
 
  }
}
   
    int main()
    {
    Soduku s;s.putSoduku();cout<<endl<<endl;
    s.Solver(0,0);
    cout<<"Solved Soduku\n";
    s.putSoduku();
    return 0;
    }

 Input (Empty cell is equal to zero).:- 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 0 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

output:-
Solved Soduku
3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9 

No comments:

Post a Comment