Brute force sudoku cracker

[poissonnier at gmail.com]

Had the same reaction as everyone when I saw theses puzzles a month or
so ago, so here is my solution...
the solve function is recursive, so it can also solve the 'deadlock
set' (example3). find_cell looks for an empty cell with the most filled
cells in it's row and column, so the search tree doesn't grow too
'wide'.

-----------------------------------

example1 = """8 9 - - - - 3 - 4
- - 5 - 3 - - - -
- 7 - - 8 1 5 - -
- 4 - - - 7 - - 3
- - - 5 4 3 - - -
2 - - 1 - - - 5 -
- - 7 9 1 - - 4 -
- - - - 7 - 2 - -
9 - 8 - - - - 7 5"""

example2 = """- 5 2 - - - - - -
9 - - 1 - - - 5 -
- - 4 8 3 - - - 2
- 3 - - 9 - 1 - 5
- - - - - - - - -
5 - 7 - 6 - - 4 -
1 - - - 7 3 6 - -
- 7 - - - 9 - - 3
- - - - - - 2 7 -"""

example3 = """- 3 - 5 - - 8 1 -
1 - - 7 6 - - 9 -
4 - - - - - - - -
8 4 3 9 7 5 1 2 6
- 1 - 6 - - - 7 8
6 - - 8 - 1 9 3 -
- - - 1 5 7 - - 9
- 9 - - 8 6 - - 1
- 6 1 - 9 2 - 8 -"""

class ImpossibleException(Exception): pass


def field_from_string(field_str):
    def mapper(x):
        if x == '-': return None
        else: return int(x)
    return [map(mapper, line.split()) for line in
field_str.split('\n')]


def field_from_file(filename):
    f = open(filename)
    field = field_from_string(f.read())
    f.close()
    return field


def print_field(field):
    def mapper(x):
        if x == None: return '  '
        else: return str(x)+' '
    str_rows = [map(mapper, x) for x in field]
    str_rows = ['| ' + " ".join(str_row) + '|' for str_row in str_rows]
    print 'x'+'-'*27+'x'
    print "\n".join(x for x in str_rows)
    print 'x'+'-'*27+'x'


def check_constraint(field, (x,y), num):
    """Checks if putting num at (x,y) is valid."""
    #row constraint
    occ = [elem for elem in field[x] if elem == num]
    if occ:
        return False
    #column constraint
    occ = [field[k][y] for k in range(9) if field[k][y] == num]
    if occ:
        return False
    #subfield constraint
    sub_x, sub_y = x//3, y//3
    occ = [field[k+3*sub_x][l+3*sub_y] for k in range(3) for l in
range(3)
        if field[k+3*sub_x][l+3*sub_y] == num]
    if occ:
        return False
    return True


def find_cell(field):
    """Returns coords of an empty cell or None if all cells are filled.
    Returns cells with most row and column 'neighbours' first."""
    def count(row):
        return len([x for x in row if x is not None])

    #[(count, index), ... ]
    x_counts = zip((count(row) for row in field), range(9))
    sorted_x_counts = sorted(x_counts, reverse=True)
    x_keys = [l for k,l in sorted_x_counts]

    columns = [[field[k][y] for k in range(9)] for y in range(9)]
    y_counts = zip((count(column) for column in columns), range(9))
    sorted_y_counts = sorted(y_counts, reverse=True)
    y_keys = [l for k,l in sorted_y_counts]

    for x in x_keys:
        for y in y_keys:
            if field[x][y] == None:
                return (x,y)
    else:
        return None


def set_value(field, (x,y), num):
    """Returns copy of field with cell (x,y) set to num."""
    #new_field = copy.deepcopy(field)
    new_field = [row[:] for row in field]
    new_field[x][y] = num
    return new_field


def solve(field):
    xy = find_cell(field)
    if not xy:
        return field
    poss = [e for e in range(1,10) if check_constraint(field, xy, e)]
    for e in poss:
        new_field = set_value(field, xy, e)
        try:
            return solve(new_field)
        except ImpossibleException:
            pass #try next possibility
    raise ImpossibleException()


if __name__ == '__main__':
    field = field_from_string(example3)
    print 'initial field:'
    print_field(field)
    print 'solution:'
    try:
        print_field(solve(field))
    except ImpossibleException:
        print 'not solvable'