Печать работает, но возвращаемое значение равно None при использовании обратного отслеживания для решения судоку

Question

Я написал следующий код, чтобы решить игру Судоку методом возврата. Можно распечатать правильный результат, но я не нашел способа получить тот же результат, что и возвращаемое значение, вместо его печати. Как мне изменить программу, чтобы она работала?

import numpy as np

def find_possible(sudoku,r,c):
    """returns the possible Values as numpy array for a given position"""
    position = sudoku[r, c]
    if position == 0:
        line = sudoku[r, :]
        column = sudoku[: ,c]
        r0 = (r//3)*3
        c0 = (c//3)*3
        square = sudoku[r0:r0+3,c0:c0+3]
        numbers = np.arange(1, 10)
        blocked_numbers = np.unique(np.append(np.append(line,column),square))
        return np.setdiff1d(numbers,blocked_numbers)
    else: return np.array([])

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku,r, c)
            if sudoku[r,c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r,c] = list_of_possible[i]
                    backtrack(sudoku)
                    sudoku[r,c] = 0
                return

    result = sudoku
    print(result)

table = np.array([[5, 3, 0, 0, 7, 0, 0, 0, 0],
                  [6, 0, 0, 1, 9, 5, 0, 0, 0],
                  [0, 9, 8, 0, 0, 0, 0, 6, 0],
                  [8, 0, 0, 0, 6, 0, 0, 0, 3],
                  [4, 0, 0, 8, 0, 3, 0, 0, 1],
                  [7, 0, 0, 0, 2, 0, 0, 0, 6],
                  [0, 6, 0, 0, 0, 0, 2, 8, 0],
                  [0, 0, 0, 4, 1, 9, 0, 0, 5],
                  [0, 0, 0, 0, 8, 0, 0, 7, 9]])

backtrack(table)

РЕДАКТИРОВАТЬ

Если print заменен на return, возврат значение по-прежнему None из-за первого return. И если я дам первое return значение Матрицы судоку, результат не будет окончательным

Answer 1

Вы не передаете результат «назад по дорожке» исходному вызову вашей функции backtrack. (Результат означает, что судоку было решено.) Ваш print работает, потому что вы попадаете на эту строку ровно один раз: когда ваши циклы for заканчиваются после того, как не осталось нулей. Однако на этом решение не заканчивается, и ваше «дерево» вызовов backtrack продолжается. Вы можете убедиться в этом, посмотрев на table: в какой-то момент она была полностью решена (нулей не осталось), но если вы напечатаете ее в конце, там снова будут нули.

С после изменений ваша функция либо возвращает None (как вы делали раньше, я просто добавил None для ясности), либо решенную судоку в sudoku. Внутри for l oop, result хранит результат вызова backtrack, и мы можем проверить, был ли результат None (и мы должны продолжать решать), или мы закончили и можем вернуть result (либо к предыдущему вызову backtrack, либо к исходному вызову вне функции).

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku, r, c)
            if sudoku[r, c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r, c] = list_of_possible[i]
                    result = backtrack(sudoku)
                    if result is not None:
                        return result
                    sudoku[r, c] = 0
                return None
    return sudoku

Кстати, имя result - это просто еще одна ссылка на тот же объект как sudoku. Я подумал, что это может помочь понять, что происходит, но вам это не нужно:

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku, r, c)
            if sudoku[r, c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r, c] = list_of_possible[i]
                    if backtrack(sudoku) is not None:
                        return sudoku
                    sudoku[r, c] = 0
                return None
    return sudoku

Кроме того, попробуйте начать использовать линтер типа Pylint или flake8, который немного проанализирует ваш код для некоторых улучшений. , Например, в Python вместо

for i in range(len(list_of_possible)):

вы можете просто написать

for possible in list_of_possible:

Answer 2

Вам необходимо использовать оператор return. Вместо print(result) используйте return result