解决数独游戏的回溯

debugcn 发表于 Dev

富国阮宝

昨天我刚刚学会了回溯，我很困惑。在这个部分

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))

唐·富马雷

这是因为您sudoku()递归调用。因此，您返回1到最后一个调用者，该调用者sudoku()本身来自elif/else路径之一。在这些路径中，您不会返回值。相反，您if/elif/else可以通过返回默认值离开该块并退出该函数None。