企业官网建设流程全解析

欢迎来到李耶的频道【LeetCode面试题】。

解数独

37.解数独

题目

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

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

1. 数字1-9在每一行只能出现一次。
2. 数字1-9在每一列只能出现一次。
3. 数字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 == 9
• board[i].length == 9
• board[i][j]是一位数字（1-9）或者'.'
• 题目数据保证输入数独仅有一个解

解法一：回溯法（DFS）⭐

思路：采用深度优先搜索策略，逐个处理空白格。对于每个空白格，尝试填入数字1-9，并通过辅助函数检查填入是否合法（所在行、列、3x3宫格内无重复）。如果合法，则递归处理下一个空白格；若后续填数无解，则回溯撤销当前填入的数字，尝试下一个数字。

3x3宫格索引计算：boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)。

functionsolveSudoku(board){constrows=newArray(9).fill().map(()=>newArray(10).fill(false));constcols=newArray(9).fill().map(()=>newArray(10).fill(false));constboxes=newArray(9).fill().map(()=>newArray(10).fill(false));constspaces=[];// 1. 初始化：记录已有数字，收集空位for(leti=0;i<9;i++){for(letj=0;j<9;j++){constchar=board[i][j];if(char==='.'){spaces.push([i,j]);}else{constnum=Number(char);constboxIndex=Math.floor(i/3)*3+Math.floor(j/3);rows[i][num]=true;cols[j][num]=true;boxes[boxIndex][num]=true;}}}// 2. 回溯填充functiondfs(index){// 所有空位都填满了，说明找到了一个可行解if(index===spaces.length){returntrue;}const[i,j]=spaces[index];constboxIndex=Math.floor(i/3)*3+Math.floor(j/3);for(letnum=1;num<=9;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(index+1)){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){constnumStr=String(num);constboxRowStart=Math.floor(row/3)*3;constboxColStart=Math.floor(col/3)*3;for(leti=0;i<9;i++){if(board[row][i]===numStr)returnfalse;if(board[i][col]===numStr)returnfalse;}for(leti=boxRowStart;i<boxRowStart+3;i++){for(letj=boxColStart;j<boxColStart+3;j++){if(board[i][j]===numStr)returnfalse;}}returntrue;}functiondfs(){for(leti=0;i<9;i++){for(letj=0;j<9;j++){if(board[i][j]==='.'){for(letnum=1;num<=9;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检查，逻辑非常直观
• 劣势：每次检查都需要扫描行、列、宫，效率低于解法一的布尔数组；建议面试中使用解法一

解法对比

扩展题

1. 有效的数独：判断一个9x9数独是否有效，无需解决它。
2. N 皇后问题：经典的 N 皇后问题，其解题思路（回溯 + 剪枝）与解数独高度相似。

“锲而不舍，金石可镂。” —— 荀子《劝学》

关注李耶，每天一道面试题，一起卷起来 🔥