使用了分治法，贪心法和回溯法解决了循环赛程表，双机流水线调度优化，删k数最小，数独问题四个算法设计问题
分治算法是一种处理问题的策略，其基本思想是将一个复杂的问题分解为两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技术是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等。
分治算法通常遵循以下几个步骤：
- 分解：将原问题分解为若干个规模小，相互独立，与原问题形式相同的子问题。
- 解决：如果子问题规模较小而容易被解决则直接解决，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
分治算法能解决的问题一般具有以下几个特征：
- 问题的规模缩小到一定的程度就可以容易地解决
- 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
如果一个问题满足以上特点，我们就可以使用分治算法来解决。
现在考虑实验题目
设围棋⽐赛有m=2^p (p为正整数）位参赛者。现要设计⼀个满⾜以下要求的循环⽐赛⽐赛⽇程表：
(1)每位选⼿必须与其他m-1位选⼿各赛⼀次；
(2)每位选⼿⼀天只能参赛⼀次；
(3)循环赛在m-1天内结束。
请按此要求将⽐赛⽇程表设计成有m⾏和m-1列的表格。在表中的第i⾏，第j列处填⼊第i个选⼿在第j天所遇到的选⼿。其中1≤i≤n，1≤j≤n-1。
分析：观察八位选手的赛程表示例不难发现，对于8x8的赛程表而言，不难发现，图中左上角的4x4矩阵部分和右下角的4x4的部分相同，左下角4x4矩阵和右上角4x4矩阵部分相同，也就是说我们只需要从一半对称到另一半就可以完成这个矩阵，从而将八位选手的赛程表转化为四位选手的赛程表问题。对于任意2的p次方位选手，我们最终都可以分解为2位选手的情况，而两位选手的日程表安排非常简单，也就是[1,2],[2,1]，因此，可以用递归的算法来循环解决上述赛程表安排问题
可用分治算法解决问题如下：
# 定义一个函数用于显示比赛日程表
def display(table, n):
print("比赛日程表：")
for i in range(n):
for j in range(n):
print(table[i][j], end=" ")
if j == 0:
print("|", end=" ")
print()
def table(k, d):
# 是否是最初条件
if k == d:
return
for i in range(d):
for j in range(d):
a[i + d][j + d] = a[i][j]
a[i][j + d] = a[i][j] + d
a[i + d][j] = a[i][j] + d
table(k, d * 2)
if __name__ == "__main__":
# 输入人数
n = int(input("学生人数k=2^n,请输入k:"))
k = 2 ** n
# 初始化一个全零的二维数组
a = [[0 for _ in range(k)] for _ in range(k)]
# 初始化并判断是否只有一个人参赛
if k == 1:
a[0][0] = 0
else:
a[0][0] = 1
# 递归
table(k, 1)
# 输出
display(a, k)代码解析：在这段代码中，首先定义了一个名为display的函数，用于显示比赛日程表。这个函数接收一个二维数组和一个整数n作为参数，然后打印出这个二维数组，这个二维数组就是比赛日程表。
然后定义了一个名为table的函数，这个函数是用来生成比赛日程表的。这个函数使用了递归的方式来生成日程表。在每一次递归中，它会将当前的日程表分为四个部分，然后对这四个部分进行填充，以生成下一轮的日程表。
在主函数中，首先获取用户输入的参赛者数量，然后初始化一个全零的二维数组作为比赛日程表的初始状态。然后调用table函数来生成比赛日程表，最后调用display函数来显示比赛日程表。
算法体现：前面提到，分治算法的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
在这段代码中，table函数就是使用分治算法来生成比赛日程表的。这个函数接收两个参数，k表示参赛者的数量，d表示当前的比赛轮次。在每一次递归中，它会将当前的日程表分为四个部分，然后对这四个部分进行填充，以生成下一轮的日程表。
具体来说，假设当前的日程表是一个n×n的二维数组，那么在下一轮中，它会将这个二维数组分为四个n/2×n/2的子数组，然后对这四个子数组进行填充。填充的规则是，左上角的子数组保持不变，右上角和左下角的子数组加上d，右下角的子数组与左上角的子数组相同。即：
右上方矩阵=左上方矩阵+规模m
**左下方矩阵=右上方矩阵对称，右下方矩阵=左上方矩阵对称 **
这个过程会一直递归下去，直到d等于k，也就是所有的比赛轮次都已经安排完毕。这时，就得到了最终的比赛日程表。
这种方法的优点是，由于每一次递归都会将问题的规模减半，因此它的时间复杂度是O(n log n)，其中n是参赛者的数量。这使得它能够有效地处理大规模的问题。
现在我们对代码进行调试来看具体的矩阵复制过程：
将断点打在代码第16行，初始化
在一轮循环后，首先完成初始情况，即2名选手的日程表安排：
接着，在第二轮循环里，开始根据左上角2x2矩阵，来完成右上、下，左下角矩阵的复制，先完成了第一个数字的复制：
然后完成第一排的复制：
然后完成第二排第一个数字的复制：
完成第二排的复制，此时，已经完成了4名选手的赛程表：
同理，可以得到最终8名参赛选手的输出：
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这是显然的，如最小生成树，对其它问题却是非常难证明的，如背包问题）。
贪心算法的步骤如下：
- 建立数学模型：将问题抽象化，建立数学模型。
- 把求解的问题分成若干个子问题：对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解：通过求解每一子问题的局部最优，将局部最优解合成全局最优解。
贪心算法适用的问题一般具有以下特征：
- 每个问题都可以分解为小问题。
- 这些小问题之间有最优的顺序，即先做A问题，再做B问题。
- 对每个小问题都可以做出最优的选择，即贪心选择。
- 我们做出的每个选择都无法改变以后的选择，也就是说每个选择都是无后效性的。
如果一个问题满足以上特点，我们就可以使用贪心算法来解决。
现在考虑实验题目：
⽤两台机器加⼯10个零件。这⾥既不能将⼀个零件分开由2台机器处理，也没有⼀台机器能同时处理2个零件。这10个零件交给第⼀台机器处理需要时间为[1 3 5 7 4 2 8 4 9 9]，交给第⼆台机器处理需要时间[1.5 2 6 8 2 1 3 8 11 4]。这⾥假设两台机器都连续⼯作，没有休息时间，请设计⼀个算法，使得这两台机器处理完这10个零件的时间最短，并显示两台机器所处理零件的具体顺序。
分析：这个问题的贪心算法思路可以抽象为以下几个步骤：
- 差值计算和排序：首先，计算每个零件在两台机器上的处理时间差，并按照这个差值进行排序。这一步的目标是找出那些在一台机器上处理时间明显比另一台机器短的零件。
- 零件分配：然后，根据差值的正负，将零件分配给两台机器。如果差值大于0，零件被分配给处理时间较短的机器，否则被分配给另一台机器。这一步的目标是尽可能平衡两台机器的工作负载。
- 尝试优化：最后，尝试通过交换零件的顺序来寻找可能的更优解。创建当前零件顺序的副本，然后交换某两个零件的位置。然后，计算新的处理时间，并如果新的处理时间小于当前的最优解，就更新结果。这一步的目标是尽可能找到更优的零件处理顺序，以进一步减少总的完成时间。
这个算法的关键在于，它在每一步都尽可能做出最优的选择（即贪心的选择），从而达到全局最优解。
import copy
n = 10
a = [1, 3, 5, 7, 4, 2, 8, 4, 9, 9]
b = [1.5, 2, 6, 8, 2, 1, 3, 8, 11, 4]
def gettime(arr):
return sum([x[1] for x in arr])
# 计算每个零件在两台机器上的处理时间差，并排序
parts = sorted([(a[i] - b[i], i) for i in range(n)])
# 分配零件
order_a = []
order_b = []
for diff, i in parts:
if diff > 0:
order_b.append((i+1, a[i]))
else:
order_a.append((i+1, b[i]))
# 逆序 order_a
order_a.reverse()
time_a = gettime(order_a)
time_b = gettime(order_b)
# 计算结果
res = max(time_a, time_b)
print("非优化情况下最短完成时间：", res)
print("非优化情况下机器A处理的零件顺序：", [x[0] for x in order_a])
print("非优化情况下机器B处理的零件顺序：", [x[0] for x in order_b])
# 初始化一个新的 order_a 和 order_b
new_order_a = []
new_order_b = []
for i in range(len(order_a)):
# 创建 order_a 和 order_b 的深拷贝
new_order_a = copy.deepcopy(order_a)
new_order_b = copy.deepcopy(order_b)
# 交换零件
new_order_a[i], new_order_b[i] = new_order_b[i], new_order_a[i]
# 将 new_order_a 中的元素 (i, b[i]) 替换为 (i, a[i])
new_order_a = [(j, a[j-1]) for j, _ in new_order_a]
# 将 new_order_b 中的元素 (i, a[i]) 替换为 (i, b[i])
new_order_b = [(z, b[z-1]) for z, _ in new_order_b]
# 计算时间
new_time_a = gettime(new_order_a)
new_time_b = gettime(new_order_b)
# 更新结果
if max(new_time_a, new_time_b) < res:
res = max(new_time_a, new_time_b)
order_a = new_order_a
order_b = new_order_b
time_a = gettime(order_a)
time_b = gettime(order_b)
print("最短完成时间：", res)
print("机器A处理的零件顺序：", [x[0] for x in order_a])
print("A完成时间：", time_a)
print("机器B处理的零件顺序：", [x[0] for x in order_b])
print("B完成时间：", time_b)最优解分析：
这个问题是一个经典的两台并行机器调度问题，目标是最小化最大完工时间，也被称为P||Cmax问题。这个问题已经被证明是NP-hard的，因此贪心策略的正确性并不能得到严格的数学证明。但是有一个著名的近似算法可以得到2-approximate解，也就是说，这个算法得到的解的质量至少是最优解的一半，该算法就是我未优化前的贪心思路。
我的贪心策略是基于这样的想法：尽可能平衡两台机器的工作负载，并尝试通过交换零件的顺序来寻找可能的更优解。需要注意的是，这种交换策略并不能保证总是能找到最优解。这是因为，交换策略是基于当前的零件分配顺序进行的，而这个顺序是由最初的贪心策略决定的。这个策略在许多情况下都能找到一个很好的解，但不能保证总是找到最优解。
例如，考虑一个极端情况，所有零件在机器A上的处理时间都比在机器B上的处理时间短，但机器A上的最长处理时间比机器B上的所有处理时间都长，在这种情况下，最优解可能是将一部分零件分配给机器B，以减少最大完成时间。
我的贪心策略虽然会将所有零件分配给机器A，然后尝试通过交换零件的顺序来寻找更优解。然而，如果最优解需要将一部分零件分配给机器B，那么这种交换策略可能无法找到最优解，因为交换过程是基于贪心的顺序的。
因此，虽然我的贪心策略在许多情况下都能找到一个很好的解，交换策略可以在一些情况下改进解，但不能保证总是找到最优解。
这个算法的正确性可以从以下两个方面来理解：
- 初始分配策略：这个策略试图平衡两台机器的负载，这是一个合理的策略，因为如果两台机器的负载差距太大，那么总的完成时间就会很长。
- 交换策略：这个策略试图通过交换零件的位置来进一步优化完成时间。这也是一个合理的策略，因为通过交换零件的位置，可能会找到一种更好的分配方案。
可以看到，通过交换策略大大优化了我的算法，但是仍然不能保证算法一定是最优的。
关于动态规划：
对于这个问题，经过分析我认为动态规划（DP）可能并不是一个有效的解决方案。虽然动态规划在许多优化问题中都非常有效，但是它通常适用于具有“最优子结构”和“无后效性”这两个性质的问题。
“最优子结构”是指一个问题的最优解包含其子问题的最优解；“无后效性”是指一旦确定了某个阶段的状态，那么在这个阶段以后的过程将不再受到之前阶段的影响。
然而，在这个问题中，一个零件的处理顺序可能会影响其他零件的处理时间，因为此时的机器并不在同一时间起点上，因此这个问题并不具有“无后效性”。此外，一个局部最优的零件处理顺序并不一定能导致全局最优解，因此这个问题也不具有“最优子结构”，这里和贪心法的缺点一样。
因此，虽然动态规划是一种强大的算法设计技术，但它可能并不适用于这个问题。这个问题更适合使用贪心算法或其他启发式算法来求解。此外，从正确性上讲，由于这是一个P||Cmax问题，保证精确性则需要指数时间的时间复杂度，而我的代码在仅有多项式时间复杂度的前提下，能够保证至少有超过一半以上的最优顺序，而动态规划无法保证这一点。
时间复杂度分析：
虽然这类问题是NP-hard问题，但是对于我的算法代码，时间复杂度主要由以下几部分决定：
- 零件排序：
parts = sorted([(a[i] - b[i], i) for i in range(n)])，这部分的时间复杂度为O(n log n)，其中n是零件的数量。 - 零件分配：这部分的时间复杂度为O(n)，因为它只是遍历一次零件列表。
- 交换零件并计算新的完成时间：这部分在最坏的情况下需要进行n次深度复制和n次时间计算，所以时间复杂度为O(n^2)。
综上，这个代码的总体时间复杂度为O(n^2)。
给定n位正整数a，去掉其中任意k个数字后，剩下的数字按原次序排列组成⼀个新的正整数。对于给定的n和k，设计⼀个算法，找出剩下数字组成的新数最⼩值的删数⽅案。
思路分析
对于一个数字，高位数位的数值大小更对数字的大小起决定性作用，满足最优子结构，因此，可以采用贪心法，从高位开始贪心，挑选小数字数位保留。假设有可删数k个，选取前k+1个高位，找到最小数（有多个最小则优先选定靠左高位数），该最小数即保留数位，该位的左方数字删去，即：
若某轮有删除配额k：
1.选取最左k+1个数组成的子序列；
2.在子序列中选取最小数值；
3.消耗删除配额，将最小值左方数位从原序列删去（若有多最小值，选取靠左数位）（k->k’，剩余可删数位数减少）；
4.将选定的最小数值数位移出原序列，输出到答案序列中；
5.If 剩余序列长度 == k’（下一轮不足以选取k’+1个数）
6.else k’ == 0（无剩余删除配额）
7.剩余序列全部保留，输出到答案序列中。
def main():
n = input("输入被删减的数字n:") # 输入n
if n[0] == '-' or n == '0': # 判断n是否为负数或者为0
print("n 不是正数!") # 输出n不是正整数
return
k = int(input("输入删减位数 k:")) # 输入k
if len(n) <= k: # 判断n的长度是否小于等于k
print("删的太多了!") # 输出没有足够的数字
return
ans = []
while k > 0 and len(n) > k:
min_index = min(range(k+1), key=n.__getitem__)
ans.append(n[min_index])
n = n[min_index+1:]
k -= min_index
ans += list(n)
ans = ''.join(ans).lstrip('0')
print(ans)
if __name__ == "__main__":
main()算法结果： 设有12位数字a = 751938541011，删除配额k = 5 从左搜索高位前6个，子序列为751938，最小数值为1，选定1，删掉75，k=k-2=3，已有答案序列为1，从左搜索高位前4个，子序列为9385，最小数值为3，选定3，删掉9，k=k-1=2，已有答案序列为3 从左搜索高位前3个，子序列为854，最小数值为4，选定4，删掉85，k=k-2=0，已有答案序列为134 k == 0，剩余序列全部保留，得到最终解1341011。
时间复杂度分析：最好情况下，前k+1个数位数值单调递减，一轮搜索删除k个数得出结果，时间复杂度O(k+1)；最坏情况为单调不递减序列，每轮搜索均直接保留最高位，需搜索n-k轮，每轮搜索k位，时间复杂度O(k(n-k))。
回溯算法是一种试探性的解决问题方法，其基本思想是从问题的初始状态出发，通过尝试各种可能的步骤来寻找问题的解。如果在某一步骤后，发现原问题的解不可能在此基础上得到，那么就“回溯”到前一步，再试其他的可能性。
回溯算法通常遵循以下几个步骤：
- 选择：在当前状态下，对每一个可能的选项进行尝试。
- 扩展：根据选择的结果，进入下一个状态。
- 回溯：如果在某一步骤后，发现原问题的解不可能在此基础上得到，那么就回溯到前一步，再试其他的可能性。
回溯算法能解决的问题一般具有以下几个特征：
- 需要求解的问题可以分解为若干个子问题，子问题之间有一定的顺序关系，只有前一个子问题的解才能导出后一个子问题的解，即该问题具有最优子结构性质。
- 每个子问题的解集是一个有限集，可以通过遍历完全枚举出来。
- 问题的解或者子问题的解是否满足约束条件，可以在常数时间内判断。
如果一个问题满足以上特点，我们就可以使用回溯算法来解决。例如，数独问题、八皇后问题、全排列问题等都可以使用回溯算法来解决。
现在考虑实验题目
⽤回溯算法求解任意的9*9的数独问题。（数独问题描述：标准的数独游戏是在⼀个 9 X 9 的棋盘上填写 1 – 9 这 9 个数字，规则是这样的：棋盘分成下图所示的 9 个区域（不同区域由⿊⾊粗线标出，每个区域是 3 X 3 的⼦棋盘），在每个⼦棋盘中填充 1 – 9 且不允许重复 ，下⾯简称块重复每⼀⾏不许有重复值，每⼀列不许有重复值）
分析：解决这个数独问题我们可以尝试使用回溯算法思路如下：
- 初始化：首先，我们需要一个二维数组来表示数独的状态，以及三个二维数组来记录每一行、每一列和每一宫中已经出现的数字。
- 深度优先搜索：从数独的第一个位置开始，如果该位置的数字已经确定，就移动到下一个位置；如果该位置的数字还没有确定，就尝试所有可能的数字。
- 尝试填入数字：对于每一个可能的数字，首先检查该数字是否在当前位置的行、列和宫中都没有出现过，如果没有出现过，就将该数字填入数独中的当前位置，并在行、列和宫的记录数组中标记该数字。
- 递归：然后，递归地对数独的下一个位置进行深度优先搜索。如果在下一个位置找到了一个解，就返回该解；如果在下一个位置没有找到解，就取消填入的数字，并在行、列和宫的记录数组中取消标记该数字，然后尝试下一个可能的数字。
- 回溯：如果所有的数字都试过了，就回溯到上一层（即上一个位置），并尝试下一个可能的数字。
- 找到解：如果已经到达数独的最后一个位置，并且该位置的数字已经确定，就找到了一个解。
# 定义一个函数来打印数独的当前状态
def print_sudoku(sudoku):
for row in sudoku: # 遍历数独的每一行
print(" ".join(str(num) for num in row)) # 将每一行的数字转为字符串并用空格连接，然后打印
exit(0) # 打印完数独后结束程序
# 定义一个函数来记录数独中某个位置的数字
def record(x, y, rows, cols, boxes, sudoku):
num = sudoku[x][y] # 获取数独中位置 (x, y) 的数字
# 在行、列和宫的记录数组中标记该数字
rows[x][num] = cols[y][num] = boxes[(x//3)*3 + y//3][num] = 1
# 定义一个函数来取消记录数独中某个位置的数字
def derecord(x, y, rows, cols, boxes, sudoku):
num = sudoku[x][y] # 获取数独中位置 (x, y) 的数字
# 在行、列和宫的记录数组中取消标记该数字
rows[x][num] = cols[y][num] = boxes[(x//3)*3 + y//3][num] = 0
sudoku[x][y] = 0 # 将数独中位置 (x, y) 的数字清零
# 定义一个函数来使用深度优先搜索解决数独
def dfs(x=0, y=0, rows=None, cols=None, boxes=None, sudoku=None):
if sudoku[x][y] != 0: # 如果数独中位置 (x, y) 的数字已经确定
if x == 8 and y == 8: # 如果已经到达数独的最后一个位置
print_sudoku(sudoku) # 打印数独
elif y == 8: # 如果已经到达当前行的最后一个位置
dfs(x+1, 0, rows, cols, boxes, sudoku) # 移动到下一行的第一个位置
else: # 如果还没有到达当前行的最后一个位置
dfs(x, y+1, rows, cols, boxes, sudoku) # 移动到当前行的下一个位置
else: # 如果数独中位置 (x, y) 的数字还没有确定
for num in range(1, 10): # 遍历所有可能的数字
# 如果该数字在当前位置的行、列和宫中都没有出现过
if not rows[x][num] and not cols[y][num] and not boxes[(x//3)*3 + y//3][num]:
sudoku[x][y] = num # 将该数字填入数独中的当前位置
record(x, y, rows, cols, boxes, sudoku) # 记录该数字
if x == 8 and y == 8: # 如果已经到达数独的最后一个位置
print_sudoku(sudoku) # 打印数独
elif y == 8: # 如果已经到达当前行的最后一个位置
dfs(x+1, 0, rows, cols, boxes, sudoku) # 移动到下一行的第一个位置
else: # 如果还没有到达当前行的最后一个位置
dfs(x, y+1, rows, cols, boxes, sudoku) # 移动到当前行的下一个位置
derecord(x, y, rows, cols, boxes, sudoku) # 取消记录该数字
return # 如果所有的数字都试过了，返回上一层
# 初始化数独、行、列和宫的记录数组
sudoku = [[0] * 9 for _ in range(9)] # 创建一个 9x9 的二维数组来存储数独的状态，初始状态为全 0
rows = [[0] * 10 for _ in range(10)] # 创建一个 10x10 的二维数组来记录每一行的数字，初始状态为全 0
cols = [[0] * 10 for _ in range(10)] # 创建一个 10x10 的二维数组来记录每一列的数字，初始状态为全 0
boxes = [[0] * 10 for _ in range(10)] # 创建一个 10x10 的二维数组来记录每一宫的数字，初始状态为全 0
# 从 txt 文件中读取数独初始状态，并记录已有数字
with open('sudoku.txt', 'r') as f:
for i, line in enumerate(f): # 遍历文件的每一行
row = list(map(int, line.split())) # 将每一行的数字分割并转换为整数
for j, num in enumerate(row): # 遍历每一行的每一个数字
sudoku[i][j] = num # 设置当前位置的数字
if num != 0: # 如果当前位置的数字不为 0
record(i, j, rows, cols, boxes, sudoku) # 记录当前位置的数字
# 调用深度优先搜索解决数独
dfs(rows=rows, cols=cols, boxes=boxes, sudoku=sudoku) # 使用深度优先搜索算法解决数独
print("该数独无解") # 如果数独无解，打印提示信息下面是sudoku.txt保存的基本测试数独
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
可以看到生成了正确的数独结果。
时间复杂度分析：在最坏的情况下，即数独的初始状态为空（所有的格子都是 0），DFS 需要尝试所有可能的数字填充方式，因此时间复杂度为 O(9^N)，其中 N 是数独的空格数，最多为 81。
空间复杂度分析：注意到回溯算法涉及到递归调用，以及数独存储形式涉及矩阵，因此考虑分析空间复杂度，在这里空间复杂度主要取决于数独的大小和深度优先搜索的递归深度。
- 数独的大小：这段代码中，数独是一个 9x9 的二维数组，所以它的空间复杂度是 O(1)。此外，还有三个 10x10 的二维数组（
rows、cols和boxes）用于记录每一行、每一列和每一宫的数字，所以它们的空间复杂度也是 O(1)。 - 深度优先搜索的递归深度：在最坏的情况下，即数独的初始状态为空（所有的格子都是 0），深度优先搜索需要递归地尝试所有可能的数字填充方式，所以它的空间复杂度是 O(N)，其中 N 是数独的空格数，最多为 81。
因此，这段代码的总空间复杂度是 O(1) + O(N) = O(N)。但是，因为数独的大小是固定的，所以我们通常可以认为这段代码的空间复杂度是常数，即 O(1)。
代码开源在GitHub仓库：