-1

/*
This is source code of function which solves sudoku,
function returns 1 if solution exists and 0 if not exist.
In case if solution exists, you have resolution in entry parameter of
this function
You can run this function in function main() eg.
if(sudoku(T)) print(T);
where print(T) is group of printing instructions of all table T and T is matrix
which is declared as int T[9][9];
*/

#include <stdlib.h>
#include <stdio.h>

int sudoku(int S[9][9])
{
    int **T; 
    int W[9]; 
    int nr, ile, i, i1, j, j1, jest, k, L, LL, min, ok, w, wpis;

    ok=1;
    i=0;
    while (i<9 && ok){ 
        j=0;
        while (j<9 && ok) {
          ok=((S[i][j]>=0) && (S[i][j]<=9));
          j++;
        }
        i++;
    }
    if (ok){ 
        w=0;
        while ((w<9) && ok){
           for (i=0;i<9;i++) W[i]=0;
           for (j=0;j<9;j++)  if (S[w][j]>0) W[S[w][j]-1]++;
           j=0;
           while (j<9 && ok){
             ok=(W[j]<2);  
             j++;     
           }
           w++;  
        }
        if (ok) {
          k=0;
          while (k<9 && ok){
            for (i=0;i<9;i++) W[i]=0;
            for (i=0;i<9;i++) if (S[i][k]>0) W[S[i][k]-1]++;
            i=0;
            while (i<9 && ok){
              ok=(W[i]<2);
              i++;   
            }        
            k++;
          }
          if (ok){
            for (i=0;i<9;i++) W[i]=0;
            for (i=0;i<3;i++)
            for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++; 
            i=0;
            while (i<9 && ok){
                ok=(W[i]<2);
                i++;   
            }
            if (ok){
              for (i=0;i<9;i++) W[i]=0;
              for (i=0;i<3;i++)
              for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;     
              i=0;
              while (i<9 && ok){
                ok=(W[i]<2);
                i++;   
              }
              if (ok){
                for (i=0;i<9;i++) W[i]=0;
                for (i=0;i<3;i++)
                for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;      
                i=0;
                while (i<9 && ok){
                  ok=(W[i]<2);
                  i++;   
                }
                if (ok){
                  for (i=0;i<9;i++) W[i]=0;
                  for (i=3;i<6;i++)
                  for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++;        
                  i=0;
                  while (i<9 && ok){
                    ok=(W[i]<2);
                    i++;   
                  }
                  if (ok){
                    for (i=0;i<9;i++) W[i]=0;
                    for (i=3;i<6;i++)
                    for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;     
                    i=0;
                    while (i<9 && ok){
                      ok=(W[i]<2);
                      i++;   
                    }
                    if (ok){
                      for (i=0;i<9;i++) W[i]=0;
                      for (i=3;i<6;i++)
                      for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;          
                      i=0;
                      while (i<9 && ok){
                        ok=(W[i]<2);
                        i++;   
                      }
                      if (ok){
                        for (i=0;i<9;i++) W[i]=0;
                        for (i=6;i<9;i++)
                        for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++;      
                        i=0;
                        while (i<9 && ok){
                          ok=(W[i]<2);
                          i++;   
                        }
                        if (ok){
                          for (i=0;i<9;i++) W[i]=0;
                          for (i=6;i<9;i++)
                          for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;
                          i=0;
                          while (i<9 && ok){
                            ok=(W[i]<2);
                            i++;   
                          }
                          if (ok){
                            for (i=0;i<9;i++) W[i]=0;
                            for (i=6;i<9;i++)
                            for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;
                            i=0;
                            while (i<9 && ok){
                              ok=(W[i]<2);
                              i++;   
                            }
                          if (ok){
                            ile=0;
                            T=(int **)malloc(2*sizeof(int *));
                            for(i=0;i<9;i++)
                            for(j=0;j<9;j++){
                              if (S[i][j]==0){
                                ile++; 
                                T[0]=(int *)realloc(T[0], ile*sizeof(int));
                                T[1]=(int *)realloc(T[1], ile*sizeof(int));
                                T[0][ile-1]=i; 
                                T[1][ile-1]=j;
                              }             
                            }
                            if (ile>0){
                              nr=0; 
                              while (nr>-1 && nr<ile){ 
                                wpis=0;
                                min=S[T[0][nr]][T[1][nr]];
                                S[T[0][nr]][T[1][nr]]=0;
                                LL=min;
                                for (L=9;L>min;L--){      
                                  jest=0;
                                  j=0;
                                  while (j<9){
                                    if (S[T[0][nr]][j]==L) jest=1;
                                    j++;   
                                  }      
                                  i=0;
                                  while (i<9){
                                    if (S[i][T[1][nr]]==L) jest=1;
                                    i++;   
                                  }
                                  if (T[0][nr]<3) i=0; else{
                                    if (T[0][nr]>2 && T[0][nr]<6) i=3; else        i=6;                       
                                  }
                                  if (T[1][nr]<3) j=0; else {
                                    if (T[1][nr]>2 && T[1][nr]<6) j=3; else j=6;     
                                  }
                                  for (i1=i;i1<i+3;i1++)
                                  for (j1=j;j1<j+3;j1++) if (S[i1][j1]==L) jest=1; 
                                  if (!jest) LL=L;
                                }
                                if (LL>min){
                                  S[T[0][nr]][T[1][nr]]=LL;
                                  wpis=1;       
                                } else
                                {
                                  S[T[0][nr]][T[1][nr]]=0;
                                  wpis=0;  
                                }
                                if (wpis) nr++; else nr--;
                              }       
                            }   
                            ok=(nr>ile-1); 
                            free(T[0]);
                            free(T[1]);
                            free(T);
                          }
                        }
                      }
                    }
                   }
                 }
               }
             }
           }        
         }
      }         
    }
    return ok;
}

/*
in function main()
int T[9][9];
...

if (sudoku(T)) print(T);
...
*/

Edited by dxprogrammer

2
Contributors
1
Reply
23
Views
3 Years
Discussion Span
Last Post by nitin1
This topic has been dead for over six months. 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.