title: How does this Sudoku Solver Work?
body: <p>I've found some code that solves a sudoku puzzle, but I only understand part of it.</p>
  
  <pre><code>static boolean solve(int i, int j, int[][] cells) {
      if (i == 9) {
          i = 0;
          if (++j == 9)
              return true;
      }
      if (cells[i][j] != 0)  // skip filled cells
          return solve(i+1,j,cells);
  
      for (int val = 1; val &lt;= 9; ++val) {
          if (legal(i,j,val,cells)) {
              cells[i][j] = val;
              if (solve(i+1,j,cells))
                  return true;
          }
      }
      cells[i][j] = 0; // reset on backtrack
      return false;
  }
  
  static boolean legal(int i, int j, int val, int[][] cells) {
      for (int k = 0; k &lt; 9; ++k)  // row
          if (val == cells[k][j])
              return false;
  
      for (int k = 0; k &lt; 9; ++k) // col
          if (val == cells[i][k])
              return false;
  
      int boxRowOffset = (i / 3)*3;
      int boxColOffset = (j / 3)*3;
      for (int k = 0; k &lt; 3; ++k) // box
          for (int m = 0; m &lt; 3; ++m)
              if (val == cells[boxRowOffset+k][boxColOffset+m])
                  return false;
  
      return true; // no violations, so it's legal
  }
  </code></pre>
  
  <p>I understand the legal() method, it simply checks for duplicates which is not permitted. What is not so clear is how the recursion in solve() is doing its job.</p>
  
  <p>Could anyone provide insight on how that part works. I really want to understand it so I can implement one myself.</p>
  
  <p>Thanks</p>