A simple sudoku solver

sudoku.py

"""
A simple sudoku puzzle solver. It uses the observation that an empty position
can only contain labels that are not in any other position on the same row, column or 
square. 

The solver uses a depth first strategy. When a candidate position is filled, that value is 
removed from the list of possible value for all positions on the same row, column or squeare.
This reduces the search space considerably. 

Example:

input.txt

.....6...
.59.....8
2....8...
.45......
..3......
..6..3.54
...325..6
.........
.........

$ cat input.txt | python sudoku.py

"""

import sys

indexes = [(i, j) for i in range(9) for j in range(9)]

def read():
    return [line.strip() for line in sys.stdin.readlines()]

def matching_coordinates(i, j):
    for k in range(9):
        yield i, k
        yield k, j
    rs = i - (i % 3)
    cs = j - (j % 3)
    for i_ in range(rs, rs + 3): 
        for j_ in range(cs, cs + 3):
            yield (i_, j_)

def possible_placements(lines):
    occupied = [((i, j), lines[i][j]) for i, j in indexes if lines[i][j] != "."]
    od = dict(occupied)
    unoccupied = [(i, j) for i, j in indexes if lines[i][j] == "."]
    labels = set(str(i+1) for i in range(9))
    def gen():
        for (i, j) in unoccupied:
            yield ((i, j), labels.difference(set(od[(i_, j_)] for i_, j_ in matching_coordinates(i, j) if od.has_key((i_, j_)))))
    return list(gen())

def dfs(ul):
    res = []
    ud = dict(ul)
    def dfs_():
        if len(ul) == 0:
            return True

        (i, j), items = ul.pop()

        if len(items) == 0:
            ul.append(((i, j), items))
            return False

        for item in list(items):
            cl = ((i_, j_) for i_, j_ in matching_coordinates(i, j) if (i_, j_) in ud)
            rl = []
            
            for i_, j_ in cl:
                s = ud[(i_, j_)]
                if item in s:
                    s.remove(item)
                    rl.append((i_, j_))

            if dfs_() != False:
                res.append(((i, j), item))
                return True

            for i_, j_ in rl:
                ud[(i_, j_)].add(item)

        ul.append(((i, j), items))
        return False
    dfs_()
    return res


def copy_ud(ud):
    for (i_, j_), s in ud.items():
         yield (i_, j_), set(s)

def print_grid(grid):

    for line in grid:
        print "|".join(line)    

def fill_grid(lines, res):
    grid = [list(line) for line in lines]
    for (i, j), v in res:
        assert grid[i][j] == '.', "Found a value where an empty square should be"
        grid[i][j] = v

    for (i, j) in indexes:
        assert grid[i][j] != '.', "Found am empty square when all should have been filled"
    return grid

def validate(grid):
    for i in range(9):
        assert len(set(grid[i][j] for j in range(9))) == 9
        assert len(set(grid[j][i] for j in range(9))) == 9

    for a in range(3):
        for b in range(3):
            i = 3*a
            j = 3*b
            assert len(set(grid[i_][j_] for i_ in range(i, i + 3) for j_ in range(j, j + 3))) == 9

def main():
    lines = read()
    #print_grid(lines)
    ul = possible_placements(lines)
    res = dfs(ul)
    grid = fill_grid(lines, res)
    validate(grid)
    print_grid(grid)

if __name__ == "__main__":
    main()