欢迎来到李耶的频道【LeetCode面试题】。解数独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] ] 输出true输入board [ [8,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] ] 输出false提示board.length 9board[i].length 9board[i][j]是一位数字1-9或者.题目数据保证输入数独仅有一个解解法一回溯法DFS⭐思路采用深度优先搜索策略逐个处理空白格。对于每个空白格尝试填入数字1-9并通过辅助函数检查填入是否合法所在行、列、3x3宫格内无重复。如果合法则递归处理下一个空白格若后续填数无解则回溯撤销当前填入的数字尝试下一个数字。3x3宫格索引计算boxIndex Math.floor(i / 3) * 3 Math.floor(j / 3)。functionsolveSudoku(board){constrowsnewArray(9).fill().map(()newArray(10).fill(false));constcolsnewArray(9).fill().map(()newArray(10).fill(false));constboxesnewArray(9).fill().map(()newArray(10).fill(false));constspaces[];// 1. 初始化记录已有数字收集空位for(leti0;i9;i){for(letj0;j9;j){constcharboard[i][j];if(char.){spaces.push([i,j]);}else{constnumNumber(char);constboxIndexMath.floor(i/3)*3Math.floor(j/3);rows[i][num]true;cols[j][num]true;boxes[boxIndex][num]true;}}}// 2. 回溯填充functiondfs(index){// 所有空位都填满了说明找到了一个可行解if(indexspaces.length){returntrue;}const[i,j]spaces[index];constboxIndexMath.floor(i/3)*3Math.floor(j/3);for(letnum1;num9;num){if(!rows[i][num]!cols[j][num]!boxes[boxIndex][num]){// 尝试填入数字rows[i][num]true;cols[j][num]true;boxes[boxIndex][num]true;board[i][j]String(num);// 递归处理下一个空位if(dfs(index1)){returntrue;}// 回溯撤销填入的数字rows[i][num]false;cols[j][num]false;boxes[boxIndex][num]false;board[i][j].;}}returnfalse;// 1-9 都试过了无解触发回溯}dfs(0);}时间复杂度 / 空间复杂度O(9^m) / O(9^2)其中 m 为空位数量最大 81。回溯算法本质是暴力搜索最坏情况下需要探索 9^m 种可能但由于数独约束强实际效率远高于理论值。空间主要用于递归调用栈和三个布尔数组。优势采用经典的 DFS 回溯框架并使用高效的布尔数组进行行-列-宫三重校验是面试中最推荐的写法。解法二行优先顺序枚举思路不预先收集空位而是从(0,0)开始按行优先顺序遍历整个棋盘。遇到空位则尝试填入数字并递归已填数字则跳过。这种方式与解法一本质相同只是实现细节略有差异。functionsolveSudoku(board){functionisValid(row,col,num){constnumStrString(num);constboxRowStartMath.floor(row/3)*3;constboxColStartMath.floor(col/3)*3;for(leti0;i9;i){if(board[row][i]numStr)returnfalse;if(board[i][col]numStr)returnfalse;}for(letiboxRowStart;iboxRowStart3;i){for(letjboxColStart;jboxColStart3;j){if(board[i][j]numStr)returnfalse;}}returntrue;}functiondfs(){for(leti0;i9;i){for(letj0;j9;j){if(board[i][j].){for(letnum1;num9;num){if(isValid(i,j,num)){board[i][j]String(num);if(dfs())returntrue;board[i][j].;}}returnfalse;}}}returntrue;}dfs();}时间复杂度 / 空间复杂度O(9^m) / O(9^2)优势isValid函数直接对board检查逻辑非常直观劣势每次检查都需要扫描行、列、宫效率低于解法一的布尔数组建议面试中使用解法一解法对比解法核心机制优势推荐指数回溯法预处理空位 布尔数组DFS 三重状态数组校验高效状态管理清晰⭐⭐⭐⭐⭐回溯法行优先顺序枚举DFS 实时校验代码结构非常直观⭐⭐⭐⭐扩展题有效的数独判断一个9x9数独是否有效无需解决它。N 皇后问题经典的 N 皇后问题其解题思路回溯 剪枝与解数独高度相似。“锲而不舍金石可镂。” —— 荀子《劝学》关注李耶每天一道面试题一起卷起来