Python sudoku solver.

gistfile1.py

import heapq
import itertools
nums = set(range(1,10))
class Node:
    def __init__(self, grid):
        self.children = []
        self.grid = grid
        self.answered = 0
        for i in self.grid:
            for j in i:
                if j != 0:
                    self.answered +=1
    def generateChildren(self):
        # If a row/column/grid can be solved, do it immediately
        # and use for all children.
        # If we have multiple options for guesses, make each guess
        # a new child grid. Guesses should made on those rows/columns/grids
        # that have the most unsolved. Guesses _must_ keep the grid valid

        # fill in easy solutions before we do anything
        for i in self.grid:
            diff = nums - set(i)
            if len(diff) == 1:
                i[i.index(0)] = diff.pop()
                self.answered +=1
            # here is where would we can make a guess...
        for i,j in enumerate(zip(*self.grid)):
            diff = nums - set(j)
            if len(diff) == 1:
                x = j.index(0)
                n = diff.pop()
                self.grid[x][i] = n
                print "Found: {} at {},{}".format(n,i,j)
                self.answered +=1
        for i in [0,1,2]:
            for j in [0,1,2]:
                q = quad(self.grid, i,j)
                diff = nums - set(q)
                if len(diff) == 1:
                    y,x = divmod(q.index(0),3)
                    self.grid[3*y+i][3*x+j] = diff.pop()
                    self.answered +=1
                    
        # Start making guesses
        # Find the quadrant with the most solved and try to place
        # make new guesses
        quads = sorted([(quad(self.grid,i,j),i,j) for i in [0,1,2] for j in [0,1,2]],key=lambda x: x.count(0))

        # Only put in guesses for the first one...
        
        found = False
        for qq in quads:
            q = qq[0]
            diff = nums - set(q)
            i = qq[1]
            j = qq[2]
            for k in itertools.permutations(diff):
                node = Node(list(self.grid))
                for m in k:
                    y,x = divmod(q.index(0),3)
                    node.grid[3*y+i][3*x+j] = m
                #check if this insertion is valid and only then insert it
                # as a child node
                if valid(node.grid):
                    self.children.append(node)
                    print "New child:",
                    for a in node.grid:
                        print a
                    found = True
            if found:
                break
                    
def quads(grid):
    return [quad(grid,i,j) for i in [0,1,2] for j in [0,1,2]]
def valid(grid):
    # A grid is valid if the current quadrant row and column only
    # contain the number once, we don't check 0s
    return all(map(lambda x: len(set(x)) ==  len(filter(None,x)),x+zip(*x)+quads))
        
def quad(arr,x,y):
    out = []
    for i in xrange(x*3,x*3+3):
        for j in xrange(y*3,y*3+3):
            out.append(arr[i][j])
    return out
def solved(x):
    return all(map(lambda x: set(x) == nums,x+zip(*x)+quads))
def solve(x):
    root = Node(x)
    #queue = collections.deque([root])
    queue = []
    heapq.heappush(queue,(0-root.answered,root))
    while queue:
        t = heapq.heappop(queue)[1]
        # Could sort the queue by number of points remaining to be solved
        if solved(t.grid):
            return t.grid
        t.generateChildren()
        for i in t.children:
            heapq.heappush(queue,(0-i.answered,i))
        
    return False
s = 0
with open('sudoku.txt') as f:
    for i in xrange(0,50):
        print f.readline().strip() 
        array = []
        for j in xrange(0,9):
            array.append(map(int,list(f.readline().strip())))
        #Solve the array
        array = solve(array)
        if array:
            for j in array:
                print " ".join(map(str,j))
            s += sum(array[0][:3])
        else:
            print "No solution"   
print s