title: solve sudoku with backtracking - C++
body: <p>So I am trying to solve sudoku with backtracking </p>
  
  <p>And with this example :
  <a href="https://i.stack.imgur.com/ETXK2.jpg" rel="nofollow noreferrer">example_pic</a></p>
  
  <p>I hard-coded some of the indexes in the two dimensional array with numbers on places given from webSudoku (picture above).
  It definitely has solutions but, my code prints "solution doesn't exist</p>
  
  <p>Here is my code : </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  int a[10][10]= {{2,0,0,0,9,0,0,3,1},
              {0,0,3,5,0,6,0,2,0},
              {0,0,8,1,3,0,5,4,0},
              {7,2,0,0,0,9,0,0,4},
              {4,0,0,0,0,0,0,0,8},
              {3,0,0,6,0,0,0,9,5},
              {0,7,6,0,4,5,1,0,0},
              {0,1,0,9,0,7,4,0,0},
              {5,3,0,0,8,0,0,0,6}};
  
  bool is_valid(int x, int y, int value){
      if(a[x][y] != 0) return false;
  
      //check_row and column
      for(int tmp=1; tmp&lt;=9; tmp++){
          if(value == a[x][tmp]) return false;
      }
      for(int tmp=1; tmp&lt;=9; tmp++){
          if(value == a[tmp][y]) return false;
      }
      //check in 3*3 block
      int x_s = (x-1)/3*3 + 1;
      int y_s = 3*((y+2)/3-1)+1;
      for(int ch_x = x_s; ch_x&lt;x_s+3; ch_x++){
          for(int ch_y=y_s; ch_y&lt;y_s+3; ch_y++){
              if(ch_x!=x &amp;&amp; ch_y!=y){
                  if(value==a[ch_x][ch_y]) return false;
              }
          }
      }
      return true;
  }
  
  bool find(int &amp;x, int &amp;y){
      // check if valid cells are exists
      for(x=1; x&lt;=9; x++){
          for(y=1; y&lt;=9; y++){
              if(a[x][y] == 0)
                  return true;
          }
      } 
      return false;
  }
  
  bool solve(){
      int x,y;
      //base::case
      if(!find(x,y)) return true;
      for(int cand = 1; cand &lt;=9; cand++){
          if(is_valid(x,y,cand)){
              a[x][y] = cand;
              if(solve()) return true;
              a[x][y] = 0;
          }
      }
      return false;
  }
  
  void print(){
      //print the sudoku plate
      for(int i=1;i&lt;=9; i++){
          for(int j=1; j&lt;=9; j++){
              printf("%2d",a[i][j]);
          }
          printf("\n");
      }
      return ;
  }
  
  int main(){
      //Fill in some empty grid with the known values
      /*for(int i=1; i&lt;=9; i++){
          for(int j=1; j&lt;=9; j++){
          scanf("%1d",&amp;a[i][j]);
          }
      }*/
  
      if (solve()) print();
      else printf("No solution exists\n");
      return 0;
  }
  </code></pre>
  
  <p>I guess my 'solve function' or 'is_valid' function is not working right.</p>
  
  <p>In 'is_valid' function, if there is problem it would be </p>
  
  <pre><code>bool find(int &amp;x, int &amp;y){
  // check if valid cells are exists
      for(x=1; x&lt;=9; x++){
          for(y=1; y&lt;=9; y++){
              if(a[x][y] == 0)
                  return true;
          }
      }
      return false;
  } 
  </code></pre>
  
  <p>But, I also hard-coded this part and in my scope it doesn't seem like have problem.</p>
  
  <p>In 'solve function' </p>
  
  <pre><code>bool solve(){
      int x,y;
      //base::case
      if(!find(x,y)) return true;
      for(int cand = 1; cand &lt;=9; cand++){
          if(is_valid(x,y,cand)){
              a[x][y] = cand;
              if(solve()) return true;
              a[x][y] = 0;
          }
      }
      return false;
  }
  </code></pre>
  
  <p>I cant figure out where i got it wrong. If you find any other mistakes in the solve() function - let me know. Because I am not sure I understand the "backtracking" thing completely... </p>
  
  <p>p.s. : reference I read (<a href="https://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf" rel="nofollow noreferrer">https://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf</a>)</p>