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

zhengbei2 贡献于2013-10-04

作者 X  创建于2010-10-18 02:35:00   修改者X  修改于2010-10-18 02:36:00字数2614

文档摘要:阅读一.问题描述在8×8格的国际象棋棋盘上放置八个皇后,使得任意两个皇后不能互相攻击,即任何行、列或对角线(与水平轴夹角为45°或135°的斜线)上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。二.解题思路描述一个正确的解应当是每一列,每一行,每一条斜线上均只有一个皇后。对于递归算法,本人才有模拟的方式进行,而且,我觉得开辟一个二维数组更显而易见。
关键词:

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

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档