LeetCode 37. 解数独（难）

约束编程：基本的意思是在放置每个数字时都设置约束。在数独上放置一个数字后立即排除当前行、列和子方块对该数字的使用。这会传播 约束条件 并有利于减少需要考虑组合的个数。
回溯算法：让我们想象一下已经成功放置了几个数字在数独上。但是该组合不是最优的并且不能继续放置数字了。该怎么办？ 回溯。意思是回退，来改变之前放置的数字并且继续尝试。如果还是不行，再次回溯。

题目

编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

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

示例

数独及其解，答案被标成红色。

250px-Sudoku-by-L2G-20050714.png
250px-Sudoku-by-L2G-20050714_solution.png

考察知识点

哈希表、回溯算法
回溯算法模板

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)  # 路径就是要添加的结果
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

核心思想

方法一、暴力破解

首先的想法是通过蛮力法来生成所有可能用1 到 9填充空白格的解，
并且检查合法从而保留解。这意味着共有 \(9^{81}\)个操作需要进行。
其中 \(9\) 是可行的数字个数，\(81\) 是需要填充的格子数目。
因此我们必须考虑进一步优化。

方法二、回溯法

两个本方法中用到的重要概念

  • 1、约束编程

基本的意思是在放置每个数字时都设置约束。在数独上放置一个数字后立即排除当前行、列和子方块对该数字的使用。这会传播 约束条件 并有利于减少需要考虑组合的个数。这个情况在N皇后问题中也出现过，N皇后问题也考虑了回溯算法。这说明约束编程和回溯算法一般都会复共同出现，约束编程可以视为一种剪枝策略。 7.png

  • 2、回溯算法 让我们想象一下已经成功放置了几个数字在数独上。 但是该组合不是最优的并且不能继续放置数字了。该怎么办？ 回溯。 意思是回退，来改变之前放置的数字并且继续尝试。如果还是不行，再次回溯。 8.png

获取子块id的方法 关于获取3x3方子块的方法，可以参照36题，方块索引= (行 / 3) * 3 + 列 / 3 ，其中 / 是向下取整的除法。

算法 现在准备好写回溯函数了
backtrack(row = 0, col = 0)
- 从最左上角的方格开始 row = 0, col = 0。直到到达一个空方格，解决数独问题，也是一个3x3方格一个3x3方格的处理。 - 从 1 到 9 迭代循环数组，尝试放置数字 d 进入 (row, col) 的格子。 - 如果数字 d 还没有出现在当前行，列和子方块中： - 将 d 放入 (row, col) 格子中。 - 记录下 d 已经出现在当前行，列和子方块中。 - 如果这是最后一个格子row == 8, col == 8 ： - 意味着已经找出了数独的解，退出。 - 否则 - 放置接下来的数字。 - 如果数独的解还没找到：将最后的数从 (row, col) 移除。

代码步骤（这道题的解法和N皇后很像）
1、定义could_place方法，检测该位置，是否可以放置该数字。
2、定义place_number方法，将数放置到对应位置，并添加rows、columns、boxes约束。
3、定义remove_number方法，将某个位置的数据去掉，替换回'.'，同时去掉约束。
4、定义place_next_numbers方法。进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
4.1、如果是最后一行，最后一列，使用nonlocal关键字用来在函数或其他作用域中使用外层(非全局)。设置sudoku_solved为True 标记已经解决了该数独问题。
4.2、否则，判断是否是最后的一列，是的话折返去下一行。不然，就在本行中递归调用回溯函数。
5、定义backtrack回溯函数
5.1、如果当前位置是空的，也就是'.'，就从1到10，一个一个的填进去试试。
5.1.1、先判断该位置能不能放这个数，如果没有被约束，就将这个数放到这个位置。
5.1.2、然后调用place_next_numbers，进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
5.1.3、如果没有解决，就执行撤销操作。
5.2、否则调用place_next_numbers方法，测下一个位置。
6、用lambad函数 计算box_index，初始化init rows, columns and boxes，并建立约束。将str的数独输入转化成int类型。声明终止条件sudoku_solved为False并调用backtrack()。

LeetCode题解

Python版本

