37解数独

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

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

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

一个数独。

答案被标成红色。

Note:

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

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

Solution 1

递归填空
执行用时：412 ms
内存消耗：13.8 MB

class Solution:
    def solveSudoku(self, board: [[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        def getNext(board, row, col, box):
            minCount = 10
            minI = 0
            minJ = 0
            for i in range(9):
                for j in range(9):
                    number = board[i][j]
                    k = int(i/3)*3 + int(j/3)
                    if (number != '.'):
                        continue
                    # calculate count of fills
                    count = 0
                    for num in map(str, range(1, 10)):
                        if not (row[i].get(num) or col[j].get(num) or box[k].get(number)):
                            count += 1
                    if (count < minCount):
                        minCount = count
                        minI = i
                        minJ = j
                    # end loop
                    if minCount == 0:
                        break
                if minCount == 0:
                    break
            # return information of next fill
            i = minI
            j = minJ
            k = int(i/3)*3 + int(j/3)
            fills = []
            for num in map(str, range(1, 10)):
                if not (row[i].get(num) or col[j].get(num) or box[k].get(num)):
                    fills.append(num)
            isFull = True
            for line in board:
                if ('.' in line):
                    isFull = False
                    break
            return i, j, fills, isFull

        def RecursivelyFillBoard(board, row, col, box):
            i, j, fills, isFull = getNext(board, row, col, box)
            if isFull:
                return True
            if fills == []:
                return False
            k = int(i/3)*3 + int(j/3)
            for num in fills:
                board[i][j] = num
                row[i].update({num: True})
                col[j].update({num: True})
                box[k].update({num: True})
                if RecursivelyFillBoard(board, row, col, box):
                    return True
                board[i][j] = '.'
                row[i].update({num: False})
                col[j].update({num: False})
                box[k].update({num: False})

        # solveSudoku
        row = [{}, {}, {}, {}, {}, {}, {}, {}, {}, ]
        col = [{}, {}, {}, {}, {}, {}, {}, {}, {}, ]
        box = [{}, {}, {}, {}, {}, {}, {}, {}, {}, ]
        for i in range(9):
            for j in range(9):
                number = board[i][j]
                k = int(i/3)*3 + int(j/3)
                if (number == '.'):
                    continue
                if not (row[i].get(number)):
                    row[i].update({number: True})
                if not (col[j].get(number)):
                    col[j].update({number: True})
                if not (box[k].get(number)):
                    box[k].update({number: True})

        RecursivelyFillBoard(board, row, col, box)