[数据结构与算法]LeetCode-N 皇后（C++）

51. N 皇后

题目描述：

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

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

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

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

示例 1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

解题思路：

本题使用回溯算法。for循环遍历每一列，递归遍历每一行，每次判断该位置能否放皇后，能放皇后将皇后放进去，然后递归遍历下一行，然后回溯，取消皇后的放置。

首先定义全局变量result为结果集。初始化棋盘chessboard。

回溯三部曲

1. 确定回溯函数参数和返回值：传入的参数有n，row表示遍历到的行数以及棋盘。
2. 确定终止条件：如果row等于n，说明遍历到了最后一行，将棋盘加入结果集，返回。
3. 确定单层回溯逻辑：for循环遍历每一列，递归遍历每一行，每次判断该位置能否放皇后，能放皇后将皇后放进去，然后递归遍历下一行，然后回溯，取消皇后的放置。

判断某一位置能否放置皇后要判断该列是否有皇后，检查两个斜线是否有皇后。

代码：

class Solution {	//51. N 皇后
public:
	vector<vector<string>> result;
	bool isNotAttack(int row, int col, vector<string>& chessboard, int n) {
		for (int i = 0; i < row; ++i) {	//检查列
			if (chessboard[i][col] == '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;
		}
		//检查45度角是否有皇后
		for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
			if (chessboard[i][j] == 'Q')return false;
		}
		return true;
	}

	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 (isNotAttack(row, col, chessboard, n)) {
				chessboard[row][col] = 'Q';
				backtracking(n, row + 1, chessboard);
				chessboard[row][col] = '.';
			}
		}
	}

	vector<vector<string>> solveNQueens(int n) {
		result.clear();
		vector<string> chessboard(n, string(n, '.'));
		backtracking(n, 0, chessboard);
		return result;
	}
};

参考资料：

代码随想录