题解 | pyhon3递归回溯#Sudoku#

递归回溯思路：

每一次往下延展，棋盘会多一个值

有几个0，递归就有多深。每递归一次，就填满一个0，直到棋盘填满，递归结束，返回True

// 检验填入的k是否满足条件不重复
def isValid(row, col, k, board):
    // 判断在该行是否符合
    for i in board[row]:
        if k == i:
            return False
    // 判断在该列是否符合
    for rows in board:
        if k == rows[col]:
            return False
    // 判断在九宫格里是否符合
    row_start = int(row/3)*3
    col_start = int(col/3)*3
    for i in range(row_start,row_start+3):
        for j in range(col_start, col_start+3):
            if board[i][j]==k:
                return False
    return True

// 回溯函数返回的是bool值

def backtracking(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] != '0':
                continue
            for k in range(1,10):
                if isValid(i, j, str(k), board):
                    board[i][j] = str(k)
                    // 开始递归
                    if backtracking(board):
                        return True
            		// 回溯，去掉 0
					board[i][j] = '0'

            else:
                return False
    return True

while True:
    try:
        board = []
        for i in range(9):
            row = input().split()
            board.append(row)
        backtracking(board)
        for row in board:
            print(" ".join(row))
    except:
        break