题目：Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
下面是一个数独的题目：
其解：
数独不是很了解，没做过。不过知道规则。就是在这个9x9的格纸中间添1到9的数字。使每一行不能重复，每一列也不能重复，然后上面那个粗线框起来的3x3的格纸中的数字也不能重复。
不知道这样的游戏有啥意义。。。
Anyway，这个和那个什么皇后的题很类似，一般用回溯。不过递归显得比较清晰。
添格子么。。。那不是一个一个添。顺序呢？我肯定是从左到右从上到下这么添。那代码我也这样写。对于每个格子，假设前面的所有格子已经添好了，并且构成了一个合理的棋盘。对当前的格子，如果没有填充，在查看该格子所在的行，列还有所在的3x3子格子后，我尝试每个剩余的可用数字，对每个数字，填充当前格子，然后问题就递归地变成了下面一个格子的填充问题。
如下图所示，我们要填充第三个格子。
我们首先查看Cell(0,2)所在的列2，标记出现的数字，也就是8；然后再查看其所在的行0，标记出现的数字5，3和7，最后查看它所在的3x3的格子，有5，3，6，9，和8。这样，3，5，6，7，8，9都被标记了，剩下的就是0，2，4三种可能。
我们不妨选一种，比如4，然后继续递归Cell(0,3)。如果这种选择不合理，在最后没有生成合理的结果，那在递归返回到Cell(0,2)的时候，我们在选择下一个可能的值就是了，例如2.但是这里有个要注意的是，如果当前所有的可能的值尝试都失败，一定要重新恢复当前Cell的值。再返回false。代码如下：
/**
* 该函数假设从board[0][0]到
* board[row][col]之前的所有
* 格子都已经添满并且构成一个合理的board
* @param board 棋盘
* @param row 当前需要填充的cell的row
* @param col 当前需要填充的cell的col
* @return
*/
private static boolean solve(char[][]board, int row, int col){
int nextCol = (col + 1) % SIZE; //下一个需要填充的格子的列号
int nextRow = col == SIZE-1 ? row + 1 : row; //下一个需要填充的格子的行号
boolean[] set = new boolean[SIZE]; //记录当前格子可用的数字
if(board[row][col] == '.') {
scanColRowGrid(board, row, col, set);
for(int i = 0; i < SIZE; i++){
if(!set[i]){
board[row][col] = (char)('1' + i);
if(nextRow == SIZE) return true;
if(solve(board, nextRow, nextCol)) return true;
//else try next available number in this cell...
}
}
board[row][col] = '.'; //一定要恢复这个值
return false;
}else {
if(nextRow == SIZE) return true;
return solve(board, nextRow, nextCol);
}
}
其中的scanColRowGrid就是决定当前格可添的数字。
/**
* 决定board[row][col]可填写的数字
* @param board
* @param row
* @param col
* @param set 当函数返回时，set[i]为false表明数字i+1可以填写到棋盘中。
* @return
*/
private static boolean[] scanColRowGrid(char[][] board, int row, int col, boolean[] set){
for(int i = 0; i < SIZE; i++){
if(board[row][i] >= '1' && board[row][i] <= '9') {
set[board[row][i] - '1'] = true;
}
}
for(int i = 0; i < SIZE; i++){
if(board[i][col] >= '1' && board[i][col] <= '9') {
set[board[i][col] - '1'] = true;
}
}
int grid = getGrid(row, col);
int st_row = 3 * (grid / 3);
int st_col = 3 * (grid % 3);
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
char c = board[st_row + i][st_col + j];
if(c >= '1' && c <= '9') {
set[c - '1'] = true;
}
}
}
return set;
} /**
* 通过行号和列号查询该格子所在的3x3格
* @param row
* @param col
* @return 0～8的数字，代表从左到右从上到下的3x3格标号
*/
private static int getGrid(int row, int col){
return 3 * (row / 3) + col / 3;
}
注意我们对3x3格的标号方式，是从左到右从上到下，标号为0～8，方便我们转换。
这道题虽然不难，但是比较经典，值得总结。