Python sudoku solver doesn't return a solution

Question

I've been writing this program, bit by bit, testing that each part worked before carrying on. However, when I finished and put everything together, I couldn't get a solution. I was trying to solve the sudoku by creating a list of possible numbers for each square, and by removing them based on the existing square. I assumed that when there was only one possible number in a square, that would be the solution. And it would loop through, until it finished.

I've been looking through my code for half an hour and still no luck. I inserted a raw_input("") to see if there was any problems. I found that it made some progress at the beginning, but then it stopped.

So I printed the possible numbers for a coordinate and somewhere in the process, every possibility was deleted.

Here is what the code looks like now:

# Create the Sodoku grid
grid = [[3,2,0,1,6,0,8,0,9],
        [0,7,8,9,0,3,1,2,6],
        [6,0,0,8,0,0,4,5,3],
        [7,1,0,4,0,0,0,6,2],
        [5,4,0,0,0,0,0,0,7],
        [0,0,0,2,0,5,3,1,0],
        [0,5,9,7,4,0,2,0,8],
        [2,0,7,5,0,9,0,0,0],
        [8,6,4,0,0,0,0,9,5],]

# Create possibilities
possible = {}
for y in range(9):
    for x in range(9):
        possible[(y,x)] = [1,2,3,4,5,6,7,8,9]

# A function that returns the row it is in.
def check_row(y,x):
    return grid[y]

# A function that returns the column it is in.
def check_column(y,x):
    column = []
    for hops in range(9):
        column.append(grid[hops][x])
    return column

# A function that returns the square it is in.
#  ------------- 
# 1| 0 | 1 | 2 |
#  -------------
# 2| 3 | 4 | 5 |
#  -------------
# 3| 6 | 7 | 8 |
#  -------------
#    1   2   3
def check_square(they,thex):

    square0 = []
    square1 = []
    square2 = []
    square3 = []
    square4 = []
    square5 = []
    square6 = []
    square7 = []
    square8 = []

    for y in range(3):
        for x in range(3):
             square0.append([y,x])

    for y in range(3):
        for x in range(3,6):
            square1.append([y,x])

    for y in range(3):
        for x in range(6,9):
            square2.append([y,x])

    for y in range(3,6):
        for x in range(3):
            square3.append([y,x])

    for y in range(3,6):
        for x in range(3,6):
            square4.append([y,x])

    for y in range(3,6):
        for x in range(6,9):
            square5.append([y,x])

    for y in range(6,9):
        for x in range(3):
            square6.append([y,x])

    for y in range(6,9):
        for x in range(3,6):
            square7.append([y,x])

    for y in range(6,9):
        for x in range(6,9):
            square8.append([y,x])

    tests = [square0,
             square1,
             square2,
             square3,
             square4,
             square5,
             square6,
             square7,
             square8]

    square_list = []

    def list_of_grid(result):
        for cood in result:
            [they,thex] = cood
            square_list.append(grid[they][thex])


    # Check which square it of and print the list of grid
    for test in tests:
        if [they,thex] in test:
            list_of_grid(test)

    return square_list


# Function that eliminates row possibilities
def elim_row(y, x):

    get_rid_of = []
    for element in check_row(y, x):
        if element != 0:
            get_rid_of.append(element)

    for stuff in get_rid_of:
        try:
            if stuff in possible[(y,x)]:
                possible[(y,x)] = []
            else:
                possible[(y,x)].remove(stuff)
        except ValueError:
            pass

# Funciton that eliminates column possibilites
def elim_column(y, x):

    get_rid_of = []
    for element in check_column(y, x):
        if element != 0:
            get_rid_of.append(element)

    for stuff in get_rid_of:
        try:
            if stuff in possible[(y,x)]:
                possible[(y,x)] = []
            else:
                possible[(y,x)].remove(stuff)
        except ValueError:
            pass

# Function that eliminates square possibilites
def elim_square(y, x):

    get_rid_of = []
    for element in check_square(y, x):
        if element != 0:
            get_rid_of.append(element)

    for stuff in get_rid_of:
        try:
            if stuff in possible[(y,x)]:
                possible[(y,x)] = []
            else:
                possible[(y,x)].remove(stuff)     
        except ValueError:
            pass

# Check if done:
def done():
    empty = 0
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                empty += 1
    if empty == 0:
        return True
    else:
        return False

# print grid
if __name__ == "__main__":
    # Go through each row, column and square and delete possibilites
    while done != True:

        raw_input("")

        for cood in possible.keys():
            (y, x) = cood

            elim_row(y,x)
            elim_column(y,x)
            elim_square(y,x)

            # Check if len of possible == 1
            if len(possible[cood]) == 1:
                grid[y][x] = possible[cood][0]

        print possible[(0,2)]
        for rows in grid:
            print rows

Answer 1

You never call done(). You only test if the function object is never equal to True:

while done != True:

Function objects are never equal to True. Don't test for equality here, just call the function:

while not done():

Next, in elim_row() you clear the possible values whenever you loop over the values to eliminate:

for stuff in get_rid_of:
    try:
        if stuff in possible[(y,x)]:
            possible[(y,x)] = []
        else:
            possible[(y,x)].remove(stuff)
    except ValueError:
        pass

That sets possible[(y,x)] to an empty value for any value in the row not 0. You do the same in your other 2 elim_ functions.

You probably wanted to use:

for stuff in get_rid_of:
    if stuff in possible[(y,x)]:
        possible[(y,x)].remove(stuff)

This will clear your possibilities real fast.