37.leetcode题目讲解(Python): 解数独

题目如下:
题目
Note

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

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

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

算法参考流程图如下:
数独算法流程参考

参考代码如下:

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


如果您有好的建议,欢迎来信与我交流
邮箱
也欢迎关注微信公众号“苔原带”
邮箱