LeetCode--37. 解数独（回溯算法）

37. 解数独

题目描述

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

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

1. 数字1-9在每一行只能出现一次。
2. 数字1-9在每一列只能出现一次。
3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用'.'表示。

示例 1：

输入：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"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j]是一位数字或者'.'
• 题目数据保证输入数独仅有一个解

代码

classSolution{/** * 判断当前位置填入数字 k 是否合法 * * @param row 当前行 * @param column 当前列 * @param k 当前尝试填入的数字 * @param board 当前数独棋盘 */publicbooleanisValid(introw,intcolumn,chark,char[][]board){/** * 检查同行、同列 * * 数独规则： * 同一行、同一列不能出现重复数字 */for(inti=0;i<9;i++){// 同行存在重复if(board[row][i]==k){returnfalse;}// 同列存在重复if(board[i][column]==k){returnfalse;}}/** * 检查 3 × 3 九宫格 */// 当前九宫格左上角坐标introwStart=row/3*3;intcolumnStart=column/3*3;// 遍历当前九宫格for(inti=rowStart;i<rowStart+3;i++){for(intj=columnStart;j<columnStart+3;j++){// 九宫格中存在重复数字if(board[i][j]==k){returnfalse;}}}// 当前位置合法returntrue;}/** * 回溯函数 * * 返回值： * true -> 找到正确解 * false -> 当前路径失败 */publicbooleanbacktracking(char[][]board){/** * 遍历整个棋盘 */for(inti=0;i<9;i++){for(intj=0;j<9;j++){/** * 找到空格 */if(board[i][j]=='.'){/** * 尝试填入 1 ~ 9 */for(chark='1';k<='9';k++){/** * 如果当前数字合法 */if(isValid(i,j,k,board)){// 做选择：填入数字board[i][j]=k;// 递归下一层booleanresult=backtracking(board);/** * 如果后续成功， * 直接返回 true */if(result==true){returntrue;}/** * 回溯： * 当前数字不行，恢复为空格 */board[i][j]='.';}}/** * 1~9 都尝试失败 * * 说明当前路径无解 */returnfalse;}}}/** * 没有找到空格 * * 说明整个棋盘已经填完 * 找到正确答案 */returntrue;}publicvoidsolveSudoku(char[][]board){// 启动回溯backtracking(board);}}