该题目为：给定如下所示的数独，编写出算法填充数独空白部分，假设该数独只有唯一解。
数独.png
最近做到该数独题，个人认为有必要记录一下。
要面对的问题
当首次看到这道题时，很多人的第一反应应该就是头皮发麻吧。
要往空白处填充数据，那这种情况实在是太多了，只要数独没填充完，只要填充的过程中符合数独逻辑，均可往里填充。既然如此，我们该如何入手？
数独的规则
- 数独的每行数字必须均唯一
- 数独的每列数字必须均唯一
- 当前坐标所在子宫格的数必须均唯一
分析问题
既然是在数独填充的过程中，当前空白所在的行，列，子宫格的数都必须唯一，我们要做的就是：
当前空白可填充数字应该包含哪些？
可以从0到9的全量集合减去当前行，列，子宫格包含的数得出。将结果存放在临时的备选集合当中。如何填充数独？
循环遍历当前备选集合，填充到当前空白当中，然后通过深搜处理下一个空白。如果在填充过程中，要填充的某个空白无解了，下一步该如何处理？
这其实就要用到深搜的回溯功能了。如果在深搜填充过程中出现了无解，则回溯，再选择下一个备选值，直到后边的空白都为有解即可。
我的解题如下：
public class JavaTest {
public static void main(String[] args) {
Integer[][] array = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
sudoku(array);
System.out.println("\n最终结果：");
forEachsudoku(array);
}
private static boolean sudoku(Integer[][] array) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// array[i][j]均>0则标志该数独有解
if (array[i][j] == 0) {
ArrayList<Integer> list = getFullList();
// 排除行上已存在的值
for (int k = 0; k < 9; k++) {
if (array[i][k] != 0) {
list.remove(array[i][k]);
}
}
// 排除当前列上已存在的值
for (int k = 0; k < 9; k++) {
if (array[k][j] != 0) {
list.remove(array[k][j]);
}
}
// 排除当前子九宫格上已存在的值
int row = i / 3;
int column = j / 3;
for (int k1 = 3 * row; k1 < 3 * row + 3; k1++) {
for (int k2 = 3 * column; k2 < 3 * column + 3; k2++) {
if (array[k1][k2] != 0) {
list.remove(array[k1][k2]);
}
}
}
// 排除完毕后，无可用备选值了，则表明无解
if (list.isEmpty()) {
System.out.println(String.format("[%d,%d]无可备选值，无解情况为：", i, j));
forEachsudoku(array);
return false;
}
for (int k = 0; k < list.size(); k++) {
array[i][j] = list.get(k);
System.out.println(String.format("[%d,%d]已用备选数为%d，共有备选数：%s", i, j, array[i][j], list.toString()));
// 深搜当前选用的备选值是否可用
if (sudoku(array)) {
return true;
}
}
// 当前深搜无解回溯，改回当前值
array[i][j] = 0;
return false;
}
}
}
return true;
}
// 数独遍历
private static void forEachsudoku(Integer[][] arr) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
// 返回默认0到9全量值的集合
private static ArrayList<Integer> getFullList() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= 9; i++) {
list.add(i);
}
return list;
}
}
