LeetCode--37. 解数独（回溯算法）
37. 解数独题目描述编写一个程序通过填充空格来解决数独问题。数独的解法需遵循如下规则数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字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 9board[i].length 9board[i][j]是一位数字或者.题目数据保证输入数独仅有一个解代码classSolution{/** * 判断当前位置填入数字 k 是否合法 * * param row 当前行 * param column 当前列 * param k 当前尝试填入的数字 * param board 当前数独棋盘 */publicbooleanisValid(introw,intcolumn,chark,char[][]board){/** * 检查同行、同列 * * 数独规则 * 同一行、同一列不能出现重复数字 */for(inti0;i9;i){// 同行存在重复if(board[row][i]k){returnfalse;}// 同列存在重复if(board[i][column]k){returnfalse;}}/** * 检查 3 × 3 九宫格 */// 当前九宫格左上角坐标introwStartrow/3*3;intcolumnStartcolumn/3*3;// 遍历当前九宫格for(intirowStart;irowStart3;i){for(intjcolumnStart;jcolumnStart3;j){// 九宫格中存在重复数字if(board[i][j]k){returnfalse;}}}// 当前位置合法returntrue;}/** * 回溯函数 * * 返回值 * true - 找到正确解 * false - 当前路径失败 */publicbooleanbacktracking(char[][]board){/** * 遍历整个棋盘 */for(inti0;i9;i){for(intj0;j9;j){/** * 找到空格 */if(board[i][j].){/** * 尝试填入 1 ~ 9 */for(chark1;k9;k){/** * 如果当前数字合法 */if(isValid(i,j,k,board)){// 做选择填入数字board[i][j]k;// 递归下一层booleanresultbacktracking(board);/** * 如果后续成功 * 直接返回 true */if(resulttrue){returntrue;}/** * 回溯 * 当前数字不行恢复为空格 */board[i][j].;}}/** * 1~9 都尝试失败 * * 说明当前路径无解 */returnfalse;}}}/** * 没有找到空格 * * 说明整个棋盘已经填完 * 找到正确答案 */returntrue;}publicvoidsolveSudoku(char[][]board){// 启动回溯backtracking(board);}}
