按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
思路：
和以前回溯的思路是一样的，但棋盘问题没有path了，得到一个解法就返回到res里。
注意Q能否放置的判断条件isPlay不能写成一个对应棋盘的二维数组，isPlay是判断当前格子的行列，对角线是否已被占用的，而不是根据每个格子的isPlay来决定能不能放Q。
如果你真的以每个格子的isPlay来决定能不能放Q，就会超时，因为每次遍历格子，isplay都要遍历完整个棋盘。
如果isPlay只遍历一次棋盘，就只能保证第一个Q不在其他Q攻击范围，并不能保证其他Q不相互攻击。
所以isPlay是用vector<vector<bool>>& isPlay来表示，第一个[]里放0，1，2,用于表示列，主对角线，副对角线，第二个[]里放列，主对角线，副对角线对应的值。
用列进行遍历，用行来递归。
代码如下：
class Solution {
private:
vector<vector<string>> res; // 存储所有解法
// 回溯函数，`row` 表示当前行的索引
void backtracking(int n, int row, vector<string>& chessboard, vector<vector<bool>>& isPlay) {
// 当所有行都放置完皇后时，表示找到一个解
if (row == n) {
res.push_back(chessboard); // 找到一个解，加入结果
return;
}
// 尝试在当前行的每一列放皇后
for (int col = 0; col < n; col++) {
// 如果当前列已经被占用，或者该位置在主对角线或者副对角线上被占用，跳过
if (isPlay[0][col] || isPlay[1][row - col + n - 1] || isPlay[2][row + col]) {
continue;
}
// 放置皇后
chessboard[row][col] = 'Q';
// 标记当前列和对角线已被占用
isPlay[0][col] = true; // 标记列占用
isPlay[1][row - col + n - 1] = true; // 标记主对角线占用
isPlay[2][row + col] = true; // 标记副对角线占用
// 递归到下一行
backtracking(n, row + 1, chessboard, isPlay);
// 回溯，撤销放置的皇后和标记
chessboard[row][col] = '.';
isPlay[0][col] = false;
isPlay[1][row - col + n - 1] = false;
isPlay[2][row + col] = false;
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> chessboard(n, string(n, '.')); // 初始化一个 n x n 的棋盘
vector<vector<bool>> isPlay(3, vector<bool>(2 * n - 1, false)); // 三个标记数组：列、主对角线、副对角线
// 0 -> 列的占用情况
// 1 -> 主对角线的占用情况
// 2 -> 副对角线的占用情况
backtracking(n, 0, chessboard, isPlay); // 从第 0 行开始回溯
return res; // 返回所有解法
}
};
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
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"]]
这道题看似复杂，其实很简单，只要搞清楚怎么回溯就行了。
应为只有一个解，即完成棋盘，那么我们只有遇到“.”的时候把1~9都换进去尝试，判断条件就是行列和九宫格没有相同的数（写在另一个函数里），如果1~9都放不进去，说明解法错误，进行回溯，即把当前格子重新换成点。
在定义backtracking的时候，要用bool，不用void了，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。
代码如下：
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; // 放置k
if (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); }
};
暂无评论