用分支限界法解决N皇后问题

分支限界法与广度优先的最大差别在于father.checkNext(i)剪枝函数会检测是否可进入下一个节点,如果不可进入，则后续的所有排列均不搜索#includeiostream#includefstream#includealgorithm#includefunctional#includequeueusingnamespacestd;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){outloc[i];}outendl;}classQueen{public:intn;//n皇后intansNum;//对于n皇后解的个数Queen(intn){this-n=n;ansNum=0;}voidArrangQueen();};voidQueen::ArrangQueen(){queueNodeQ;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;incases;for(intCase=1;Case=cases;++Case){intn;inn;QueenQ(n);Q.ArrangQueen();outCase#Case:Q.ansNumendl;}return0;}