推荐阅读：





百度百科：[https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-\[9\]-841810-wrap](https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-%5B9%5D-841810-wrap)

java实现：[https://blog.csdn.net/Cobbyer/article/details/108127742](https://blog.csdn.net/Cobbyer/article/details/108127742)

计算机常用算法与程序设计案例教程： [https://max.book118.com/html/2019/0122/6053000055002003.shtm](https://max.book118.com/html/2019/0122/6053000055002003.shtm)

知乎：[https://zhuanlan.zhihu.com/p/93857890](https://zhuanlan.zhihu.com/p/93857890)

## 1 0-1背包

![在这里插入图片描述](/static/img/images/00972.png)

对于输入

4件物品  背包能承受的最大重量为10

单体重量2  单体价值1

单体重量3  单体价值3

...
```python
4 10
1 1
3 3
4 5
7 9
```

动态规划：
```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(1, V + 1):  # 表示当前背包的容量为j
        if j < w[i]:  # 如果当前背包容量j放不下重量为w[i]的物体
            dp[i][j] = dp[i - 1][j]  # 不拿 i 物品，此时背包价值依旧等于成功拿了上一个物体时的价值
        else:
            # 背包装得下，但是考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输出dp：

```python
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 3, 4, 4, 4, 4, 4, 4, 4]
[0, 1, 1, 3, 5, 6, 6, 8, 9, 9, 9]
[0, 1, 1, 3, 5, 6, 6, 9, 10, 10, 12]
```

dp表中每一个dp[i]的值只与dp[i-1]有关系，即后无效性原则。

 `dp[i][j]`表示前`i`件物品恰放入一个容量为`j`的背包可以获得的最大价值。

 `dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])` 表示 考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法。

 整个dp只有最终的`dp[N][V]` 有意义，其他数据都是为了求出`dp[N][V]` 而做的变化。

改进代码：

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
dp = [0 for i in range(V + 1) ]
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V, 0, -1):  # 从后往前推
        if j >= w[i]:  # 如果当前背包容量j 可以放下 重量为w[i]的物体
            dp[j] = max(dp[j], dp[j - w[i]] + c[i])
    print(dp)
```

## 2 完全背包

问题描述：给定 N 种物品每种物品**都有无限件可用**，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for v in range(1, V + 1):  # 表示当前背包的容量为j
        dp[i][v]=0
        # 最多可以放nCount个物品i
        nCount = v // w[i]
        # 和01背包的区别就在这里，01
        # 背包只有两种状态：放与不放
        # 而完全背包可以放0到k个物品i，同样是取最大值
        for k in range(nCount+1):
            dp[i][v] = max(dp[i][v], dp[i - 1][v - k * w[i]] + k * c[i]) 
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入：

```python
4 5
1 2
2 4
3 4
4 5
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```

## 3 多重背包

问题描述：给定 N 种物品每种物品 i 都有 s[i] 件可用，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
s = [0]  # 第一个元素无用  有多少件
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
    s.append(temp[2])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V,-1,-1 ):  # 表示当前背包的容量为j
        for k in range(0, s[i] + 1):
            if j>=k * w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入

```python
4 5
1 2 3
2 4 1
3 4 3
4 5 2
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 6, 6]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```

背包问题 python 【动态规划】

