title: Code explanation of Sudoku Solver
body: <p>I have question about the following code snippet:
  It is a sudoku solver which solves a Sudoku puzzle by filling the empty cells.
  I can not really get the logic behind the solver method. Why does it return false after trying k=1-9 and return true after looping over all cells. What I thought is we recursively get into solver() method and once the sudoku is done, it will return true back as invoking order and finally the first invoked solver() will return true. I think I must omit some scenarios that above two "return" happen. Could someone explain to me why should those "return" exist?</p>
  
  <pre><code>public class Solution {
  
  public static void main(String[] args) {
      Solution s = new Solution();
      char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'},
                        {'5', '.', '.', '.', '7', '9', '.', '.', '4'},
                        {'3', '.', '.', '.', '1', '.', '.', '.', '.'},
                        {'6', '.', '.', '.', '.', '.', '8', '.', '7'},
                        {'.', '7', '5', '.', '2', '.', '.', '1', '.'},
                        {'.', '1', '.', '.', '.', '.', '4', '.', '.'},
                        {'.', '.', '.', '3', '.', '8', '9', '.', '2'},
                        {'7', '.', '.', '.', '6', '.', '.', '4', '.'},
                        {'.', '3', '.', '2', '.', '.', '1', '.', '.'}};
  
      s.solver(board);
  }
  public boolean solver(char[][] board) {
      for (int r = 0; r &lt; board.length; r++) {
          for (int c = 0; c &lt; board[0].length; c++) {
              if (board[r][c] == '.') {
                  for (int k = 1; k &lt;= 9; k++) {
                      board[r][c] = (char) ('0' + k);
                      if (isValid(board, r, c) &amp;&amp; solver(board)) {
                          return true;
                      } else {
                          board[r][c] = '.';
                      }
                   }
                  return false;
               }
           }
       }
      return true;
  }
  
  public boolean isValid(char[][] board, int r, int c) {
      //check row
      boolean[] row = new boolean[9];
      for (int i = 0; i &lt; 9; i++) {
          if (board[r][i] &gt;= '1' &amp;&amp; board[r][i] &lt;= '9') {
              if (row[board[r][i] - '1'] == false) {
                  row[board[r][i] - '1'] = true;
              } else {
                  return false;
              }
          }
      }
  
      //check column
      boolean[] col = new boolean[9];
      for (int i = 0; i &lt; 9; i++) {
          if (board[i][c] &gt;= '1' &amp;&amp; board[i][c] &lt;= '9') {
              if (col[board[i][c] - '1'] == false) {
                  col[board[i][c] - '1'] = true;
              } else {
                  return false;
              }
          }
      }
  
      //check the 3*3 grid
      boolean[] grid = new boolean[9];
      for (int i = (r / 3) * 3; i &lt; (r / 3) * 3 + 3; i++) {
          for (int j = (c / 3) * 3; j &lt; (c / 3) * 3 + 3; j++) {
              if (board[i][j] &gt;= '1' &amp;&amp; board[i][j] &lt;= '9') {
                  if (grid[board[i][j] - '1'] == false) {
                      grid[board[i][j] - '1'] = true;
                  } else {
                      return false;
                  }
              }
           }
      }
  
      return true;
  }
  }
  </code></pre>