A sudoku solver based on one I found on StackOverflow (http://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work)

sudoku.py

import sys

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)

class InconsistentPositionError(Exception):
  pass

def still_consistent(a):
  """Check if a (partially filled) position is still consistent.

  Positional argument:
  1 - The 81-digit string that represents a (partially filled) sudoku position

  Returns:
  True  - if the position is still consistent
  False - if the position is not consistent

  """
  # Initialize the lists of missing numbers
  row_missing_numbers = list()
  col_missing_numbers = list()
  grd_missing_numbers = list()

  for i in range(9):
    row_missing_numbers.append(set('123456789'))
    col_missing_numbers.append(set('123456789'))

  for j in range(3):
    grd_missing_numbers.append(list())
    for k in range(3):
      grd_missing_numbers[j].append(set('123456789'))

  # Remove the numbers that are NOT missing
  for l in range(81):
    row_missing_numbers[l/9].discard(a[l])
    col_missing_numbers[l%9].discard(a[l])
    grd_missing_numbers[l/27][(l%9)/3].discard(a[l])

  # Initialize the lists of excluded numbers
  excluded_numbers = list()
  for m in range(81):
    if a[m] != '0':
      excluded_numbers.append(set('123456789'))
    else:
      excluded_numbers.append(set())
      for n in range(81):
        if a[n] != '0' and (same_row(m,n) or same_col(m,n) or same_block(m,n)):
          excluded_numbers[m].add(a[n])

  try:
    # See if any row is inconsistent
    ## 1. If a number is missing from a row and also excluded from every cell in
    ##    that row, the position is inconsistent.
    for o in range(9):
      sets = [ excluded_numbers[o*9 + x] for x in range(9) ]
      sets.append(row_missing_numbers[o])
      if len(set.intersection(*sets)) > 0:
#         print 'The position:'
#         for x in range(9):
#           print ''.join(a[x*9:x*9+9])
#         print 'Row {} causes inconsistency: {}'.format(o, a[o*9:o*9+9])
#         print 'Excluded numbers for row {}:'.format(o)
#         for x in sets:
#           print repr(x)
#         print 'Row {} missing numbers: '.format(o) + repr(row_missing_numbers[o])
        raise InconsistentPositionError()

    ## 2. If a number appears more than once in any row, the position is
    ##    inconsistent.
    for i in range(9):
      present_numbers = set()
      for j in range(9):
        if a[i*9 + j] in present_numbers:
#           print 'Row {} has duplicate numbers: {}'.format(o, a[o*9:o*9+9])
          raise InconsistentPositionError()
        elif a[i*9 + j] != '0':
          present_numbers.add(a[i*9 + j])

    # See if any column is inconsistent
    ## 1. If a number is missing from a column and also excluded from every cell
    ##    in that row, the position is inconsistent.
    for o in range(9):
      sets = [ excluded_numbers[x*9 + o] for x in range(9) ]
      sets.append(col_missing_numbers[o])
      if len(set.intersection(*sets)) > 0:
#         print 'Col {} causes inconsistency: {}'.format(o, [a[o + y*9] for y in range(9)])
        raise InconsistentPositionError()

    ## 2. If a number appears more than once in any column, the position is
    ##    inconsistent.
    for i in range(9):
      present_numbers = set()
      for j in range(9):
        if a[j*9 + i] in present_numbers:
#           print 'Col {} causes inconsistency: {}'.format(o, [a[o + y*9] for y in range(9)])
          raise InconsistentPositionError()
        elif a[j*9 + i] != '0':
          present_numbers.add(a[j*9 + i])

    # See if any grid is inconsistent
    ## 1. If a number is missing from a column and also excluded from every cell
    ##    in that row, the position is inconsistent.
    for y in range(3):
      for x in range(3):
        sets = [ excluded_numbers[y*27 + x*3 + j*9 + i] for i in range(3) for j in range(3)]
        sets.append(grd_missing_numbers[y][x])
        if len(set.intersection(*sets)) > 0:
#           print 'Grid {},{} causes inconsistency'.format(y, x)
          raise InconsistentPositionError()

    ## 2. If a number appears more than once in any grid, the position is
    ##    inconsistent.
    for y in range(3):
      for x in range(3):
        present_numbers = set()
        for j in range(3):
          for i in range(3):
            if a[y*27 + x*3 + j*9 + i] in present_numbers:
              print a[y*27 + x*3 + j*9 + i]
              print repr(present_numbers)
#               print 'Grid {},{} has duplicate numbers'.format(y, x)
              for k in range(9):
                print ''.join(a[k*9:k*9+9])
              raise InconsistentPositionError()
            elif a[y*27 + x*3 + j*9 + i] != '0':
              present_numbers.add(a[y*27 + x*3 + j*9 + i])
  except InconsistentPositionError:
    return False

  return True

solution = None

def r(a):
  """Recursively try to solve a sudoku puzzle by filling a cell at each level of
  recursion.

  Positional arguments:
  1 - The 81-digit string that represents a (partially filled) sudoku position

  """
  # print a
  global solution
  i = a.find('0')
  if i == -1:
    solution = a
    #sys.exit(a)
  # print ''.join(a)
  elif still_consistent(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:])
        if solution != None:
          break;

if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    #try:
    r(sys.argv[1])
    if solution == None:
      print 'The puzzle is unsolvable!'
    else:
      print 'The solution:'
      for x in range(9):
        print ''.join(solution[x*9:x*9+9])
    #except InconsistentPositionError:
    #  print 'This puzzle is unsolvable!'
  else:
    print 'Usage: python sudoku.py puzzle'
    print '  where puzzle is an 81-digit string representing the puzzle read left-to-right,'
    print '  top-to-bottom, and with 0 representing a blank cell.'