环形链表  [https://leetcode-cn.com/problems/linked-list-cycle/](https://leetcode-cn.com/problems/linked-list-cycle/)





[https://www.cxyxiaowu.com/647.html](https://www.cxyxiaowu.com/647.html)

设置两个指针，一个每次走一步的慢指针和一个每次走两步的快指针。

如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环

如果含有环，快指针会超慢指针一圈，和慢指针相遇，说明链表含有环。

![在这里插入图片描述](/static/img/images/01012.gif)

python
```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False  #空链表 或者 链表元素个数小于等于2
        #快慢指针
        slow = head
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:  #快指针遇到null
                return False
            slow = slow.next
            fast = fast.next.next
        return True
a=ListNode(1)
b=ListNode(2)
c=ListNode(3)
d=ListNode(4)
a.next=b
b.next=c
c.next=d
d.next=b
print(Solution().hasCycle(a))
```

![在这里插入图片描述](/static/img/images/01013.png)

![在这里插入图片描述](/static/img/images/01014.png)

```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None  # 空链表 或者 链表元素个数小于等于2
        # 快慢指针
        slow = head
        fast = head
        while (fast is not None):
            slow = slow.next
            if (fast.next is None):
                return None
            fast = fast.next.next
            if fast is slow:
                ptr = head
                while (ptr is not slow):
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
a.next = b
b.next = c
c.next = d
d.next = b
print(Solution().detectCycle(a).val)
```

141. 环形链表 142. 环形链表 II 使用快慢指针求解「环形链表」

[https://leetcode-cn.com/problems/trapping-rain-water/](https://leetcode-cn.com/problems/trapping-rain-water/)





![在这里插入图片描述](/static/img/images/01113.png)

动态编程

```python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left_max = [0] * size
        right_max = [0] * size
        # 从左到右看最高
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        # 从右到左看最高
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        # 累加
        for i in range(1, size):
            ans += min(left_max[i], right_max[i]) - height[i]  # 本身有的一定高度需要减去
        return ans
print(Solution().trap([4, 2, 0, 3, 2, 5]))
```

双指针

```python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left = 0
        right = size - 1
        left_max = 0
        right_max = 0
        while (left < right):
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    ans += (left_max - height[left])
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    ans += (right_max - height[right])
                right -= 1
        return ans
print(Solution().trap([4, 2, 0, 3, 2, 5]))
```

42. 接雨水 动态编程 双指针

![在这里插入图片描述](/static/img/images/01121.png)





```python
from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return len(dp)
print(Solution().lengthOfLIS([3, 2, 1, 1, 2]))
```

![在这里插入图片描述](/static/img/images/01122.png)

```python
from typing import List
from bisect import bisect_left
class Solution:
    def maxEnvelopes(self, arr: List[List[int]]) -> int:
        # sort increasing in first dimension and decreasing on second
        arr.sort(key=lambda x: (x[0], -x[1]))
        def lis(nums):
            dp = []
            for i in range(len(nums)):
                idx = bisect_left(dp, nums[i])
                if idx == len(dp):
                    dp.append(nums[i])
                else:
                    dp[idx] = nums[i]
            return len(dp)
        # extract the second dimension and run the LIS
        return lis([i[1] for i in arr])
print(Solution().maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]))
```

300. 最长上升子序列（动态规划） 354. 俄罗斯套娃信封问题

![在这里插入图片描述](/static/img/images/01125.png)





```python
from typing import List
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break
        dfs(0, 0)
        return ans
print(Solution().restoreIpAddresses("010010"))
```

93. 复原IP地址 （递归+回溯 ）

![在这里插入图片描述](/static/img/images/01126.png)






```python
from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(index: int):
            if index == len(digits):
                combinations.append("".join(combination))
                return
            digit = digits[index]
            for letter in phoneMap[digit]:
                combination.append(letter)
                backtrack(index + 1)
                combination.pop()
        combination = list()
        combinations = list()
        backtrack(0)
        return combinations
print(Solution().letterCombinations("234"))
```

17. 电话号码的字母组合（递归+回溯 ）

![在这里插入图片描述](/static/img/images/01127.png)





```python
from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()
        backtrack([], 0, 0)
        return ans
print(Solution().generateParenthesis(3))
```

22. 括号生成（递归+回溯 ）

[https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/](https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/)





![在这里插入图片描述](/static/img/images/01128.png)

```python
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(start):
            if start == n:
                sol.append(nums[:])
            for i in range(start, n):
                nums[start], nums[i] =  nums[i], nums[start]
                dfs( start+1 )
                nums[start], nums[i] =  nums[i], nums[start]
        sol = []
        n = len(nums)
        dfs(0)
        return sol
a = Solution()
print(a.permute([1, 2, 3]))
```

或者写成：
```
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(sol):
            if len(sol) == n:
                res.append(nums[:])
            for i in range(0, n):
                if used[i]: continue
                sol.append(nums[i])
                used[i] = 1
                dfs(sol)
                sol.pop()
                used[i] = 0
        res = []
        n = len(nums)
        used = [0 for _ in range(n)]
        dfs([])
        return res
print(Solution().permute([1, 2, 3]))
```



[https://leetcode-cn.com/problems/permutations-ii/solution/](https://leetcode-cn.com/problems/permutations-ii/solution/)

![在这里插入图片描述](/static/img/images/01129.png)

```python
from typing import List
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(sol):
            if len(sol) == n:
                res.append(sol[:])
                return
            for i in range(0, n):  # nums 不改变
                # print(i, used)
                if used[i]: continue  # 当前位置的元素被使用过
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue  # 剪枝：新位置元素和上一个相同，并且上一个元素是没用过
                sol.append(nums[i])
                used[i] = 1
                dfs(sol)
                sol.pop()
                used[i] = 0
        res = []
        n = len(nums)
        nums.sort()
        used = [0 for i in range(n)]  # 全局，看看是第几层递归
        dfs([])
        # res=[tuple(i) for i in res]
        # return list(set(res))
        return res
print(Solution().permuteUnique([1, 1, 1]))
```

【算法题目】【DFS】全排列1,2

[https://leetcode-cn.com/problems/n-queens/solution/liang-chong-shi-xian-xiang-xi-tu-jie-51-n-huang-ho/](https://leetcode-cn.com/problems/n-queens/solution/liang-chong-shi-xian-xiang-xi-tu-jie-51-n-huang-ho/)






伪代码

```python
dfs函数(x) { 
    if x==n { //如果x等于n了，说明每行的皇后都放置完毕
        //将棋盘内容的快照保存下来
        return
    }
    for(y=0;i<n;++y) {
        if [x,y]这个位置是有效的，即横、竖、两个斜线都有没有被攻击 {
            将棋盘[x,y]位置设置为 Q
            dfs(x+1) 继续尝试下一行
            将棋盘[x,y]位置还原
        }
    }
}
```

python3
```python
class Solution(object):
    def solveNQueens(self, n):
        # 生成N*N的棋盘，填充棋盘，每个格子默认是''.''表示没有放置皇后
        arr = [["." for _ in range(n)] for _ in range(n)]  # 生成列表最好方式是采用列表推导式
        res = []  # 存放最终结果
        # 检查当前的行和列是否可以放置皇后
        def check(x: int, y: int):
            # 检查竖着的一列是否有皇后
            for i in range(x):
                if arr[i][y] == "Q":
                    return False
            # 检查左上的斜边是否有皇后
            i, j = x - 1, y - 1
            while i >= 0 and j >= 0:
                if arr[i][j] == "Q":
                    return False
                i, j = i - 1, j - 1
            # 检查左下的斜边是否有皇后
            i, j = x - 1, y + 1
            while i >= 0 and j < n:
                if arr[i][j] == "Q":
                    return False
                i, j = i - 1, j + 1
            # 检查右上的斜边是否有皇后
            i, j = x + 1, y - 1
            while i < n and j >= 0:
                if arr[i][j] == "Q":
                    return False
                i, j = i + 1, j - 1
            # 检查右下的斜边是否有皇后
            i, j = x + 1, y + 1
            while i < n and j < n:
                if arr[i][j] == "Q":
                    return False
                i, j = i + 1, j + 1
            return True
        def dfs(x):
            # x是从0开始计算的
            # 当x==n时所有行的皇后都放置完毕，此时记录结果
            if x == n:
                res.append(["".join(arr[i]) for i in range(n)])
                return
            # 遍历每一列
            for y in range(n):
                # 检查[x,y]这一坐标是否可以放置皇后
                # 如果满足条件，就放置皇后，并继续检查下一行
                if check(x, y):
                    arr[x][y] = "Q"  # 放上皇后
                    dfs(x + 1)  # 搜索下一行策略
                    arr[x][y] = "."  # 撤销皇后，y进入下一列搜索
        dfs(0)
        return res
print(len(Solution().solveNQueens(8)))
```

利用一个规律改进算法。之前check()是循环，效率不高。

python3
```python
class Solution(object):
    def solveNQueens(self, n):
        # 生成N*N的棋盘，填充棋盘，每个格子默认是''.''表示没有放置皇后
        arr = [["." for _ in range(n)] for _ in range(n)]  # 生成列表最好方式是采用列表推导式
        res = []  # 存放最终结果
        columns = set()
        hypotenuse1 = set()
        hypotenuse2 = set()
        # 检查当前的行和列是否可以放置皇后
        def check(x: int, y: int):
            if y in columns:
                return False
            if x - y in hypotenuse1:
                return False
            if x + y in hypotenuse2:
                return False
            return True
        def dfs(x):
            # x是从0开始计算的
            # 当x==n时所有行的皇后都放置完毕，此时记录结果
            if x == n:
                res.append(["".join(arr[i]) for i in range(n)])
                return
            # 遍历每一列
            for y in range(n):
                # 检查[x,y]这一坐标是否可以放置皇后
                # 如果满足条件，就放置皇后，并继续检查下一行
                if check(x, y):
                    columns.add(y)
                    hypotenuse1.add(x - y)
                    hypotenuse2.add(x + y)
                    arr[x][y] = "Q"  # 放上皇后
                    dfs(x + 1)  # 搜索下一行策略
                    arr[x][y] = "."  # 撤销皇后，y进入下一列搜索
                    columns.remove(y)
                    hypotenuse1.remove(x - y)
                    hypotenuse2.remove(x + y)
        dfs(0)
        return res
print(Solution().solveNQueens(8))
```

![在这里插入图片描述](/static/img/images/01130.png)

![在这里插入图片描述](/static/img/images/01131.png)

N皇后（递归+回溯）

# 36. 有效的数独 





![在这里插入图片描述](/static/img/images/01132.png)

python
```python
from typing import List
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)] # 字典 哈希表 列表第一个字典：rows[0]这个字典是第一行的键值信息
        columns = [{} for i in range(9)] # 字典 哈希表
        boxes = [{} for i in range(9)] # 字典 哈希表
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]  # 第i行  第j列  的元素
                if num != '.':
                    num = int(num)
                    box_index = (i // 3) * 3 + j // 3    # 在一个3*3方格里的index
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1  # 第i行的rows字典里找这个元素，找不到就是0，加1后变成1. 找得到加上1后就会大于1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True
print(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"]  ]))
```

运行完毕后：

![在这里插入图片描述](/static/img/images/01133.png)

![在这里插入图片描述](/static/img/images/01134.png)

![在这里插入图片描述](/static/img/images/01135.png)

按健寻值的字典：

```python
rows = [{} for i in range(9)]
print(rows)
rows[0][1]=1
rows[0][3]=1
rows[1][1]=1
print(rows)
```

结果
```python
C:\Users\xd_du\Anaconda3\envs\py37\python.exe C:/Users/xd_du/PycharmProjects/wave/gendata.py
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
[{1: 1, 3: 1}, {1: 1}, {}, {}, {}, {}, {}, {}, {}]
Process finished with exit code 0
```

# 37. 解数独

https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/

![在这里插入图片描述](/static/img/images/01136.png)

```python
from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(pos: int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit + 1)
                    dfs(pos + 1)   #递归
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
                if valid:
                    return
        line = [[False] * 9 for _ in range(9)]
        column = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
        valid = False
        spaces = list()
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
        dfs(0)
board = [
    ["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"]]
Solution().solveSudoku(board)
for i in range(9):
    print(board[i])
```

```python
def check(matrix, row, col, value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    # 检测每行
    for j in range(9):
        if matrix[row][j] == value:
            return False
    # 检测每列
    for i in range(9):
        if matrix[i][col] == value:
            return False
    # 检测元素所在3*3区域
    area_row = (row // 3) * 3
    area_col = (col // 3) * 3
    for i in range(area_row, area_row + 3):
        for j in range(area_col, area_col + 3):
            if matrix[i][j] == value:
                return False
    return True
def solveSudoku(matrix, count=0):
    """
    遍历每一个未填元素，遍历1-9替换为合适的数字
    """
    if (count == 81):  # 递归出口
        return True
    #行优先遍历
    row = count // 9  # 行标
    col = count % 9  # 列标
    if matrix[row][col] != 0:  # 已填充
        return solveSudoku(matrix, count=count + 1)
    else:  # 未填充
        for i in range(1, 10):
            if check(matrix, row, col, i):  # 找到可能的填充数
                matrix[row][col] = i
                if solveSudoku(matrix, count=count + 1):  # 是否可完成
                    return True  # 可完成
                # 不可完成
                matrix[row][col] = 0  # 回溯
        return False  # 不可完成
while True:
    try:
        matrix = []
        for i in range(9):
            matrix.append([int(i) for i in  input().split(' ')])#多维列表输入
        solveSudoku(matrix)
        for i in range(9):
            print( ' '.join(map(str, matrix[i])))
    except:
        break
```



# 生成一张标准数独地图

标准数独地图有17个数字提示，且是有唯一解的。