编程之美之构造数独

---

数独（すうどく，Sūdoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

问题：

构造一个9*9的方格矩阵，玩家要在每个方格中，分别填上1至9的任意一个数字，让整个棋盘每一列、每一行以及每一个3*3的小矩阵中的数字都不重复。

解法一

首先用二维数组的结构来存储数独游戏sudoku[][9]，通过经典的深度优先搜索来生成一个可行解。

深度优化搜索算法

从[0][0]开始对于没有处理过的格子获得一个可取的值，在搜索过程中如果没有发现可行的值则回溯，修改前一个格子的取值。直到所有的格子都取到可行的值为止，这时候我们就找到了一个可行的解。

算法流程图：

算法复杂度：O(n^2)

解法二

置换法，就是用矩阵行交换和列交换，这个方法的优点就是速度很快，缺点就是只能构造9!种，离所有合法数独总数差的很远。

算法实现过程：

1.假设已经有一个3 *3的矩阵是排列好的，具体的数字暂时用字母代替，如下图所示：

2.把整个数独矩阵的各个小矩阵（也就是宫）分别命名为B1，B2，...，B9：

3.将已有的3*3矩阵放在B5的位置，得到如下图所示矩阵：

4.通过置换行的方法，把B4和B6矩阵填好。

5.对中央小矩阵的每一列做同样的变换，得到B2和B8.