二刷LeetCode：“51.N皇后 37.解数独”题解心得（简单易懂）

引言（初遇噩梦，再遇坦然）

在阅读本文之前，建议大家已经接触过回溯算法，并完成回溯相关题目，例如：子集问题、组合问题、排列问题。
子集：子集II、子集
组合：组合、组合总和、组合总和II
排列：全排列、全排列II

🍏我第一次尝试这两道回溯算法题是在2023年的冬天。那一年，西安的冬天冷得让人直哆嗦，而在暖和得几乎让人犯困的图书馆里，这两道题却让我的心情比外面的天气还要凉快几分，简直是雪上加霜，冷到心坎里去了。之前跟着 《代码随想录》 刷题时，前面几道关于子集、组合和排列的问题简直就像是小菜一碟，让我一度觉得自己又行了。结果呢？这两道‘困难’级别的题目直接给我来了个下马威。如果你第一次就能把解析从头到尾捋个差不多，那你的水平就很NB了！（反正我当时是直接懵圈，只能尴尬而不失礼貌地保持沉默）

时隔将近一年的时间，虽然之后的这个夏天没怎么刷题吧（一段不算很差的实习经历～实在没时间精力去刷题了～～～）：

在这里插入图片描述

🌟一年的时光悄然流逝，虽然这一年我没有疯狂刷题，但当我再次面对这两道曾经让我头疼的题目时，内心竟然出奇地平静。曾经的我，一心只想着如何破题，怎么解题；如今的我，却更加关注解决问题的方法和背后的思路，这种感觉就像拨云见日般清晰。虽然这次我还是没能完全独立写出解答，但至少我已经不再像从前那样一头雾水，而是学会了逐步推导和思考。

🍎我想说的是，刷题其实是一个渐进的过程，第一次遇到难题看不懂是很正常的，不必死磕。有时候，‘简单题’未必真简单，而‘困难题’也未必无从下手。记住，积少成多，聚沙成塔。人总是在不断成长的，只要我们坚持不懈地提升自己，充实自己，曾经的难题终将成为过去式。

🍊共勉之，相信不久的将来，曾经困扰我们的题目也会迎刃而解。

好了，不说废话了，步入正轨吧😂

在这里插入图片描述

力扣第51题N皇后和第37题解数独其实大致思路是差不多的，都是基于我们在很多平台看到的回溯算法框架，例如：

