解数独--python

解数独

题目描述
编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3
宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

代码

def is_valid(row,col,val,board):
    for i in range(9):
        if board[i][col]==val or board[row][i]==val:
            return False
    row_=(row//3)*3
    col_=(col//3)*3
    for i in range(row_,row_+3):
        for j in range(col_,col_+3):
            if board[i][j]==val:
                return False
    return True
def backtrack(board):
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j]!='.':
                continue
            for k in range(1,10):
                if is_valid(i,j,str(k),board):
                    board[i][j]=str(k)
                    if backtrack(board):
                        return True
                    board[i][j]='.'
            return False
    return True
if __name__=='__main__':
    board = [["5","3",".",".","7",".",".",".","."],
             ["6",".",".","1","9","5",".",".","."],
             [".","9","8",".",".",".",".","6","."],
             ["8",".",".",".","6",".",".",".","3"],
             ["4",".",".","8",".","3",".",".","1"],
             ["7",".",".",".","2",".",".",".","6"],
             [".","6",".",".",".",".","2","8","."],
             [".",".",".","4","1","9",".",".","5"],
             [".",".",".",".","8",".",".","7","9"]]
    backtrack(board)
    print(board)

输出结果