Sudoku

[Eric Parry]

I downloaded the following program from somewhere using a link from Wikipedia and inserted the “most difficult Sudoku puzzle ever” string into it and ran it. It worked fine and solved the puzzle in about 4 seconds. However I cannot understand how it works. It seems to go backwards and forwards at random. Can anyone explain how it works in simple terms?
Eric.


def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

def r(a):
  i = a.find('0')
  if i == -1:
    print a
    exit(a)

  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])

  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

r('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
Sudoku solver where the puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank.