八皇后问题

对于如下棋盘：竖着为x，横着的为y

• 先看右反对角线：例如第二行的那个皇后，她的右斜线上的点，（1，3），（3，5），（4，6），我们可以看出，它的y-x是个定值2，
• 对于左反对角线：例如第四行的皇后：右斜线上的点（5，2），它的y-x是个负定值，而数组是不能存在负数下标的，那怎么办?将数组向右平移n个单位，因为右斜线上所有数都向右平移了n，所以总的数组中的关系不变。

在dfs代码中 u代表行，i代表列：

• 正对角线中，u+i是一个定值
• 反对角线中，使用i-u+n

代码：

#include<iostream>
 
using namespace std;
 
const int N = 20;//对角线的个数是2n - 1 
char g[N][N];//存储当前的图 
bool col[N], dg[N], udg[N];//列和对角线以及反对角线是否有皇后（true 有，false无） 
 
int n;
 
void dfs(int u)
{
	if(u == n)//表示已经搜了n行，故输出这条路径 
	{
		for(int i = 0; i < n; i ++)puts(g[i]);
		puts("");
		return;
	}
	
	for(int i = 0; i < n; i ++)
	{
		if(!col[i] && !dg[u + i] && !udg[n - u + i])//对角线为 n- u + i, 反对角线下标为 u + i 
		{
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1);
			//还原现场 
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
	}
}
 
int main()
{
	cin >> n;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			g[i][j] = '.';
			
	dfs(0);
	return 0;	
}