Решатель Python sudoku не возвращает решение

Question

Я писал эту программу постепенно, проверяя, что каждая часть работала, прежде чем продолжить. Однако, когда я закончил и собрал все вместе, я не смог найти решение. Я пытался решить судоку, создав список возможных чисел для каждого квадрата и удалив их на основе существующего квадрата. Я предполагал, что когда в квадрате будет только одно возможное число, это будет решением. И это будет проходить, пока не закончится.

Я полчаса просматривал свой код и до сих пор не повезло. Я вставил raw_input("") чтобы увидеть, есть ли проблемы. Я обнаружил, что вначале был достигнут некоторый прогресс, но затем он остановился.

Таким образом, я напечатал возможные числа для координаты и где-то в процессе, каждая возможность была удалена.

Вот как выглядит код сейчас:

# 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

Ты никогда не звонишь done(), Вы проверяете только, если объект функции никогда не равен True:

while done != True:

Функциональные объекты никогда не равны True, Не проверяйте здесь равенство, просто вызовите функцию:

while not done():

Далее в elim_row() Вы очищаете возможные значения всякий раз, когда вы перебираете значения для исключения:

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

Это устанавливает possible[(y,x)] пустое значение для любого значения в строке не 0. Вы делаете то же самое в других 2 elim_ функции.

Вы, вероятно, хотели использовать:

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

Это быстро очистит ваши возможности.