回溯法 解 n皇后问题

#include <iostream>

using namespace std;

int x[20]; //解向量
int sum; //可行方案个数
int n;

//在第t列是否可放置
bool place(int t){
	int i;
	for(i=1; i<t; i++)
		//如果 行-行 == 列-列 或者 在同一列。
		if(abs(t-i) == abs(x[t]-x[i]) || x[i]==x[t])
			return false;
	return true;
}

//回溯，即递归调用
void backtrack(int t){
	//cout << t << endl;
	int i;
	//到达最后一行，即找到所有解
	if(t > n){
		sum++;
		for(i=1; i<=n; i++)
			printf(" %d",x[i]);
		printf("\n");
	}else{
		//从第一行第一列开始，循环到 第一行 第n列
		for(i=1; i<=n; i++){
			x[t] = i; //对于第t行，第i列，放置皇后.

			//判断刚才放置的位置（x[t] = i）是否可行，如果可行，就放置下一行。
			//不可行的话，继续在第t行放置
			if(place(t))  backtrack(t+1);
		}
	}
}
int main(){
	while(cin >> n){
		backtrack(1); //从第1行开始
		cout << "方案数：" <<sum << endl; //可行解个数
	}
	
	return 0;
}