Рекурсия судоку грубой силы в Python

Я попытался реализовать подход грубой силы к решению головоломки судоку с помощью Python, как описано в следующей ссылке: http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm

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

Вот мой код для рекурсии:

def recurse(x, k, grid):
    if x > 8:
        for line in grid:
            print line
        raw_input()
    if grid[x][k] == '0':
        for number in '123456789':
            if clear(number, x, k, grid):
                grid[x] = grid[x][0:k] + number + grid[x][k+1:]           
                k += 1
                if k > 8:
                    x += 1
                    k = 0
                recurse(x, k, grid)
                k -= 1
                if k < 0:
                    x -= 1
                    k = 8
    else:
        k += 1
        if k > 8:
            x += 1
            k = 0
        recurse(x, k, grid)

По сути, я храню судоку в массиве слотов 9x9, где grid[x] обращается к x-й строке всего судоку, а grid[x][k] обращается к k-му числу в x-й строке.

Там есть функция под названием «очистить», которая определяет, может ли определенное число поместиться в этот слот или нет. Я проверял его много раз, и он работает правильно. Проблема здесь в том, что значение «x» никогда не превышает 8, что означает, что судоку никогда не достигает конца. Рекурсия останавливается до того, как все слоты будут заполнены правильно. Я совершенно неопытен в написании рекурсивных методов, поэтому, пожалуйста, потерпите меня.

Я полагал, что если число помещается в ячейку, то это число помещается в эту ячейку, а затем k увеличивается. Если k больше 8, это означает, что это конец строки, поэтому мы переходим к следующей строке. Затем рекурсивная функция вызывается снова. Если рекурсивная функция завершается, не имея возможности снова вызвать себя, это означает, что в этот слот не помещается число, поэтому мы должны вернуться. В этом случае k уменьшается.

Так в чем именно здесь проблема?


python recursion sudoku
person Community    schedule 19.01.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Добавить grid[x] = grid[x][0:k] + '0' + grid[x][k+1:] после

k -= 1
if k < 0:
    x -= 1
    k = 8

чтобы исправить это.

Чтобы остановить рекурсию, когда решение найдено:

def recurse(x, k, grid):
    if x>8:
        return grid

    if grid[x][k] == '0':
        for number in '123456789':
            if clear(number, x, k, grid):
                grid[x] = grid[x][0:k] + number + grid[x][k+1:]           
                k += 1
                if k > 8:
                    x += 1
                    k = 0
                solution= recurse(x, k, grid)
                if solution:
                    return solution
                k -= 1
                if k < 0:
                    x -= 1
                    k = 8
                grid[x] = grid[x][0:k] + '0' + grid[x][k+1:]      
    else:
        k += 1
        if k > 8:
            x += 1
            k = 0
        return recurse(x, k, grid)
person Aran-Fey    schedule 19.01.2015
comment
Вы правы .. высоко ценится. Ну, вы хоть представляете, как я могу полностью остановить рекурсию, когда x > 8? - person ; 19.01.2015
comment
Сетка возврата не работает, мешает решению, поскольку продолжает возвращаться и изменять ответы. - person ; 19.01.2015
comment
Я не понимаю. Я почти уверен, что возвращенное решение правильное. - person Aran-Fey; 19.01.2015
comment
Если я напечатаю сетку, как только x › 8, решение будет правильным. Если я печатаю сетку после завершения всей рекурсии, решение неверно. :/ - person ; 19.01.2015
comment
Вы используете код, который я разместил? Вы уверены, что печатаете решение? solution = recurse(0, 0, sudoku). - person Aran-Fey; 19.01.2015