题目：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。代码如下：
1 /** 2 * 该函数假设从board[0][0]到 3 * board[row][col]之前的所有 4 * 格子都已经添满并且构成一个合理的board 5 * @param board 棋盘 6 * @param row 当前需要填充的cell的row 7 * @param col 当前需要填充的cell的col 8 * @return 9 */ 10 private static boolean solve(char[][]board, int row, int col){ 11 int nextCol = (col + 1) % SIZE; //下一个需要填充的格子的列号 12 int nextRow = col == SIZE-1 ? row + 1 : row; //下一个需要填充的格子的行号 13 boolean[] set = new boolean[SIZE]; //记录当前格子可用的数字 14 if(board[row][col] == '.') { 15 scanColRowGrid(board, row, col, set); 16 for(int i = 0; i < SIZE; i++){ 17 if(!set[i]){ 18 board[row][col] = (char)('1' + i); 19 if(nextRow == SIZE) return true; 20 if(solve(board, nextRow, nextCol)) return true; 21 //else try next available number in this cell... 22 } 23 } 24 board[row][col] = '.'; //一定要恢复这个值 25 return false; 26 }else { 27 if(nextRow == SIZE) return true; 28 return solve(board, nextRow, nextCol); 29 } 30 }
其中的scanColRowGrid就是决定当前格可添的数字。
1 /** 2 * 决定board[row][col]可填写的数字 3 * @param board 4 * @param row 5 * @param col 6 * @param set 当函数返回时，set[i]为false表明数字i+1可以填写到棋盘中。 7 * @return 8 */ 9 private static boolean[] scanColRowGrid(char[][] board, int row, int col, boolean[] set){ 10 for(int i = 0; i < SIZE; i++){ 11 if(board[row][i] >= '1' && board[row][i] <= '9') { 12 set[board[row][i] - '1'] = true; 13 } 14 } 15 for(int i = 0; i < SIZE; i++){ 16 if(board[i][col] >= '1' && board[i][col] <= '9') { 17 set[board[i][col] - '1'] = true; 18 } 19 } 20 int grid = getGrid(row, col); 21 int st_row = 3 * (grid / 3); 22 int st_col = 3 * (grid % 3); 23 for(int i = 0; i < 3; i++){ 24 for(int j = 0; j < 3; j++){ 25 char c = board[st_row + i][st_col + j]; 26 if(c >= '1' && c <= '9') { 27 set[c - '1'] = true; 28 } 29 } 30 } 31 return set; 32 } 33 34 /** 35 * 通过行号和列号查询该格子所在的3x3格 36 * @param row 37 * @param col 38 * @return 0～8的数字，代表从左到右从上到下的3x3格标号 39 */ 40 private static int getGrid(int row, int col){ 41 return 3 * (row / 3) + col / 3; 42 }
注意我们对3x3格的标号方式，是从左到右从上到下，标号为0～8，方便我们转换。
这道题虽然不难，但是比较经典，值得总结。