回溯法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
from typing import List
from collections import defaultdict

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        # 定义could_place方法，检测该位置，是否可以放置该数字。
        def could_place(d, row, col):
            """
            Check if one could place a number d in (row, col) cell
            """
            return not (d in rows[row] or d in columns[col] or d in boxes[box_index(row, col)])

        # 定义place_number方法，将数放置到对应位置，并添加rows、columns、boxes约束。
        def place_number(d, row, col):
            """
            Place a number d in (row, col) cell
            """
            rows[row][d] += 1
            columns[col][d] += 1
            boxes[box_index(row, col)][d] += 1
            board[row][col] = str(d)  # 注意这里填入的str

        # 定义remove_number方法，将某个位置的数据去掉，替换回'.'，同时去掉约束。
        def remove_number(d, row, col):
            """
            Remove a number which didn't lead 
            to a solution
            """
            del rows[row][d]
            del columns[col][d]
            del boxes[box_index(row, col)][d]
            board[row][col] = '.'

        # 定义place_next_numbers方法。进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
        def place_next_numbers(row, col):
            """
            Call backtrack function in recursion
            to continue to place numbers
            till the moment we have a solution
            """
            # if we're in the last cell
            # that means we have the solution
            if col == N - 1 and row == N - 1:  # 如果是最后一行，最后一列。
                nonlocal sudoku_solved  # 使用nonlocal关键字用来在函数或其他作用域中使用外层(非全局)变量。
                sudoku_solved = True  # 设置sudoku_solved为True 标记已经解决了该数独问题
            #if not yet    
            else:
                # if we're in the end of the row
                # go to the next row
                if col == N - 1: # 如果是最后的一列，折返去下一行。
                    backtrack(row + 1, 0)
                # go to the next column
                else:  # 如果不是最后一列 就在本行中递归调用回溯函数
                    backtrack(row, col + 1)

        # 定义backtrack回溯函数
        def backtrack(row = 0, col = 0):
            """
            Backtracking
            """
            # if the cell is empty
            if board[row][col] == '.':  # 如果当前位置是空的，也就是'.'，就从1到10，一个一个的填进去试试。
                # iterate over all numbers from 1 to 9
                for d in range(1, 10):  
                    if could_place(d, row, col):  # 先判断该位置能不能放这个数
                        place_number(d, row, col)  # 如果没有被约束，就将这个数放到这个位置。
                        place_next_numbers(row, col)  # 然后调用place_next_numbers，进行一些place_number之后的操作，比如终止循环、同行依次递归、异行折行递归。
                        if not sudoku_solved:  # 利用sudoku_solved判定数独是否解决
                            remove_number(d, row, col)  # 如果没有解决，就执行撤销操作。
            else:  # 否则调用place_next_numbers方法，检测下一个位置。
                place_next_numbers(row, col) 

        # box size
        n = 3
        # row size
        N = n * n
        # lambda function to compute box index  用lambad函数 计算box_index
        box_index = lambda row, col: (row // n ) * n + col // n
        
        # init rows, columns and boxes  用defaultdict初始化init rows, columns and boxes
        rows = [defaultdict(int) for i in range(N)]
        columns = [defaultdict(int) for i in range(N)]
        boxes = [defaultdict(int) for i in range(N)]
		# 将str的数独输入转化成int类型，并建立约束。
        for i in range(N):
            for j in range(N):
                if board[i][j] != '.': 
                    d = int(board[i][j])
                    place_number(d, i, j)  # 在这里就把每一个已存在数字的约束建立好
        
        # 声明终止条件sudoku_solved为False并调用backtrack()
        sudoku_solved = False
        backtrack()


print("leet code accept!!!")
Input = [
    [
        ["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"]
    ]
]
Answer = [
    [
        ['5', '3', '4', '6', '7', '8', '9', '1', '2'],
        ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
        ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
        ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
        ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
        ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
        ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
        ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
        ['3', '4', '5', '2', '8', '6', '1', '7', '9']
    ]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        solution.solveSudoku(Input[i])
        result = Input[i]
        is_right = True
        for index, row in enumerate(result):
            if result[index] != Answer[i][index]:
                is_right = False
                break
        print(is_right)

时间复杂性
这里的时间复杂性是常数由于数独的大小是固定的，因此没有 N 变量来衡量。
但是我们可以计算需要操作的次数：\((9!)^9\)。
我们考虑一行，即不多于 \(9\) 个格子需要填。
第一个格子的数字不会多于 \(9\) 种情况，
两个格子不会多于 \(9 \times 8\) 种情况，
三个格子不会多于 \(9 \times 8 \times 7\) 种情况等等。
总之一行可能的情况不会多于 \(9!\) 种可能，
所有行不会多于 \((9!)^9\) 种情况。比较一下：
\(9^{81}\) = 196627050475552913618075908526912116283103450944214766927315415537966391196809 为蛮力法，而 \((9!)^{9}\) = 109110688415571316480344899355894085582848000000000 为回溯法，即数字的操作次数减少了 \(10^{27}\) 倍！

空间复杂性
数独大小固定，空间用来存储数独，行，列和子方块的结构，每个有 \(81\) 个元素。

有效语法糖

python3中global 和 nonlocal 的作用域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# global很明显就是声明代码块中的变量使用外部全局的同名变量
a = 1 
def change():
    global a
    a += 1
    print("函数内部的a的值：", a)   # 2
change()
print("调用change函数后， 函数外部的a的值：", a)  # 2

[output]
函数内部的a的值： 2
调用change函数后， 函数外部的a的值： 2

# nolocal 的使用场景就比较单一，它是使用在闭包中的，使变量使用外层的同名变量
def foo(func):
    a = 1
    print("外层函数a的值", a)
    def wrapper():
        func()
        nonlocal a
        a += 1
        print("经过改变后，里外层函数a的值：", a)
    return wrapper

@foo  # 装饰器
def change():
    print("nolocal的使用")
change()

[output]
外层函数a的值 1
nolocal的使用
经过改变后，里外层函数a的值： 2

# 总结：global的作用对象是全局变量，nonlocal的作用对象是外层变量（很显然就是闭包这种情况）

利用lambda函数计算变量

1
box_index = lambda row, col: (row // n ) * n + col // n

Python3的defaultdict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# defaultdict的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值，这个默认值是什么呢，下面会说
# defaultdict接受一个工厂函数作为参数，如下来构造：
dict =defaultdict( factory_function)
# 这个factory_function可以是list、set、str等等，作用是当key不存在时，返回的是工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0，如下举例：

from collections import defaultdict

dict1 = defaultdict(int)
dict2 = defaultdict(set)
dict3 = defaultdict(str)
dict4 = defaultdict(list)
dict1[2] ='two'

print(dict1[1])
print(dict2[1])
print(dict3[1])
print(dict4[1])

输出：
0
set()

[]