八皇后问题（递归+非递归）

Xredman posted @ Jun 04, 2009 10:15:47 AM in 以前博文 , 7978 阅读

一．问题描述

在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线（与水平轴夹角为45°或135°的斜线）上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。请用递归与非递归两种方法写出求出八皇后问题的算法。

二．解题思路描述

一个正确的解应当是每一列，每一行，每一条斜线上均只有一个皇后。

对于递归算法，本人才有模拟的方式进行，而且，我觉得开辟一个二维数组更显而易见。首先，从空棋盘开始摆放，保证第m行m个皇后互不攻击，然后摆放第m+1个皇后。当然对于第m+1个皇后可能有多种摆放方法，由此，我必须一一枚举，采用回溯策略是可行且合乎逻辑的。

而对于非递归算法，我只是借助于书本上一个递归改为非递归的框架，依次搭建而已。

在此过程中，我采用一维数组，一位对于八皇后问题，每一行不可能存在二个及二个以上的皇后，board[i]表示第i行棋盘摆放的位置为第board[i]列。递归方法借助于系统提供的栈，而我非递归算法的实现，仅仅是自己构造一个栈而已。

递归解法

#include <iostream>
#include <cstdio>
#include <sys/timeb.h>
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 <n) && (j >= 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<<"计算"<<n<<"后问题总共可有"<<total<<"种摆法!"<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}

非递归解法

#include <iostream>
#include <sys/timeb.h>
#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."<<sum<<endl;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(board[i] == j)
cout<<"Q ";
else
cout<<"X ";
cout<<endl;
}
cout<<endl;
}

bool canPut(int k)
{
for(int i = 1; i < k; i++)
if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])
return false;//1.是否在同一斜线;2.是否位于同一列
return true;
}

void Backtrack()
{
board[1] = 0;
int k = 1;
while(k > 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<<"总共排列方式为:"<<sum<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}