n皇后问题//Author:王子硕Date:2011/5/24//Description:经典n皇后问题广度优先建议n<=14#include<iostream>#include<fstream>#include<algorithm>#include<functional>#include<queue>usingnamespacestd;ifstreamin("input.txt");ofstreamout("output.txt");classNode{public:Node(intn){t=0;this->n=n;loc=newint[n+1];for(inti=0;i<=n;++i){loc[i]=0;}}Node(constNode&other){this->t=other.t;this->n=other.n;this->loc=newint[n+1];for(inti=0;i<=n;++i){this->loc[i]=other.loc[i];}}intt;//已放置t个皇后int*loc;//loc[1:t]intn;//共放置n个皇后boolcheckNext(intnext);voidprintQ();};boolNode::checkNext(intnext){inti,j;for(i=1;i<=t;++i){if(loc[i]==next)//检测同行{returnfalse;}if(loc[i]-next==t+1-i)//检测反斜线行差==列差{returnfalse;}if(loc[i]-next==i-t-1)//检测正斜线{returnfalse;}}returntrue;}voidNode::printQ(){for(inti=1;i<=n;++i){out<<loc[i]<<"";}out<<endl;}classQueen{public:intn;//n皇后intansNum;//对于n皇后解的个数Queen(intn){this->n=n;ansNum=0;}voidArrangQueen();};voidQueen::ArrangQueen(){queue<Node>Q;Nodeini(n);Q.push(ini);while(!Q.empty()){Nodefather=Q.front();Q.pop();if(father.t==n){father.printQ();++ansNum;}for(inti=1;i<=n;++i){if(father.checkNext(i)){NodeChild(father);++Child.t;Child.loc[Child.t]=i;Q.push(Child);}}}}intmain(){//#defineincin//#defineoutcoutintcases;in>>cases;for(intCase=1;Case<=cases;++Case){intn;in>>n;QueenQ(n);Q.ArrangQueen();out<<"Case#"<<Case<<":"<<Q.ansNum<<endl;}return0;}