简要说明： (1)题目来源网络（题目要求和输入样例参考LeetCode相同题目） 链接：https://leetcode-cn.com/problems/sudoku-solver/ (2)由于作者水平限制和时间限制，代码本身可能仍有一些瑕疵，仍有改进的空间。也欢迎大家一起来讨论。 ——一个大二刚接触《数据结构》课程的菜鸡留

编写一个程序，给定部分格子及数字，通过填充空格来完成数独。对于数独有如下要求：

1、数字1-9在每一行只出现一次。 2、数字1-9在每一列只出现一次。 3、数字1-9在所属九宫格（粗实线分隔的3×3宫格）只出现一次。

输入样例要求：

1、需要输入9行字符串，每一行字符串长度为9，依次代表当行的9格。 2、用字符“.”代替空白格。 3、这样表示的数独永远是9×9的。 4、可以假设数独只有唯一解。

参考输入样例：

参考输出样例：

5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9

注：仅代表个人思路。

(1) 首先要确定数独的储存形式。由于是9×9的格子，因此可以联想到二维数组(矩阵)的储存形式。 (2) 由于数独的解决过程实则是一个不断试探的过程，因此类似于笔者在《数据结构》课程中所涉及的“迷宫问题”(可参见补充部分)的解法，思路应是回溯法。 (3) 那么在回溯的过程中需要区分，当前格子是原先输入时的空白格(对应字符“.”)还是已有的“固定格”。如果是后者，在回溯的过程中不能改变。如果是前者，才是我们一一试探的对象。因此在储存数独每个格子时，需要增加一个标记，来区分这两者。 (4) 在每一次试探时需要记忆上一步执行到的数字，然后紧接着进行试探。可以直接通过查找获取，我的思路里是放在了一个栈内，栈的数据结构实在是再适合回溯法不过了。（尽管这样浪费了一定空间，但也简化了一些代码） (5) 设想试探时的步骤。需要根据记忆确定本次需要试探的值，并且根据数独的规则检查这个值是否合法。如果不合法继续进1，如果合法可以继续试探下一格。当一格试探过了9之后，表明需要继续回溯试探前一格的下一个可能的值，以此类推。 (6) 那么就要确定这个检查机制应该在何时实现。如何实现是一个不复杂的问题。我的方法是在指向目标格子、进行任何处理前先来检查各个位置是否可行，然后再来根据反馈的结果确认下一个试探的值应是多少。也可以在尝试试探每一个值时都尝试一次这个值是否合法，但在有连续多个不合法的值试探时，后者可能会花费更多的时间。 (7) 确认试探的顺序，使用朴素的行优先原则。 (8) 结合之前的思路，我的想法是在储存格子时定义一个新的结构(struct)，既存放具体的值(在内存足够的前提下，定义为int型)，又存放是否为给定格子的标记(bool型)。同时由于每一个格子的行、列、九宫格的已有值决定了部分的数据是不合法的，而且这也是一个格子的属性，因此在不顾虑内存的前提下同时储存一个bool数组，长度为9，依次对应1~9是否允许被放在本格。