八皇后问题

大体思路

首先定义一个8*8的二维矩阵，所有的元素都为0，然后开始调用回溯函数寻找皇后。
BackTrack函数是一个回溯函数，回溯的终止条件为计数变量n为8，即皇后放到了最后一行。如果n不等于8，则循环放尝试每一列，如果可以放则将这个位置标记为1，然后继续向下一行查找，直到找完所有8行。
找完后回溯依次往回跳出，并把之前找的皇后记录消除抹掉，即将其再次赋值为0，然后再寻找下一位置。
Judge判断函数用来判断这个位置是否可以放皇后。如下分别判断这一列上是否已经有皇后、对角线和反对角线上是否已经有皇后，因为是按行逐个尝试，所以不需要判断行上是否有皇后。在判断对角线和反对角线时，因为临界点的问题，需要四个方向分别判断，这种方法个人感觉比较麻烦，但是确实还没想到更加巧妙的方法，希望大家再评论区补充。
最后是print打印棋盘函数，该函数遍历棋盘，将棋盘中标记为1的点输出q作为皇后。

部分代码

#include<iostream>
using namespace std;
int num = 0;
void print(int qp[8][8]);
bool isValid(int qp[8][8], int r, int c) {
	// 判断一列上有无皇后
	for (int i = 0; i < 8; i++) {
		if (i == r) continue;
		else if (qp[i][c] == 1)return false;
	}

	//判断左对角
	int j = c - 1;
	for (int i = r - 1; i >= 0 && j >= 0; i--) {
		if (qp[i][j] == 1) return false;
		j--;

	}
	j = c + 1;
	for (int i = r + 1; i < 8 && j < 8; i++) {
		if (qp[i][j] == 1) return false;
		j++;
	}

	//判断右对角
	j = c + 1;
	for (int i = r - 1; i >= 0 && j < 8; i--) {
		if (qp[i][j] == 1) return false;
		j++;
	}
	j = c - 1;
	for (int i = r + 1; i < 8 && j >= 0; i++) {
		if (qp[i][j] == 1) return false;
		j--;
	}
	return true;
}
//深搜函数
void backTrack(int qp[8][8], int n) {
	//如果第九行就结束，表示8个皇后已经安放完毕
	if (n == 8) {
		cout<<++num <<":"<<endl;
		print(qp);
		cout<<"------------------------"<<endl;
		return;
	}
	else {
		for (int j = 0; j < 8; j++) {
			if (isValid(qp, n, j)) {
				qp[n][j] = 1;  //放皇后
				backTrack(qp, n + 1); //递归
				qp[n][j] = 0;//回溯，把皇后拿掉
			}
		}
	}

}
//输出棋盘
void print(int qp[8][8]) {
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (qp[i][j] == 1) cout<<'q';
			else cout<<'0';
		}
		cout << endl;
	}
}
int  main() {
	int a[8][8]{ 0 };
	backTrack(a, 0);//深搜开始
	cout<<"total:" <<num<<endl;
	return 0;
}

代码结果

总结

这个实验利用回溯迭代的方法进行了八皇后问题的查找。我觉得最关键的地方就是一层层的回溯放置皇后，和一层层跳出抹去标记的过程。回溯的终止条件为找遍了最后一行，此时便完成一次八皇后解的查找。完成查找后回溯上一行向，下一个位置遍历尝试，直到最后回溯到第1行的第8列，此时完成了八皇后所有解的查找。
我认为理解回溯问题最重要的找到终止条件和回溯条件，需要将什么时候向下一步走、什么时候往回走的条件写好。