解数独

题目描述：

编写一个程序，通过填充空格来解决数独问题。一个数独的解法需遵循如下规则：数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。提示：
1.给定的数独序列只包含数字 1-9 和字符 '.' 。
2.你可以假设给定的数独只有唯一解。
3.给定数独永远是 9x9 形式的。空白格用 '.' 表示。
以下答案标记为红色。

题目链接

class Solution {private boolean[][] digit;private char[][] result;private boolean[][] row;private boolean[][] col;private boolean[][] block;private boolean end;public void solveSudoku(char[][] board) {// 回溯算法// 初始化this.digit = new boolean[9][9];this.result = board;this.row = new boolean[9][10];this.col = new boolean[9][10];this.block = new boolean[9][10];for(int i = 0 ; i<9 ;i++){for(int j = 0 ; j<9 ;j++){if(board[i][j] != '.'){int temp = (int)(board[i][j] - '0');row[i][temp] = true;col[j][temp] = true;block[3*(i/3)+j/3][temp] = true;digit[i][j] = true;}}}DFS(0,0); // 从第一行第一列开始}public void DFS(int x,int y){if(x<8 && y == 9){DFS(x+1,0);return;}if(x == 8 && y == 9){end = true;return;}for(int i=1 ; i<=9 && !end; i++){ // 遍历当前位置需要填入的值 这里有坑：一定注意end标记要放再这里！否则会被覆盖修改！if(!digit[x][y]){ // 当前位置不为固定数字if(check(x,y,i)){ // 判断当前位置是否符合规则row[x][i] = true;col[y][i] = true;block[3*(x/3)+y/3][i] = true;result[x][y] = (char)(i+'0');DFS(x,y+1); // 对下一列空格位置递归row[x][i] = false;col[y][i] = false;block[3*(x/3)+y/3][i] = false;}}else{ // 当前位置为固定数字DFS(x,y+1);return;}}}public boolean check(int r,int c,int n){if(row[r][n] || col[c][n] || block[3*(r/3)+c/3][n]){ // 行判断、列判断和块判断return false;}return true;}
}

能简单地想到，这是一个典型的回溯法例题，首先按照行优先，每次对一个空格进行1到9的遍历，如果不符合规则，则继续遍历剩余的数字，否则对下一个空格再次执行同样的操作，当达到结束条件时。第一个需要注意地是：每次的当前规则都要还原操作；第二个需要注意地是：这个结束体一定只能执行一次！否则会发生覆盖！所以要在for上添加提前结束的条件，而不能在for循环外面。如果读者对回溯算法还是有些偏难理解，可以先尝试彻底解决八皇后问题，因为一般的回溯算法都是八皇后问题的变体，只要掌握了八皇后问题，一般这样的问题就都能迎刃而解。