不是最优的解法，却是最好理解的解法

1. 问题的提出

题目：LeetCode Q37 解数独.

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

思路：对此类NP问题，若无明确的数学解法，可依靠计算机进行暴力枚举尝试。同时，在暴力法内部对显然不可能构成正确答案的分支下进行剪枝。
回溯法大致的类别有：排列，组合，枚举。
其中排列和组合可以看出枚举的特殊情况。本题可以整体上采用枚举+剪枝的策略。

2. 思路

回溯法可以看成是对一个多叉树的深度优先搜索，其伪代码如下：

// 回溯法: 伪代码
backTrack(...) {
	if (当前解满足终止条件) 退出;
	if (当前解满足要求) 获取可行解;

	for (单个选择 : 所有可用选择) {
			当前解进一步;
			backTrack(...);
			当前解回退一步;
	}
}

3. 代码

针对数独问题，代码中主要有以下几个API：

import java.util.Arrays;import java.util.LinkedList;import java.util.List;/**
 * 整体也是一个枚举+剪枝的过程
 * 个人认为回溯有三类: 排列+剪枝(使用useMaker标记尝试过的)  组合+剪枝(用startFromWhere标记从哪开始搜索)  枚举+剪枝
 * 
 */publicclassQ37{/**
     * 注意返回值是void,这个有点费事
     * @param board 待解数独
     */publicvoidsolveSudoku(char[][] board){// 存放所有可能的解
        List<char[][]> result=newLinkedList<>();// 调用核心回溯方法,从第1个格子开始填backTrack(result, board,0);// 为了配合返回void必须在不修改board引用的情况下改变内部的值// 注意题目已经确保解唯一,若不唯一可从result获取全部for(int i=0; i< board.length; i++){
            board[i]= result.get(0)[i];}}/**
     * 深拷贝二维数组
     * @param origin 原始二维数组
     * @return 深拷贝后的二维数组
     */publicchar[][]deepCopy(char[][] origin){char[][] res=newchar[origin.length][];for(int i=0; i< origin.length; i++) res[i]= origin[i].clone();return res;}/**
     * 回溯核心方法
     * @param result 全局解
     * @param board 当前解
     * @param tryPosition 待尝试的位置
     */privatevoidbackTrack(List<char[][]> result,char[][] board,int tryPosition){// 如果不符合,直接剪枝if(!isValidSudoku(board))return;// 上面已经判断过一次是否满足了,下面的肯定都合法,省略一次判断,返回elseif(tryPosition==81){
            result.add(deepCopy(board));return;}// 向后探索,绝对不能写成下面注释的样子,会造成重复解int row= tryPosition/9;int col= tryPosition%9;if(board[row][col]=='.'){for(int k=0; k<9; k++){
                board[row][col]=(char)(k+49);// '1'的ASCII码是49backTrack(result, board, tryPosition+1);
                board[row][col]='.';}}// 注意这个地方,如果tryPosition的位置有数字了,直接按游戏展开树纵向深入,比上面的IF分支去掉了尝试和回溯的部分// 可以理解为有障碍的排列else{backTrack(result, board, tryPosition+1);}// for (int i = 0; i < board.length; i++) {//     for (int j = 0; j < board[0].length; j++) {//         // 如果这个位置没填,尝试//         if (board[i][j] == '.') {//             for (int k = 0; k < 9; k++) {//                 board[i][j] = (char) (k + 49);//                 backTrack(result, board, vaccineCell-1);//                 // if (i != 8 || j != 8 || k != 8) board[i][j] = '.';//                 board[i][j] = '.';//             }//         }//     }// }}privatebooleanisValidSudoku(char[][] board){int[][] rows=newint[9][9];int[][] col=newint[9][9];int[][] diag=newint[9][9];for(int i=0; i< board.length; i++){for(int j=0; j< board[0].length; j++){if(board[i][j]!='.'){int num= board[i][j]-'1';int index_box=(i/3)*3+ j/3;// 这个判重逻辑是:第i个行/列/小数组的数字应该填在rows/col/diag的第i行的对应数字这个位置// 如果这个位置之前填过了(用1标识)说明重复了,直接返回false// 如果这个位置之前没填过(按这个代码数组是用0初始化的)把这个位置填1if(rows[i][num]==1)returnfalse;else rows[i][num]=1;if(col[j][num]==1)returnfalse;else col[j][num]=1;if(diag[index_box][num]==1)returnfalse;else diag[index_box][num]=1;}}}returntrue;}publicstaticvoidmain(String[] args){char[][] board={{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};// char[][] board = {{'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'}};

        Q37 q37=newQ37();
        q37.solveSudoku(board);for(char[] chars: board){
            System.out.println(Arrays.toString(chars));}}}