八皇后问题(递归+非递归).doc

八皇后问题（递归+非递归）Xredman posted 2009年6月04日 21:15 in 以前博文 , 442 阅读 一问题描述在88格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45或135的斜线）上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。二解题思路描述一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。首先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，boardi表示第i行棋盘摆放的位置为第boardi列。递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。 递归解法#include #include #include using namespace std;const int MAX_SIZE = 100;enum flag blank =X,queen = 1;char ChessMAX_SIZEMAX_SIZE;/棋盘图int n;/解决n皇后问题int total;/用于计摆放方式void Init()/对棋牌进行初始化 for(int i = 0; i n; i+) for(int j = 0; j n; j+) Chessij = blank; total = 0;/初始时有零中摆放方式bool Judge(int r,int c)/判断(r,c)位置是否可放置 int i,j; for(i = r + 1; i n; i+) if(Chessic = queen) return false;/说明c列上已有一皇后 for(i = c + 1; i n; i+) if(Chessri = queen) return false;/说明r行上已有一皇后 for(i = r + 1, j = c + 1; (i n) & (j n); i+, j+) if(Chessij = queen) return false;/45度斜线上已有一皇后 for(i = r + 1, j = c - 1; (i = 0); i+, j-) if(Chessij = queen) return false;/135度斜线上已有一皇后 return true;/排除四种情况后，说明(r,c)点可放置皇后void Backtrack(int k,int cnt)/回溯算法主程序 if(k 0 | cnt = n)/棋牌摆放完毕 or 以摆满n后 if(cnt = n) printf(No.%d:n,+total); for(int i = 0; i n; i+) for(int j = 0; j n; j+) printf( %c ,Chessij); putchar(n); putchar(n); else int r = k / n, c = k % n; if(Judge(r,c) /可放置一皇后 Chessrc = queen; Backtrack(k-1,cnt+1); Chessrc = blank; Backtrack(k-1,cnt); int main()/此为主函数 timeb t1,t2; long kk; coutn) Init(); ftime(&t1); Backtrack(n*n-1,0); ftime(&t2); cout计算n后问题总共可有total种摆法!endl; kk = (t2.time-t1.time)*1000 + litm; cout本次回溯耗时:kk毫秒endl; system(PAUSE); cout输入皇后个数:; return 0;非递归解法#include #include #define N 100using namespace std;int boardN;int n,sum;void init() for(int i = 1; i = n; i+) boardi = 0;void display() int i,j; coutNo.sumendl; for(i = 1; i = n; i+) for(j = 1; j = n; j+) if(boardi = j) coutQ ; else coutX ; coutendl; coutendl;bool canPut(int k) for(int i = 1; i 0) boardk+; while(boardk = n) & !(canPut(k) boardk += 1; if(boardk = n) if(k = n) sum+; display(); else k+; boardk = 0; else k-; int main() timeb t1,t2; long kk; coutn) init(); sum = 0; ftime(&t1); Backtrack(); ftime(&t2); cout总共排列方式为: