秒懂八皇后，dfs+回溯

前言：

八皇后问题时一个很经典的算法问题，我们自己一个一个试的话很麻烦，很容易漏掉某种情况，而计算机特有的重复方法可以让我们更好的解决问题，这或许就是我们学习计算机的意义吧

那么接下来让我们看一看八皇后问题

题目描述：

输入与输出：

思路： 

首先看到棋盘，我们很容易想到dfs，那我们如何运用呢？

首先，本题的关于摆放问题的限制很多：

1.一行只能有一个皇后

2.一列只能有一个皇后

3.从右上到左下的对角线（/）只能有一个皇后

4.从左上到右下的对角线（\）只能有一个皇后

1和2用数组标记很容易解决，那么3和4的解决方法成为了本题的难点

给出一个标有行和列的方格，

给出一个标有行和列的方格，我们很容易发现从右上到左下的对角线上的方格，每往下一个行加1而列减1，我们不难发现每条对角线上方格的和是一样的，而每条对角线各自的和是不一样的，因此条件3我们可以用行加列的和来区分辨别

同理从左上到右下的对角线上的方格，每往下一个行加1且列加1，我们不难想到，每条对角线上方格的差是一样的，而每条对角线各自的差是不一样的，但与3不同的是，差值可能出现负值而导致数组越界访问，那么我们将其加上n即可

AC代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30] = { 0 };
int b[30] = { 0 };
int c[30] = { 0 };
int d[30] = { 0 };
//注意此处要开26以上，因为本题数据n最大为30，行加列最大可到26；
//数组a记录行，b列，c对角线/ ，d对角线\;
//为1则存在皇后，为0则不存在
int summ = 0;//记录总共的可能数
void print() {
	if (summ < 3) {
		for (int i = 1; i <= n; i++) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	summ++;
}
//dfs的变量i为第几个皇后，因为每行只有一个皇后，i也可代表表格第i行
void dfs(int i) {
	if (i == n + 1) {
		print();
		return;
	}
	else {
		//j表示列
		for (int j = 1; j <= n; j++) {
			if (b[j] == 0 && c[i + j] == 0 && d[i - j + n] == 0) {
				a[i] = j;//记录要输出的数据，因为每次i都是从1到n，因此不用清空数组a
				b[j] = 1;
				c[i + j] = 1;
				d[i - j + n] = 1;
				dfs(i + 1);
				b[j] = 0;
				c[i + j] = 0;
				d[i - j + n] = 0;
			}
		}
	}
}
int main() {
	cin >> n;
	dfs(1);
	printf("%d", summ);
}