Brute force sudoku cracker

[Bas]

Hi group,

I came across some of these online sudoku games and thought after
playing a game or two that I'd better waste my time writing a solver
than play the game itself any longer. I managed to write a pretty dumb
brute force solver that can at least solve the easy cases pretty fast.

It basically works by listing all 9 possible numbers for all 81 fields
and keeps on striking out possibilities until it is done.

-any ideas how to easily incorporate advanced solving strategies?
solve(problem1) and solve(problem2) give solutions, but solve(problem3)
gets stuck...

-any improvements possible for the current code? I didn't play a lot
with python yet, so I probably missed some typical python tricks, like
converting for-loops to list expressions.

TIA,
Bas

***********

from itertools import ifilterfalse

problem1 = [' 63   7  ',
            '   69   8',
            '9    7  2',
            '  2 1  8 ',
            ' 5 8 6 9 ',
            ' 9  7 2  ',
            '6  1    3',
            '7   45   ',
            '  9   14 ']

problem2 = [' 3   9  7',
            ' 1  8    ',
            '   1   9 ',
            '  49 5  6',
            ' 2     1 ',
            '5  6 74  ',
            ' 5   1   ',
            '    4  2 ',
            '7  5   3 ']

problem3 = [' 3 5  81 ',
            '   76  9 ',
            '4        ',
            ' 439 5  6',
            ' 1     7 ',
            '6  8 193 ',
            '        9',
            ' 9  86   ',
            ' 61  2 8 ']

#define horizontal lines, vertical lines and 3x3 blocks
groups = [range(9*i,9*i+9) for i in range(9)] + \
         [range(i,81,9) for i in range(9)] + \
         [range(0+27*i+3*j,3+27*i+3*j) + range(9+27*i+3*j,12+27*i+3*j)
+ \
          range(18+27*i+3*j,21+27*i+3*j) for i in range(3) for j in
range(3)]

def display(fields):
    for i in range(9):
        line = ''
        for j in range(9):
            if len(fields[9*i+j]) == 1:
                line += ' ' + str(fields[9*i+j][0])
            else:
                line += '  '
        print line


def all(seq, pred=bool):
    "Returns True if pred(x) is True for every element in the iterable"
    for elem in ifilterfalse(pred, seq):
        return False
    return True

def product(seq):
    prod = 1
    for item in seq:
        prod *= item
    return prod

def solve(problem):
    fields = [range(1,10) for i in range(81)] #fill with all
posibilities for all fields
    for i,line in enumerate(problem):
        for j,letter in enumerate(line):
            if letter != ' ':
                fields[9*i+j]=[int(letter)] #seed with numbers from
problem
    oldpos = 0
    while True:
        pos = product(len(field) for field in fields)
        if pos == oldpos: #no new possibilities eliminated, so stop
            break
        display(fields)
        print pos,'possibilities'
        oldpos = pos
        for group in groups:
            for index in group:
                field = fields[index]
                if len(field) == 1: #if only number possible for field
remove it from other fields in group
                    for ind in group:
                        if ind != index:
                            try:
                                fields[ind].remove(field[0])
                            except ValueError:
                                pass
                else: #check if field contains number that does not
exist in rest of group
                    for f in field:
                        if all(f not in fields[ind] \
                               for ind in group if ind!=index):
                            fields[index] = [f]
                            break