解决数独游戏的回溯

Question

昨天刚学回溯，一头雾水。本节

if y == 9:
    if x == 8:
        display(s)
        return 1
    else:
        sudoku(s,x+1,0)

我使用 return 停止运行程序，但 print(sudoku(s,0,0)) 仍然打印 None 值而不是 1。谁能知道为什么？

s = [[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]]


def display(s):
    for i in s:
        print(*i)


def checkvalid(s,x,y,k):
    for i in range(9):
        if s[x][i] == k or s[i][y] == k:
            return False
    for i in range(x//3*3, x//3*3+3):
        for j in range(y//3*3, y//3*3+3):
            if s[i][j] == k:
                return False
    return True


def sudoku(s,x,y):
    if y == 9:
        if x == 8:
            display(s)
            return 1
        else:
            sudoku(s,x+1,0)
    elif s[x][y] == 0:
        for k in range(1,10):
            if checkvalid(s,x,y, k):
                s[x][y] = k
                sudoku(s,x,y+1)
                s[x][y] = 0
    else:
        sudoku(s,x,y+1)


print(sudoku(s,0,0))

Answer 1

这是因为你递归调用了sudoku()。因此，您 return 1 到最后一个调用者，它是来自 elif/else 路径之一的 sudoku() 本身。在这些路径中，您不会 return 返回值。相反，您离开 if/elif/else 块并通过 returning 默认值 None.

退出函数

解决数独游戏的回溯

solving a backtracking of sudoku game

python

return

sudoku

backtracking

python-3.x