8皇后-----回溯法C++编程练习
/* * 八皇后问题回溯法编程练习 * 在8×8的棋盘上,放置8个皇后,两个皇后之间不能两两攻击 * 也即,直线,垂直45度、135度方向不能出现两个皇后 * * copyright Michael 2014-12-19 * QQ 1192065414 **/ #include <iostream> #include <stack> #include <stdlib.h> #include <string.h> using namespace std; struct Sposition { int iRow; int iColumn; }; /* * 保存结果使用的栈 **/ stack<Sposition> ResultStack; /* * 判断在水平方向x,垂直方向y,是否可以放置新皇后 **/ bool JudgeIsAcceptable(int x ,int y) { struct Sposition pos; stack<Sposition> resultS(ResultStack); int stackSize = resultS.size(); for ( ; stackSize > 0 ; --stackSize ) { pos = resultS.top(); if( pos.iRow == x ) //判断同一直线上是否已经有皇后 { return false; } if( (x-pos.iRow) == (y-pos.iColumn) ) //判断45度角是否已经有皇后 { return false; } if( (x-pos.iRow) == (pos.iColumn-y) ) //判断-45度角是否已经有皇后 { return false; } resultS.pop(); } return true; } /* * 皇后放置算法 * 0 0 0... * 0 0 0... * 0 0 0... * ...... * 遍历第0列,取第0列的第一个、第二个... * 从第1列开始尝试,然后尝试第2列,当尝试到一列,8行都不能放置皇后,则回溯,返回前一列的下一行继续尝试 **/ void SolveQueue() { Sposition pos; for (int i = 0 ; i < 8 ; ++i ) { //The first line of the queue pos.iRow = i; pos.iColumn = 0; ResultStack.push(pos); int x = 0; //标记当前行,0~7行 int y = 1; //标记当前列,0~7列 while( y<8 ) //从第一列开始 { for ( ; x < 8 ; ++x ) //从第0行开始探索 { if ( JudgeIsAcceptable(x,y) ) { pos.iRow = x; pos.iColumn = y; ResultStack.push(pos); //放置完成,输出结果 if ( 8 == ResultStack.size() ) { while ( !ResultStack.empty() ) { pos = ResultStack.top(); cout<<pos.iRow<<"\t"<<pos.iColumn<<endl; ResultStack.pop(); } } x = 0; //这一列放置完成,继续下一列放置 break; } } if ( 8 == x ) //这一列,8行都不能放置皇后,回溯到上一列的下一行 { pos = ResultStack.top(); x = pos.iRow+1; if ( 8 <= x ) { y = y-2; //如果上一列放置的地方已经是最后一列,则无需继续尝试,应该回溯两列,从前两列继续尝试 ResultStack.pop(); pos = ResultStack.top(); x = pos.iRow+1; } else { --y; //回溯到前一列的下一行继续尝试 } ResultStack.pop(); continue; //控制列数,不进行 ++y 操作 } ++y;; } if ( (8 == y) && (ResultStack.size() != 8) ) //如果8行已经尝试完,但是放置不够8行,出错状态,处理下一种可能性 { while ( !ResultStack.empty() ) { ResultStack.pop(); } } cout<<endl; cout<<endl; } } int main() { SolveQueue(); }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。