Решатель судоку на Python

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

alist = [1,2,3,4,5,6,7,8,9]

def checkSudoku(grid):
    a = grid
    b = grid
    c = grid
    d = False
    e = False
    f = False
    newlist = []
    for i in a:
        i.sort()
        if i == alist:
            d = True
        else:
            d = False
            break
    for j in range(9):
        for k in b:
            newlist.append(k)

        newlist.sort()
        if i == alist:
            e = True
            newlist = []
        else:
            e = False
            break

    if d == True and e == True:
        return True
    else:
        return False

По сути, My должен был проверить все три фактора, необходимые для того, чтобы это было правдой, затем вернуть True, если все три верны, иначе вернуть false. Любая помощь?


python sudoku
person user3483844    schedule 22.04.2014    source источник
comment
Хорошие новости: кто-то уже решил именно эту проблему. norvig.com/sudoku.html   -  person Casey    schedule 22.04.2014
comment
Предложение по улучшению вашего кода: используйте лучшие имена переменных. Я не могу понять, что означают ваши переменные с a по f, не покопавшись в куче кода. Если бы у них были осмысленные имена, я мог бы сразу увидеть проблемы. Однобуквенные имена переменных часто плохи, за исключением очень ограниченных ситуаций (i и j часто являются традиционными индексными переменными в циклах, а x, y и z имеют давнюю математическую традицию в качестве имен координат и т. д.).   -  person Blckknght    schedule 22.04.2014
comment
Каждый раз, когда вы устанавливаете переменную в False, вы можете просто вернуть False. Вам также может быть интересно взглянуть на класс set.   -  person U2EF1    schedule 22.04.2014
comment
@emodendroket Если этот вопрос был решен в другом месте на Stack Overflow, то его можно пометить как дубликат. Однако нет ничего плохого в том, чтобы задать вопрос, на который уже есть ответ извне.   -  person SimonT    schedule 22.04.2014
comment
@SimonT Это не было критикой. Что-то не так с публикацией ссылки на стороннее решение проблемы?   -  person Casey    schedule 22.04.2014
comment
@emodendroket Нет, я неправильно понял ваше намерение. Виноват.   -  person SimonT    schedule 22.04.2014

Ответы (2)


arrow_upward
1
arrow_downward

Не уверен, что это ваша проблема, но в этом коде есть довольно очевидная проблема:

a = grid
b = grid
c = grid

Похоже, вы думаете, что это создает 3 копии сетки, но это не так. Он создает три разные ссылки на один и тот же объект. Это означает, что ваше i.sort() на a позже повлияет на логику на b.

Что вам нужно сделать, так это скопировать объект. То, что это вложенный список, делает это немного сложным, но простой способ сделать это с помощью библиотечной функции deepcopy:

a = copy.deepcopy(grid)
b = copy.deepcopy(grid)
c = copy.deepcopy(grid)
person wvdz    schedule 22.04.2014
comment
Более простое решение может состоять в том, чтобы сделать копию, когда вы выполняете сортировку подсписка, используя функцию sorted. Тогда вообще не нужно иметь несколько копий сетки! - person Blckknght; 22.04.2014

arrow_upward
1
arrow_downward

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

for row in grid:
    if sorted(row) == alist:
        # now you know that the row contains all ints 1-9.

Это также означает, что вам не нужно пытаться вручную дублировать grid. Если вам нужна помощь в дублировании list (особенно многомерного list), проверьте этот вопрос.

Что касается проверки каждого поля 3x3: сначала выполните итерацию по каждому из 9 «верхних левых» углов следующим образом:

for x in (0,3,6):
    for y in (0,3,6):
        subgrid = grid[y][x:x+3] + grid[y+1][x:x+3] + grid[y+2][x:x+3]
        if sorted(subgrid) == alist:
            # do your thing

Чтобы получить помощь по нарезке списка, проверьте это.

person SimonT    schedule 22.04.2014