学步园

回溯法：全排列并进行剪枝

#include <iostream>
#include <algorithm>
using namespace std;

#define N 100000
int C[N];
int tot;
int visited[3][N];//列访问，副对角线访问，主对角线访问

//八皇后问题
void search(int n, int cur)
{
	if (cur == n)
		tot++;
	else for (int i = 0; i < n; i++)
	{
		if (!visited[0][i] && !visited[1][cur + i] && !visited[2][cur - i + n])
		{
			C[cur] = i;
			visited[0][i] = visited[1][cur + i] = visited[2][cur - i + n] = 1;
			search(n, cur + 1);
			visited[0][i] = visited[1][cur + i] = visited[2][cur - i + n] = 0;
		}
	}
}

int main()
{
	int n;
	cin >> n;
	search(n, 0);
	cout << tot << endl;
	return 0;
}