37.leetcode题目讲解（Python）： 解数独

题目如下：

当我们拿着数独游戏时，我们是通过观感直觉来求解的。详细说来：
1. 我们会去找那些规则下能够确定唯一解的空格，然后填入唯一解后再去寻找其他可以确定唯一解的空格。
2. 如果找不到有唯一解，我们就找解空间比较小的空格，从解空间中挑一个填上去试试，如果可行继续尝试步骤1，2。如果不可行（有一些空格没有解），我们就把尝试的解从解空间中去掉，再挑其他解进行尝试。

我采用的解题思路如下，为了方便理解，代码有点长，但用断点跟一遍很容易懂，代码 beat 80%：

1. 通过数独规则确定每行/ 每列/ 每3*3 box 的候选解空间，如果解空间都为空，代表数独解出，返回答案。反之，步骤2。
2. 对于每个空格基于（1）中对应解空间的交集确定解空间，如果有空格解空间为空，返回错误。
3. 找出那些有唯一解的空格，如果有填入，再重复步骤（递归）
4. 如果没有唯一解的空格，挑选解空间最小的空格，挑选空间中的一个解填入，然后重复步骤（递归），如果返回错误，就将该解从解空间中删除，如果删除后解空间为空，返回错误。反之，再挑一个解填入，重复步骤（递归）。

算法参考流程图如下：

参考代码如下：

注意：
1. 深拷贝和浅拷贝的问题。
2. 要求直接对 board进行修改，不可以返回值。

如果您有好的建议，欢迎来信与我交流

也欢迎关注微信公众号“苔原带”