sudoku | Python Fiddle

import os, sys, codecs, copy

class Sudoku:
  def __init__(self, s = ""):
    # init possible
    self.possible = [ [set([k+1 for k in range(9)]) for dd in range(9)] for ddd in range(9) ]
    # init unsolved
    self.unsolved = set([])
    for a in range(9):
      for b in range(9):
        self.unsolved.add((a,b))
    # init to be propagated
    self.to_be_propagated = set([])
    # already update possible given input grid
    self.apply_grid(s)

def apply_grid(self, s):
    s = s.replace("\n", "")
    s = s.replace("\r", "")
    k = 0
    for row_index in range(9):
      for col_index in range(9):
        c = s[k]
        if c.isdigit():
          v = int(c)
          self.possible[row_index][col_index] = v
          self.unsolved.remove((row_index,col_index))
          self.to_be_propagated.add((row_index,col_index))
        k += 1
       
  def propagate(self):
    tbp = set([])
    success = True
    for (row_index,col_index) in self.to_be_propagated:
      v = self.possible[row_index][col_index]
      success &= self.propagate_row(v, row_index, col_index, tbp)
      success &= self.propagate_col(v, row_index, col_index, tbp)
      success &= self.propagate_square(v, row_index, col_index, tbp)
      if not success:
        print "(%d,%d) could not be propagated"%(row_index,col_index)
        return False
    
    self.to_be_propagated = copy.deepcopy(tbp)
    return True

def propagate_row(self, v, row_index, col_index, tbp):
    row_ids = [(row_index,d) for d in range(9) if d != col_index]
    return self.propagate_to(v, row_ids, tbp)

def propagate_col(self, v, row_index, col_index, tbp):
    col_ids = [(d,col_index) for d in range(9) if d != row_index]
    return self.propagate_to(v, col_ids, tbp)

def compute_square_ids(self, row_index, col_index):
    square_ids = set([])
    row0 = row_index / 3 * 3
    col0 = col_index / 3 * 3
    for x in range(3):
      for y in range(3):
        r = row0+x
        c = col0+y
        if r == row_index and c == col_index:
          continue
        square_ids.add((r,c))
    return square_ids

def propagate_square(self, v, row_index, col_index, tbp):
    square_ids = self.compute_square_ids(row_index, col_index)
    return self.propagate_to(v, square_ids, tbp)
        
  def propagate_to(self, v, ids, tbp):
    for cell in ids:
      a = cell[0]
      b = cell[1]
      if cell not in self.unsolved:
        if self.possible[a][b] == v:
          return False
        else:
          continue
      else:
        p = self.possible[a][b]
        if not v in p:
          continue
        p.remove(v)
        if len(p) == 1:
          self.possible[a][b] = p.pop()
          self.unsolved.remove(cell)
          tbp.add(cell)
    return True
          
  def solve(self):
    success = True
    while(success and self.to_be_propagated):
      success &= self.propagate()
      if not success:
        return False
    if not len(self.unsolved):
      return True
      
    for cell in sorted(self.unsolved, key = (lambda x:len(self.possible[x[0]][x[1]]))):
      a = cell[0]
      b = cell[1]
      for v in self.possible[a][b]:
        print >> sys.stdout, "trying value %d for cell (%d,%d)"%(v,a+1,b+1)
        s = copy.deepcopy(self)
        s.possible[a][b] = v
        s.to_be_propagated.add(cell)
        s.unsolved.remove(cell)
        if not s.solve():
          continue
        else:
          #self = copy.deepcopy(s)
          self.possible = copy.deepcopy(s.possible)
          self.to_be_propagated = copy.deepcopy(s.to_be_propagated)
          return True
      return False
          
  def pretty_print(self):
    s = ""
    for a in range(9):
      for b in range(9):
        s += str(self.possible[a][b])
      s += "\n"
    s += "\n"

print s

def is_solved(self):
    b = True
    # check every possible have only one element
    for k in range(9):
      for j in range(9):
        if not str(self.possible[j][k]).isdigit():
          return False
    for k in range(9):
      if len(set(self.possible[k][:])) != 9:
        print "wrong row %d"%k
        return False
      if len(set(self.possible[:][k])) != 9:
        print "wrong col %d"%k
        return False
    for k in range(3):
      for j in range(3):
        square_ids = self.compute_square_ids(3*j,3*k)
        square_ids.add((3*j,3*k))
        values = set( [self.possible[idd[0]][idd[1]] for idd in square_ids] )
        if len( values ) != 9:
          print "wrong square (%d,%d)"%(j,k)
          return False
    print "well done!"
    return True

# IRONBEN: tu rentres ton sudoku ci-dessous, a la place de mon exemple (espace pour les cases vides, comme dans l'exemple)
# et tu appuies sur le bouton run pou executer! c'est qd meme pas si complique...

s = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
s = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

#s = "41.3..895.3.1...4..5.7...1.825437169.9.58.432.4.91..5.289643571573291684164875923"

s = sys.argv[1]

# call the solver
S = Sudoku(s)
print S.solve()

# print results
S.pretty_print()

S.is_solved()

Python Fiddle

Python Cloud IDE