题解 | 八皇后问题

8皇后问题：将8 个皇后放置在8*8的棋盘上，并且使得皇后彼此之间不能攻击。

皇后彼此不能相互攻击：指的是任何两个皇后都不能处于同一条横线、纵线或者斜线上。

返回解决方案个数。

思路：逐行放置皇后，每次尝试将皇后放在当前一行的某一列，判断是否不互相攻击，，冲突则跳过该列；如果不冲突就在该列放置皇后，并且递归处理下一个位置的皇后，最后注意撤销当前选择的列，以便尝试其他可能的列。

#include<stdio.h>
#include<vector>
using namespace std;

vector<vector<int>> queeenVec;//结果序列
void DFSFindQueen(vector<int> &queen, int pos) {//pos为下一号皇后
	//在i中找到合适的列
	for (int i = 1; i <= 8; i++) {
		bool isOK = true;
		for (int j = 0; j < pos; j++) {//遍历0~pos-1行
			if (queen[j] == i||j-queen[j] == pos-i || j + queen[j] == pos +i) {//同一列或斜对角
				isOK = false;
				break;//冲突
			}
		}
		if (isOK == true) {//位置无冲突
			queen.push_back(i);
			if (pos == 7) {
				queeenVec.push_back(queen);//已找到8个合适位置
				for (int k = 0; k <8; k++) {
					printf("%d",queen[k]);
				}
				printf("\n");
			}
			else {
				//递归找下一个合适列
				DFSFindQueen(queen, pos + 1);
			}
			queen.pop_back();//撤销选择，回溯一边尝试其他可能
		}
	}

}
int main() {
	vector<int> queen;//存放每行皇后对应的列
	DFSFindQueen(queen, 0);
	printf("%d\n", queeenVec.size());//92种可能
	return 0;
}