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

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

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

思路：

回溯，一个数一个数地试……

不知道为什么board的值会变，所以只好用了一个self.result来存答案

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        from collections import defaultdict
        row, column, squre  = defaultdict(set), defaultdict(set), defaultdict(set)
        fill_list = []
        for i in range(9):
            for j in range(9):
                if board[i][j].isdigit(): #排除掉空的情况
                    row[i].add(board[i][j].encode("utf-8"))
                    column[j].add(board[i][j].encode("utf-8"))
                    squre[(i // 3, j // 3)].add(board[i][j].encode("utf-8"))
                else:
                    fill_list.append([i, j])
                    
        self.result = []           
        def backtrack(idx):
            if idx == len(fill_list):
                for row1 in board:
                    self.result.append(row1[:])
                return
            if not self.result:
                i, j = fill_list[idx][0], fill_list[idx][1]
                for digit in range(1, 10):
                    if str(digit) in row[i] or str(digit) in column[j] or str(digit) in squre[(i // 3, j // 3)]:
                        continue

                    board[i][j] = str(digit)
                    row[i].add(board[i][j])
                    column[j].add(board[i][j])
                    squre[(i // 3, j // 3)].add(board[i][j])

                    backtrack(idx + 1)

                    row[i].remove(board[i][j])
                    column[j].remove(board[i][j])
                    squre[(i // 3, j // 3)].remove(board[i][j])

        backtrack(0)  
        for i in range(9):
            for j in range(9):
                board[i][j] = self.result[i][j]