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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 17 11:06:48 2019@author: Administrator
"""class Solution:def isValidSudoku(self, board):row = [set(range(1, 10)) for _ in range(9)]  # 行剩余可用数字col = [set(range(1, 10)) for _ in range(9)]  # 列剩余可用数字block = [set(range(1, 10)) for _ in range(9)]  # 块剩余可用数字empty = []  # 收集需填数位置for i in range(9):for j in range(9):if board[i][j] != '.':  # 更新可用数字val = int(board[i][j])row[i].remove(val)col[j].remove(val)block[(i // 3)*3 + j // 3].remove(val)else:empty.append((i, j))def backtrack(iter=0):if iter == len(empty):  # 处理完empty代表找到了答案return Truei, j = empty[iter]b = (i // 3)*3 + j // 3for val in row[i] & col[j] & block[b]:row[i].remove(val)col[j].remove(val)block[b].remove(val)board[i][j] = str(val)if backtrack(iter+1):return Truerow[i].add(val)  # 回溯col[j].add(val)block[b].add(val)return Falsebacktrack()if __name__=="__main__":Solution().isValidSudoku([["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"]])