数独生成与求解

记得第一次写数独的算法的时候是在大学期间，那时候闲来无事；在手机上玩着数独游戏，看着自己解不出来的题，想着是不是折腾折腾数独，写出一个求解数独的算法出来。

想到就做，不过最终以失败告终，做到了何种程度已记不清了。

后来，用 c 实现了求解数独的算法；而最近，则是用 Python 重新实现了求解数独的算法并实现了数独生成的算法。

在这里，也是想着介绍我使用 Python 实现的数独求解和数独生成的算法。

数独求解 - sudoku_solving.py

首先说说此算法使用到的数独的机制：

1. 【机制 1】单元格的候选数只有一个时，此单元格的值即为其候选数的值
2. 【机制 2】单元格的其中一个候选数在此单元格所在行/列/3*3小矩阵中唯一时，则此候选数即可确定为此单元格的值

求解步骤：

1. 分别以行/列/3*3小矩阵遍历数独中的所有单元格，根据单元格所在行/列/3*3小矩阵中其余单元格的值来更新此单元格的候选值
2. 在每个单元格的候选数更新后，均进行检测是否满足【机制 1】
3. 在 3 次遍历数独后，进行检测是否满足【机制 2】
4. 重复步骤 1~3，直至求出解或无法进行下一步
5. 若在第 4 步无法继续进行下去之后，则进行递归尝试可选值，最后得出解（并得出是否多解）

数独生成 - sudoku_generate.py

生成步骤：

1. 生成数独终盘
   1. 遍历整个数独，随机（从其候选值中进行随机）获取每个单元格的值
   2. 若能走到最后，则表示生成数独终盘成功，否则重新进行步骤 1，直至成功
2. 在终盘中进行挖洞，生成具有唯一解的数独难题
   1. 一次性挖取1个洞，然后立即进行求解，拟验证是否为唯一解
   2. 验证为唯一解后继续挖洞，否则重新挖洞
   3. 若在某一次挖洞中，将所有的可挖值都试过一遍后仍无法获取唯一解，则挖洞结束