Leetcode--Java--37. 解数独

题目描述

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

样例描述

输入：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"]]
输出：[["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"]]

思路

1. 递归回溯法。
   
   对于每一个空位，根据布尔数组看每一行、列，九宫格哪些数被填过了，枚举所有可以填的数字。然后继续，如果都不能填，就回溯到上一个状态。

代码

classSolution{//标记row[i][t]第i行 的是否存在tboolean  row[][]=newboolean[9][9];boolean  col[][]=newboolean[9][9];//cell通过i/3,j/3坐标来确定存在数字tboolean cell[][][]=newboolean[3][3][9];publicvoidsolveSudoku(char[][] board){//初始化board已经有的数for(int i=0; i<9; i++){for(int j=0; j<9; j++){if(board[i][j]!='.'){//获取数  减一因为数放在下标0-8int t= board[i][j]-'1';//将该数标记在对应的行 列以及九宫格
                 row[i][t]= col[j][t]= cell[i/3][j/3][t]=true;}}}dfs(board,0,0);}//通过返回boolean来判断当前分支是否可以，所以不是voidpublicbooleandfs(char[][] board,int x,int y){//对于每一行，从左往右根据列来填//这一行所有列填完if(y==9){//换下一行，从第一列开始
            x++;
            y=0;}//所有行填完，x到9 说明数独全部填完if(x==9)returntrue;//如果这个位置已经有数，直接下一个,一定要带return！ 因为要标志分支是否可解if(board[x][y]!='.')returndfs(board, x, y+1);//否则是空位 就开始枚举所有可以填的数for(int num=0; num<9; num++){//如果这个数不在行、列和九宫格出现过才能填if(!row[x][num]&&!col[y][num]&&!cell[x/3][y/3][num]){//填入数   加'1'恢复数
                board[x][y]=(char)(num+'1');
                row[x][num]= col[y][num]= cell[x/3][y/3][num]=true;//当前填完后，如果下一个也成功，才说明是正确的if(dfs(board, x, y+1))returntrue;//否则，下一个失败的话。 进行回溯，恢复所有状态
               board[x][y]='.';
               row[x][num]= col[y][num]= cell[x/3][y/3][num]=false;}}//如果上面for循环的都出现在九宫格了，说明当前分支无解，return到上个状态returnfalse;}}