Python Sudoku Solver

sudoku.py

#!/usr/bin/env python


puzzle = []

puzzle_s = ("9.5...1..",
            "..18....6",
            "..8.35.49",
            "..9..4..1",
            "78.3.1.65",
            "6..9..4..",
            "35.21.8..",
            "8....96..",
            "..6...5.7",)
for row_s in puzzle_s:
    row = []
    for val in row_s:
        if val == '.':
            row.append(None)
        else:
            row.append(int(val))
    puzzle.append(row)

#possibilities = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
possibilities = []
for x in range(9):
    row = []
    for y in range(9):
        row.append(set([1,2,3,4,5,6,7,8,9]))
    possibilities.append(row)

squares = (
        (0,0), (3,0), (6,0),
        (0,3), (3,3), (6,3),
        (0,6), (3,6), (6,6),
    )

def eliminate():
    eliminated_something = False

    # for each row
    for x in range(9):
        # construct a list of numbers present in that row
        present = set([])
        for y in range(9):
            if puzzle[x][y] is not None:
                present.add(puzzle[x][y])
        # for each cell in that row: eliminate the numbers already present from that cells' possibilities
        for y in range(9):
            old_possibilities = possibilities[x][y].copy()

            possibilities[x][y] = possibilities[x][y] - present

            if possibilities[x][y] != old_possibilities:
                eliminated_something = True

    # for each column
    for y in range(9):
        # construct a list of numbers present in that column
        present = set([])
        for x in range(9):
            if puzzle[x][y] is not None:
                present.add(puzzle[x][y])
        # for each cell in that column: eliminate the numbers already present from that cells' possibilities
        for x in range(9):
            old_possibilities = possibilities[x][y].copy()

            possibilities[x][y] = possibilities[x][y] - present

            if possibilities[x][y] != old_possibilities:
                eliminated_something = True

    # for each square
    for square_x, square_y in squares:
        # construct a list of numbers present in that square
        present = set([])
        for x in range(square_x, square_x + 3):
            for y in range(square_y, square_y + 3):
                if puzzle[x][y] is not None:
                    present.add(puzzle[x][y])
        # for each cell in that square: eliminate the numbers already present from that cells' possibilities
        for x in range(square_x, square_x + 3):
            for y in range(square_y, square_y + 3):
                old_possibilities = possibilities[x][y].copy()

                possibilities[x][y] = possibilities[x][y] - present

                if possibilities[x][y] != old_possibilities:
                    eliminated_something = True

    return eliminated_something

def fill_out_single_possibilities():
    for x in range(9):
        for y in range(9):
            if len(possibilities[x][y]) == 1:
                option, = possibilities[x][y]
                puzzle[x][y] = option

from pprint import pprint
pprint([[(cell if cell is not None else 0) for cell in row] for row in puzzle])
pprint(possibilities)

while eliminate():
    fill_out_single_possibilities()

print("new possibilities")
pprint(possibilities)

pprint([[(cell if cell is not None else 0) for cell in row] for row in puzzle])