n皇后问题
背景：
八皇后问题是一个以国际象棋为背景的问题:如何能够在 8*8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。在古代求一个8皇后问题就难为人了，在现代可以依靠计算机帮我们计算，甚至可以延伸到n皇后。
问题描述：
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
输入：共有若干行，每行一个正整数N=10，表示棋盘和皇后的数量；如果N=0，表示结束。
输出： 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
皇后可以对行，列，对角线共八个方向进行攻击，要使得皇后不能互相攻击。
如上如所示是符合条件的一种情况。
思路：一看n只有1~10，意味着可以暴力算法算出每一种情况对应的种类数count，再用一个Switch case就行了。
解析看代码
#include#include using namespace std; int n; int Count = 0; const int maxn = 100001; int P[maxn];//不同方案，下标存列，值存行 bool hasTable[maxn] = {false}; void generateP(int index) { if(index == n+1) { { Count++; return;//结束 } } for(int x = 1 ; x <= n ; x++)//x 行，index列 { if(hasTable[x]==false)//这行被标记就跳过 { bool flag = true; //默认排列为真 for(int pre = 1 ; pre < index ; pre++)//判断对角线 { if(abs(x-P[pre]) == abs(index-pre)) { //如果这2个位置行数之差==列数之差那么 flag = false; //这2个位置在同一条对角线上 break; //1 0 0 0 0 } //0 2 0 0 0 } //0 0 3 0 0 if(flag)//如果对角线不满足就无法进入下一步 //0 0 0 4 0 { //0 0 0 0 5 P[index] = x; hasTable[x] = true;//标记 generateP(index + 1);//列数加一 hasTable[x] = false;//回溯,取消此次标记，进入循环尾 } } } } void chushihua() { Count = 0; memset(hasTable,false,maxn); } int main() { while(cin >> n){ if(n==0) return 0; generateP(1); cout << Count << endl; chushihua(); } return 0; }
运行结果：
