链接：51. N 皇后
题解：
这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
函数 backtrack 依然像个在决策树上游走的指针，通过 row 和 col 就可以表示函数遍历到的位置，通过 isValid 函数可以将不符合条件的情况剪枝：
核心框架：
// 函数找到一个答案后就返回 true bool backtrack(vector<string>& board, int row) { // 触发结束条件 if (row == board.size()) { res.push_back(board); return true; } ... for (int col = 0; col < n; col++) { ... board[row][col] = 'Q'; if (backtrack(board, row + 1)) return true; board[row][col] = '.'; } return false; } for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择 路径.remove(选择) 将该选择再加入选择列表 class Solution { public: vector<vector<string>> res; /* 输入棋盘边长 n，返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) { // '.' 表示空，'Q' 表示皇后，初始化空棋盘。 vector<string> board(n, string(n, '.')); backtrack(board, 0); return res; } // 路径：board 中小于 row 的那些行都已经成功放置了皇后 // 选择列表：第 row 行的所有列都是放置皇后的选择 // 结束条件：row 超过 board 的最后一行 void backtrack(vector<string>& board, int row) { // 触发结束条件 if (row == board.size()) { res.push_back(board); return; } int n = board[row].size(); for (int col = 0; col < n; col++) { // 排除不合法选择 if (!isValid(board, row, col)) continue; // 做选择 board[row][col] = 'Q'; // 进入下一行决策 backtrack(board, row + 1); // 撤销选择 board[row][col] = '.'; } } /* 是否可以在 board[row][col] 放置皇后？ */ bool isValid(vector<string>& board, int row, int col) { int n = board.size(); // 检查列是否有皇后互相冲突 for (int i = 0; i < n; i++) { if (board[i][col] == 'Q') return false; } // 检查右上方是否有皇后互相冲突 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') return false; } // 检查左上方是否有皇后互相冲突 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') return false; } return true; } };
