title: SUDOKU solver in c++
body: <p>I need help to make a Sudoku solver in C++.</p>
  <p>Requirements of the program:</p>
  <ol>
  <li>Input Sudoku:[Done]</li>
  <li>Read Sudoku: [Done]</li>
  <li>Validate function: (validates the Sudoku:) [Done]</li>
  <li>Display function [done]</li>
  <li>solve function [need help]</li>
  </ol>
  <p>My plan:</p>
  <ul>
  <li>Make a function to validate the sudoku [done]
  and assign possibility of 1-9 for every blank colume. and perform a brute-force<br />
  method to solve the puzzle. It will call the function validate each time
  while doing brute force. It consumes a lot of time and I understood that it is
  impossible.</li>
  </ul>
  <p>I need a better algorithm for the <code>solve</code> function, please help me.</p>
  <p>I have commented some of the code just to analyses the code: Apologize if that is the wrong way.</p>
  <p>Here is what I have done so far:</p>
  <pre><code>/*  Program: To solve a SU-DO-KU: 
      Date:23-sep-2013 @ 5.30:
  */
  
  
  #include&lt;iostream&gt;
  using namespace std;
  
  int su_in[9][9]={
                   0,0,7   ,0,0,0    ,4,0,6,
                   8,0,0   ,4,0,0    ,1,7,0,
                   0,0,0   ,3,0,0    ,9,0,5,
                   
                   0,0,0   ,7,0,5    ,0,0,8,
                   0,0,0   ,0,0,0    ,0,0,0,
                   4,0,0   ,2,0,8    ,0,0,0,
                   
                   7,0,4   ,0,0,3    ,0,0,0,
                   0,5,2   ,0,0,1    ,0,0,9,
                   1,0,8   ,0,0,0    ,6,0,0   
                  };
  int su_out[9][9];/*={
  
  
                   5,3,7   ,9,1,2    ,4,8,6,
                   8,2,9   ,4,5,6    ,1,7,3,
                   6,4,1   ,3,8,7    ,9,2,5,
                   
                   9,1,3   ,7,4,5    ,2,6,8,
                   2,8,6   ,1,3,9    ,7,5,4,
                   4,7,5   ,2,6,8    ,3,9,1,
                   
                   7,6,4   ,8,9,3    ,5,1,2,
                   3,5,2   ,6,7,1    ,8,4,9,
                   1,9,8   ,5,2,4    ,6,3,7
                  };*/
              
  struct chance{
      
      int poss[9];
      
  };              
                  
  int box_validate(int,int,int);
  void read(int);
  void display(int);
  int validate(int);
  int solve();
  
  int main()
  {   
      int i,j,row,get_res=2;
      
      enum {input=1,output};
      
      cout&lt;&lt;&quot;enter the sudoku: use 0 if the colum is empty:\n&quot;;
      
  //  for(i=0; i&lt;9; i++){
  //  read(i);
  //  }
      
      cout&lt;&lt;&quot;\n\t\tTHE ENTERED SU-DO-CU IS:\n\n&quot;;
      display(input);
      
      get_res=validate(input);
      
      if(get_res==0)
          cout&lt;&lt;&quot;valid input!\n&quot;;
          else if(get_res==1)
             cout&lt;&lt;&quot;invalid input!\n&quot;;
  
  //  display(input);
      for(i=0; i&lt;9; i++)
      for(j=0; j&lt;9; j++)
      su_out[i][j]=su_in[i][j];
      
  //  display(output);
      get_res=validate(output);
      
      if(get_res==0){
          cout&lt;&lt;&quot;valid solution!\n&quot;; display(output);}
      //  else if(get_res==1)
      //     cout&lt;&lt;&quot;invalid sudoku!\n&quot;;
      
      if(solve()==0) display(output);
      else cout&lt;&lt;&quot;not solved buddy!!\n&quot;;
  
  
  }
  
  
  
  
  void read(int row) // function to read the SU-DO-CU
  {   
      unsigned num,i;
      cout&lt;&lt;&quot;enter the row:'&quot;&lt;&lt;row+1&lt;&lt;&quot;'\n&quot;;
      
      for(i=0; i&lt;9;   i++)
      {
      cin&gt;&gt;num;
      if(num&lt;0||num&gt;9)
      cout&lt;&lt;&quot;error! invalid input: enter a number &lt; or = 9 and &gt; or = 0 \n&quot;;
      else
      su_in[row][i]=num;
      }
  }
  
  
  void display(int sudoku) // function to display the SU-DO-CU
  {
      unsigned i,j;
      
          for(i=0;i&lt;9; i++)
          {   
              if(i%3==0)
              cout&lt;&lt;&quot;\t\t-------------------------\n&quot;;    
              
              cout&lt;&lt;&quot;\t\t&quot;;
              for(j=0; j&lt;9; j++)
                  {   
                      if(j%3==0)
                      cout&lt;&lt;&quot;| &quot;;
              
              //      if(su[i][j]==0)
              //      cout&lt;&lt;&quot;_ &quot;;
              //      else    
                      if(sudoku==1)
                      cout&lt;&lt;su_in[i][j]&lt;&lt;&quot; &quot;;
                      
                      else if(sudoku==2)
                      cout&lt;&lt;su_out[i][j]&lt;&lt;&quot; &quot;;
                      
                      if(j==8)
                      cout&lt;&lt;&quot;|&quot;;  
                      
                  }
                  
              cout&lt;&lt;&quot;\n&quot;;
              if(i==8)
              cout&lt;&lt;&quot;\t\t-------------------------\n&quot;;    
              
          
          }
          
          
  }
  
  
  int validate(int sudoku) // function to validate the input SU-DO-CU
  {
      unsigned i,j,k,n,count=0;
  //..........................row validation
      for(i=0; i&lt;9; i++)
          for(j=0; j&lt;9; j++)
              for(k=0;k&lt;9;k++)
                  {
                      if(sudoku==1 &amp;&amp; k!=j &amp;&amp; su_in[i][j]!=0)
                         {
                          if(su_in[i][j]==su_in[i][k])
                          return 1;
                         }
                       else if(sudoku==2 &amp;&amp; k!=j )
                         {
                          if(su_out[i][j]==su_out[i][k])
                          return 1;
                         }  
              
                      
                  }
  //..................................colume validation
      for(i=0;  i&lt;9;  i++)
          for(j=0;  j&lt;9;  j++)
              for(k=0;  k&lt;9;  k++)
                  {
                      if(sudoku==1 &amp;&amp; k!=j &amp;&amp; su_in[j][i]!=0)
                         {
                          if(su_in[j][i]==su_in[k][i])
                          return 1;
                         }
                       else if(sudoku==2 &amp;&amp; k!=i )
                         {
                          if(su_out[j][i]==su_out[j][k])
                          
                          return 1;
                         }    
                  }
      // each box validating.......................
      for(i=0;  i&lt;=6;  i=i+3)
          for(j=0; j&lt;=6; j=j+3)
          {
              if(box_validate(i,j,sudoku)==1)
              return 1;
          }
      
      // sum validation for output....
      
      if(sudoku==2)
      {
          for(i=0; i&lt;9; i++)
          for(j=0; j&lt;9; j++)
              count=count+su_out[i][j];
          
      if(count!=405) return 1;
      }
      
      
          return 0;           
                  
  }
  
  
  int box_validate(int i,int j,int sudoku)
  {   
      unsigned k=j,n=i;
      int temp_i=i,temp_j=j,temp_k=k, temp_n=n;
          for(i=temp_i;  i&lt;temp_i+3;  i++)
          for(j=temp_j;  j&lt;temp_j+3;  j++)
              for(k=temp_k;  k&lt;temp_k+3;  k++)
                  {           
                    if(sudoku==1 &amp;&amp; k!=j &amp;&amp; su_in[i][j]!=0)
                   {
                      if(su_in[i][j]==su_in[i][k])
                       return 1;
                      
                          for(n=temp_n;  n&lt;temp_n+3;  n++)
                          {
                               if(sudoku==1 &amp;&amp;  su_in[i][j]!=0)
                                if(k==j &amp;&amp; n==i)
                                  ;else 
                                    if(su_in[i][j]==su_in[n][k])
                                      return 1;
                                  
                          }
                  }
          
  
                  if(sudoku==2 &amp;&amp; k!=j )
                  {
                      if(su_out[i][j]==su_out[i][k])
                       return 1;
                      
                          for(n=temp_n;  n&lt;temp_n+3;  n++)
                          {
                               if(sudoku==1 )
                                if(k==j &amp;&amp; n==i)
                                  ;else 
                                    if(su_out[i][j]==su_out[n][k])
                                      return 1;
                                  
                          
  
                            }
                  }
              }
      return 0;
      
  }
  
  
  int solve()
  {
      unsigned i,j,k,m,n,x;   
  
  struct chance cell[9][9];
  
      for(i=0; i&lt;9; i++)
          for(j=0; j&lt;9; j++)
              if(su_in[i][j]==0)
                  for(k=0;k&lt;9; k++)
                  cell[i][j].poss[k]=k+1;
                  
                  /*
      for(i=0; i&lt;9; i++)
          for(j=0; j&lt;9; j++)
              if(su_in[i][j]==0)
                  for(k=0;k&lt;9; k++)
                  {   su_out[i][j]=cell[i][j].poss[k]=k+1;            
                          su_out[i][j]=cell[i][j].poss[k];
                          for(m=0; m&lt;9; m++)
                            for(n=0; n&lt;9; n++)
                            for(x=1; x&lt;=9; x++)
                            { if(x!=k+1)
                              cell[m][n].poss[x]==x;
                              if(validate(2)==0)
                                 return 0;
                         }
              }*/
              
          for(i=0; i&lt;9; i++)
          for(j=0; j&lt;9; j++)
              if(su_in[i][j]==0)
              while (validate(2)==0)
              {
              
                  for(k=0;k&lt;9; k++)
                  {   su_out[i][j]=k+1;           
                          for(m=i+1; m &lt;9 ; m++)
                            for(n=0; n &lt;9 ; n++)
                              for(x=1; x&lt;=9; x++)
                            { su_out[m][n]=x;
                              if(validate(2)==0)
                                 return 0;
                         }
              }
            }
  }
  </code></pre>