title: recursion solution of sudoku in python
body: <pre><code>def answer_solve_sudoku(__grid):
  
      res = check_sudoku(__grid)
      if res is None or res is False:
          return res
  
      grid = copy.deepcopy(__grid)
  
      # find the first 0 element and change it to each of 1..9,
      # recursively calling this function on the result
      for row in xrange(9):
          for col in xrange(9):
              if grid[row][col] == 0:
                  for n in xrange(1, 10):
                      grid[row][col] = n
                      new = answer_solve_sudoku(grid)
                      if new is not False:
                          return new
                  # backtrack
                  return False
  
      # if we get here, we found no zeros and so we're finished
      return grid
  </code></pre>
  
  <p>Here is the code, and <code>check_sudoku(grid)</code> can return if a grid is a valid sudoku or not.</p>
  
  <p>I just can't understand the recursion part, I tried to write down the process on the paper, but it failed everytime, how is backtraking working? and what is <code>new</code>? if the <code>answer_solve_sudoku(grid)</code> is valid?</p>
  
  <p>I know it sets every 0 to 1..9, and checks if it's a valid grid or not, but I just can't draw the whole process on the paper. And can't really understand how the backtrack is working.</p>
  
  <p>btw, is there any advice of understanding recursion code?</p>
  
  <p>Best Regards,</p>
  
  <p>Sheng Yun</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I read the code again and again, and now I have some understanding, but I'm just not that sure about this, it will be kind if anyone gives me some comments.</p>
  
  <p>1, <code>return new</code> will only be called when the solver found the solution, and this will be called right after <code>return grid</code></p>
  
  <p>2, when will</p>
  
  <pre><code># backtrack
  return False
  </code></pre>
  
  <p>be called? if the next solution isn't right, <code>check_sudoku(__grid)</code> will return <code>False</code>, and if the next solution is right, it will call another <code>answer_solve_sudoku(grid)</code> till it gets the right solution, and when it gets the right solution, it will <code>return grid</code> and then <code>return new</code>. So when is:</p>
  
  <pre><code># backtrack
  return False
  </code></pre>
  
  <p>called?</p>