八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

原理：用递归来模拟每一行，用循环来模拟一行中的每一格，检查当前格能否满足条件，如果一直到第八行结束都满足，则更新一种解法。

原始解法：由于数量级小，可以用二维数组来表示坐标，当模拟到某一格时，检查在对角线或者同列有没有其他已经被标记过的点，如果没有，就进入下一次递归，也就是模拟下一行，直到模拟结束，cnt就是所求的结果。

优化：可以用一维数组来代替二维数组，因为行号是顺序的，所以可以用数组下标来表示行，数组元素表示这一行的第几列加入这种解法。check()函数用来检查有没有和之前的点同列或者同对角线，比二维数组的方法更加简单，时间和空间也都有所优化。

解法：

cpp
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define rrep(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define lep(i, a, b) for(int i = (int)(a); i >= (int)(b); i--)
#define UPS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-7, PI = acos(-1);
/*=======================================*/
short arr[13]={0},s=1,m=8;
LL sum=0;
int cnt=0;

int check(int n){
	
	rrep(i,1,s){
		sum++;
		if(arr[i]==n) return 0;
		if((int)fabs(i-s)==(int)fabs(arr[i]-n)) return 0;
	}
	return 1;
}

void dfs(){
	if(s==m+1){
		cnt++;
		return;
	}
	rep(i,1,m){
//		if(arr[s][i]==0){				//此处为原始解法
//			v[s]=i;
//			rep(j,1,8){
//				arr[s][j]++;
//				arr[j][i]++;
//				int fs=(int)fabs(s-j);
//				if(i-fs>0) arr[j][i-fs]++;
//				if(i+fs<=8) arr[j][i+fs]++;
//			}
//			arr[s][i]-=3;
//			s++;
//			dfs();
//			s--;
//			arr[s][i]+=3;
//			rep(j,1,8){
//				arr[s][j]--;
//				arr[j][i]--;
//				int fs=(int)fabs(s-j);
//				if(i-fs>0) arr[j][i-fs]--;
//				if(i+fs<=8) arr[j][i+fs]--;
//			}
//		}
		if(check(i)){
			arr[s++]=i;
			dfs();
			s--;
		}
	}
}

int main(){
	UPS

	LARGE_INTEGER t1,t2,tc;
	QueryPerformanceFrequency(&tc);
	QueryPerformanceCounter(&t1);

	dfs();
	cout<<cnt<<endl;
	cout<<sum<<endl;
	
	QueryPerformanceCounter(&t2);
	double time=(double)(t2.QuadPart-t1.QuadPart)/(double)tc.QuadPart;
	cout<<"time = "<<time*1000<<"ms"<<endl;
	
	return 0;
}