leetcode他山之石

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

解题思路：

类似8皇后问题。

深度遍历的过程，从开始一直扫描，直到遇到空字符，便可开始填数字，该位置的数字从1~9依次遍历，不行的时候就回退。下面根据代码的具体情况进行讲解：

代码过程如下：

1. checkValid方法中position是位置，位置从0开始，直到81时结束，根据position可以确定此时的行和列。该方法的含义是判断在给position位置填写了数之后，行列以及块是否合法，即是否会出现相同的数字出现

2. solve方法是核心：从开始的位置一直扫描，直到遇到非数字，然后开始递归，.的位置有可能是任何数字，然后从1-9开始试，将该位置的值设为1-9中的其中一个之后，调用checkValid方法判断该位置为填充上值之后是否合法，如果合法，继续下一个位置的判断，即开始递归。当该递归返回时，如果是false,则表示刚才的位置数字填错了，需要重新填，则先恢复，在继续试探。直到返回true为止，否则返回false