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

《八皇后问题(递归+非递归)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八皇后问题（递归+非递归）Xredmanposted@2009年6月04日21:15in以前博文,442阅读一．问题描述在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。二．解题思路描述一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。首

2、先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。 而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，board[i]表示第i行棋盘摆放的位置为第board[i]列。递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。递归解法 #include

3、#include#includeusingnamespacestd;constintMAX_SIZE=100;enumflag{blank='X',queen=1};charChess[MAX_SIZE][MAX_SIZE];//棋盘图intn;//解决n皇后问题inttotal;//用于计摆放方式voidInit(){//对棋牌进行初始化    for(inti=0;i

4、i][j]=blank;    total=0;//初始时有零中摆放方式}boolJudge(intr,intc){//判断(r,c)位置是否可放置    inti,j;    for(i=r+1;i

5、后    for(i=r+1,j=c+1;(i=0);i++,j--)        if(Chess[i][j]==queen)            returnfalse;//135度斜线上已有一皇后    returntrue;//排除四种情况后，说明(r,c)点可放置皇后}vo

6、idBacktrack(intk,intcnt){//回溯算法主程序        if(k<0

7、

8、cnt==n)//棋牌摆放完毕or以摆满n后    {        if(cnt==n)        {            printf("No.%d:",++total);            for(inti=0;i

9、i][j]);                putchar('');            }                       putchar('');        }    }    else    {        intr=k/n,c=k%n;        if(Judge(r,c))        {//可放置一皇后            Chess[r][c]=queen;            Backtrack(k-1,cnt+1);            Chess[r][

10、c]=blank;        }        Backtrack(k-1,cnt);    }    }intmain(){//此为主函数    timebt1,t2;    longkk;    cout<<"输入皇后个数:";    while(cin>>n)    {            Init();            ftime(&t1