void backtrack(路径，选择列表) {if (满足结束条件) {res.add(路径);return;}for (选择：选择列表) {做选择;backtrack(路径，选择列表); // 递归撤销选择;}
}

其实回溯算法就是我们常说的DFS算法，本质上就是一种暴力穷举算法，解决一个回溯问题，实际上就是一个决策树的遍历过程。其核心就是for循环里面的递归，在递归调用之前“做选择”，在递归调用之后“撤销选择”，特别简单！

在这里插入图片描述
for循环可以理解为横向遍历，递归过程则是纵向遍历，这样就把一棵树遍历了。一般来说搜索到叶子结点就是找到其中的一个结果了。（这个很重要，后续便于理解）

经典回顾

leetcode.cn/problems/n-queens/description/" rel="nofollow">51. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中'Q' 和 '.'分别代表了皇后和空位。

在这里插入图片描述

思路解读

在写这道题目之前，首先要明确它和我们之前做的其他回溯算法的题目有什么区别。都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二维矩阵还会有点不知所措，还多了一些规则约束：

同一行不能有皇后
同一列不能有皇后
同一斜线不能有皇后

这个问题的本质其实和全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。这里借随想录的树形结构举例：
在这里插入图片描述

实际上就是我们要拿到叶子节点，这样也就是皇后的具体位置了。总体上来说，就比普通的全排列问题多了一些规则约束，对Java语言来说多了一步数组转集合的操作而已。逐步拆解后你就会发现其实没有那么难！下面开始细细分析一波：

本题我用的是Java语言编写分析，C++代码见后文即可！Java操作字符串这些的其实真的麻烦！

class Solution {// 力扣的方法签名 public List<List<String>> solveNQueens(int n) {}
}

正常情况下我们拿到一个回溯算法，大多数都要定义两个全局变量(res和track)，比如这样：

class Solution {List<List<String>> res = new ArrayList<>();List<String> track = new ArrayList<>();// 力扣的方法签名 public List<List<String>> solveNQueens(int n) {}
}

但是仔细看看这个题你会发现它其实是一个List集合里面包含了二维数组，类似于就是result集合里面包含的track一样。所以我们不得不再写一个方法，将我们操作的二维数组转换为track集合。所以就有了如下代码：

class Solution {List<List<String>> res = new ArrayList<>();// 力扣的方法签名 public List<List<String>> solveNQueens(int n) {}// 二维数组转Listpublic List Array2List(char[][] chessboard) {// 这个就是我们最终返回的“track”集合！List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}
}

对二维数组进行初始化：

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {// 注意这里是字符数组char[][] chessboard = new char[n][n];// 让每一行先填满“.”  后面在指定位置放置皇后“Q”for (char[] c : chessboard) {Arrays.fill(c, '.');}// 参数待定backTrack(...);return res;}	
}

按照前文提供的回溯模版，我们来分析一下：

void backtrack(路径，选择列表) {if (满足结束条件) {res.add(路径);return;}for (选择：选择列表) {做选择;backtrack(路径，选择列表); // 递归撤销选择;}
}

参数n是棋盘的大小，用row来记录当前遍历到棋盘的第几层了。

	void backTrack(int n,int row,char[][] chessboard){if(...){}for(...){}}

前面说过，当我们遍历到叶子结点的时候，就可以收获结果了。

	void backTrack(int n,int row,char[][] chessboard){if(row == chessboard.length){// 这里相当于就是// res.add(new ArrayList<>(track));res.add(Array2List(chessboard));return;}for(...) {}}

接下来看看单层for循环要做的事情，无非就是判断当前位置能否放置皇后’Q’的问题，而且每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

	void backTrack(int n,int row,char[][] chessboard){if(...){...}for(int i = 0;i < n;i++) {// 通过isValid函数进行剪枝if(isValid(...)){chessboard[row][i] = 'Q';// 这里每递归一次，深度都要+1backtrack(n,row+1,chessboard);chessboard[row][i] = '.';}}}

OK，写到这基本上就已经结束了，剩下的就是验证棋盘是否合法就行了，这一块就纯画图写代码，没有什么难的了。所以我们的isValid函数需要三个参数，一个就是chessboard数组，一个就是row行数，一个就是col列数。通过这三个参数去判断是否合理。

在这里插入图片描述

    boolean isValid(char[][] chessboard,int row,int col){int n = chessboard.length;// 检查列for(int i = 0;i<row;i++){if(chessboard[i][col] == 'Q'){return false;}}// 检查右上斜线（45度）for(int i = row-1, j = col+1;i>=0&&j<n;i--,j++){if(chessboard[i][j] == 'Q'){return false;}}// 检查左上斜线（135度）for(int i = row-1, j = col-1;i>=0&&j>=0;i--,j--){if(chessboard[i][j] == 'Q'){return false;}}return true;}

这里大家肯定会问，按照N皇后的规则，为什么不检查左下角、右下角和下方的格子啊？为啥只检查了左上角、右上角和上方的格子呢？原因也很简单，其实我们放置皇后的时候是一层一层，由上到下放置的，所以下方的格子根本不需要检查（还没放皇后呢），又因为一行只能放置一个皇后，所以每行也不用检查了。最后只检查正上方（列）、左上、右上三个方向即可。

代码实现

Java

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for (char[] c : chessboard) {Arrays.fill(c, '.');}// 注意这里从数组第0行开始的backTrack(n, 0, chessboard);return res;}void backTrack(int n,int row,char[][] chessboard){if(row == chessboard.length){res.add(Array2List(chessboard));return;}for(int i = 0;i < n;i++){if(isValid(chessboard,row,i)){chessboard[row][i] = 'Q';backTrack(n,row+1,chessboard);chessboard[row][i] = '.';}}}// 二维数组转Listpublic List Array2List(char[][] chessboard) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}boolean isValid(char[][] chessboard,int row,int col){int n = chessboard.length;// 检查列for(int i = 0;i<row;i++){if(chessboard[i][col] == 'Q'){return false;}}// 检查右上for(int i = row-1, j = col+1;i>=0&&j<n;i--,j++){if(chessboard[i][j] == 'Q'){return false;}}// 检查左上for(int i = row-1, j = col-1;i>=0&&j>=0;i--,j--){if(chessboard[i][j] == 'Q'){return false;}}return true;}
}

C++

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isValid(row, col, chessboard, n)) { // 验证合法就可以放chessboard[row][col] = 'Q'; // 放置皇后backtracking(n, row + 1, chessboard);chessboard[row][col] = '.'; // 回溯，撤销皇后}}
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {// 检查列for (int i = 0; i < row; i++) { // 这是一个剪枝if (chessboard[i][col] == 'Q') {return false;}}// 检查 45度角是否有皇后for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') {return false;}}// 检查 135度角是否有皇后for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;
}
public:vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> chessboard(n, std::string(n, '.'));backtracking(n, 0, chessboard);return result;}
};

leetcode.cn/problems/sudoku-solver/description/" rel="nofollow">37. 解数独

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

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

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

思路解读

这个题就和上面的N皇后问题有些不一样了，N皇后问题是每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。这里借随想录的树形结构举例：

在这里插入图片描述

比较巧妙的是，递归函数的返回值需要是boolean类型，为什么呢？

因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用boolean返回值。

class Solution {public void solveSudoku(char[][] board) {backtrack(board);}boolean backtrack(char[][] board){...}
}

本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！如果一行一列确定下来了，尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！

那么会直接返回，这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

核心代码：

    boolean backtrack(char[][] board){// 遍历行for(int i =0;i<board.length;i++){// 遍历列for(int j =0;j<board[0].length;j++){// 如果该位置有数字则跳出当前循环if(board[i][j] != '.') continue;// 找到一个具体位置了，开始放1-9试试for(char k = '1';k<='9';k++){// 判断是否满足数独条件if(isValid(...)){board[i][j] = k;// 找到合适一组立刻返回// 这里相当于遍历完整个棋盘后，把结果一层一层返回上来if(backtrack(board)) return true;board[i][j] = '.';}} return false;   // 9个数都试完了，都不行，那么就返回false}}return true;  // 遍历完没有返回false，说明找到了合适棋盘位置了}

然后就是判断棋盘是否合法：

同行是否重复
同列是否重复
九宫格里是否重复

这个就是一个模拟的过程了，一步一步写出循环就行，最难理解的回溯我们已经写完了。老样子，我们必须得传一个board数组，row和col来确定其位置，还有就是当前位置放的数字合不合理。

boolean isValid(char[][] board,int row,int col,char key){// 同一行中是否有重复的数字for(int i = 0;i < 9;i++){if(board[row][i] == key){return false;}}// 同一列中是否有重复的数字for(int i = 0;i < 9;i++){if(board[i][col] == key){return false;}}// 9宫格中是否有重复的数字// 这里的startRow和startCol都是为了确保能从正确的起始位置开始// 你可以想一想如果我在第二行第二列呢？int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for(int i=startRow;i< startRow+3;i++){for(int j=startCol;j<startCol+3;j++){if(board[i][j] == key){return false;}}}return true;
}

代码实现

Java

class Solution {public void solveSudoku(char[][] board) {backtrack(board);}boolean backtrack(char[][] board){for(int i =0;i<board.length;i++){for(int j =0;j<board[0].length;j++){if(board[i][j] != '.') continue;for(char k = '1';k<='9';k++){if(isValid(board,i,j,k)){board[i][j] = k;if(backtrack(board)) return true;board[i][j] = '.';}} return false;}}return true;}boolean isValid(char[][] board,int row,int col,char key){// 同一列中是否有重复的数字for(int i=0;i<9;i++){if(board[i][col] == key){return false;}}// 同一行中是否有重复的数字for(int j = 0;j<9;j++){if(board[row][j] == key){return false;}}// 九宫格中是否有重复的数字int startrow = (row/3) * 3;int startcol = (col/3) * 3;for(int i=startrow;i< startrow+3;i++){for(int j=startcol;j<startcol+3;j++){if(board[i][j] == key){return false;}}}return true;}
}

C++

class Solution {
private:
bool backtracking(vector<vector<char>>& board) {for (int i = 0; i < board.size(); i++) {        // 遍历行for (int j = 0; j < board[0].size(); j++) { // 遍历列if (board[i][j] == '.') {for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] = k;                // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] = '.';              // 回溯，撤销k}}return false;  // 9个数都试完了，都不行，那么就返回false}}}return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判断行里是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列里是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;
}
public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};