N皇后问题求解算法

大学时C＋＋程序设计课程的作业题目。呵呵！

N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。

下面程序利用堆栈数据结构，使用回溯法求出所有可行解。

/*
Copyright (c) 2006, Computing Center of IHEP, Beijing, China
[e-mail]
链式结构堆栈类的类模板实现及用堆栈类求解N皇后问题　
编写：089906－36@NUAA　刘爱贵　　
*/

#include "iostream.h"
#include "math.h"
#define TRUE 1
#define FALSE 0
#define ERROR -1
typedef int Status;
//用模板实现的链式结构堆栈类
template <class T>
class stack{
private:
struct link{
T data; //结点数据域
link *next; //下一结点指针
link(T Data,link* Next){//结构体构造函数
data=Data;
next=Next;
}
}*head; //堆栈顶指针
public:
stack(); //构造函数(初始化栈)
~stack(); //析构函数(销毁栈)
void push(T Data); //压栈操作
T gettop()const; //取栈顶元素
T pop(); //出栈操作
T getvalue(int index); //返回栈底开始第INDEX个栈中值
void traverse(int n); //遍历栈 N个数换行
int empty(); //判断栈是否为空，1是，0非
int sizeofstack(); //返回栈的大小
void clear(); //清空栈
};
//N皇后类
class queen{
private:
stack<int>* qStack; // 求解中所用数据结构:堆栈
public:
queen(); //构造函数
~queen(); //析构函数
Status Place(int k); // 判断当前行K列是否可以可以放置皇后
Status Queen(int n); //求出所有解
};
//类模板成员函数的实现
template<class T> stack<T>::stack()//构造函数
{
head=0;
}
template<class T> stack<T>::~stack()//析构函数
{
link* cursor=head;
while(head)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
template<class T>void stack<T>::push(T Data)//压栈操作
{
head=new link(Data,head);
}
template<class T>T stack<T>::gettop()const//取栈顶元素
{
return head->data;
}
template<class T>T stack<T>::pop()//出栈操作
{
if(head==0)return 0;
T result=head->data;
link* oldhead=head;
head=head->next;
delete oldhead;
return result;
}
template <class T>T stack<T>::getvalue(int index)//返回栈底开始第INDEX个栈中值
{
link *cursor=head;
int i=1;
int stacklen=sizeofstack();
if(index<=0||index>stacklen)return 0;
while(i<=(stacklen-index))
{
cursor=cursor->next;
i++;
}
return cursor->data;
}
template <class T> void stack<T>::traverse(int n)//遍历栈
{
link * cursor=head;
int iEnterSign=1;//换行标识
while(cursor)
{
cout<<cursor->data<<" ";
if(iEnterSign%n==0)cout<<endl;
cursor=cursor->next;
iEnterSign++;
}
if((iEnterSign-1)%n!=0)cout<<endl;
}
template <class T>int stack<T>::empty() //判断栈是否为空，1是，0非
{
return head==0?1:0;
}
template <class T>int stack<T>::sizeofstack() //返回栈的大小
{
int size=0;
link *cursor=head;
while(cursor)
{
cursor=cursor->next;
size++;
}
return size;
}
template<class T> void stack<T>:: clear() //清空栈
{
link *cursor=head;
while(cursor&&cursor->next)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
//N皇后类成员函数的实现
queen::queen() //构造函数
{
qStack=new(stack<int>);
}
queen:: ~queen() //析构函数
{
delete qStack;
}
Status queen::Place(int k) // 判断当前行K列是否可以可以放置皇后
{
int i=1,j,e;
j=qStack->sizeofstack()+1;
while(i<j)
{
e=qStack->getvalue(i);
if((k==e)||(abs(i-j)==abs(e-k))) return FALSE;
i++;
}
return TRUE;
}
Status queen::Queen(int n) //回溯法求出N皇后所有解
{
int k,m=0,e;
if(n<4)return ERROR;
k=1;
while(!qStack->empty()||k<=n)
{
while((k<=n)&&(!Place(k)))k++;
if(k<=n)
{
qStack->push(k);
if(qStack->sizeofstack()==n)
{
m++;
qStack->traverse(n);
e=qStack->pop();
k=e;
k++;
}
else k=1;
}
else
{
e=qStack->pop();
k=e;
k++;
}
}
cout<<"There are "<<m<<" ways"<<endl;
return TRUE;
}
void main(void)//程序入口函数
{
//堆栈操作示例
cout<<"堆栈操作示例："<<endl;
stack<int> *sample=new(stack<int>);
sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
int i;

for(i=1;i<=10;++i)sample->push(i);
sample->traverse(10);
sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
cout<<"Size of the Stack is:"<<sample->sizeofstack()<<endl;
cout<<"Top of stack is:"<<sample->gettop()<<endl;

for(i=1;i<=5;++i)sample->pop();
sample->traverse(10);
sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
cout<<"Size of the Stack is:"<<sample->sizeofstack()<<endl;
cout<<"Top of stack is:"<<sample->gettop()<<endl;
//用堆栈回溯实现的八皇后问题求解
cout<<"八皇后问题解:"<<endl;
queen eightqueen;
eightqueen.Queen(8);
cout<<"链式结构堆栈类的类模板实现及用堆栈类求解八皇后问题"<<endl;
cout<<"编写：089906－36@NUAA　Aigui.LIU 2002年10月12日完成";
cin.get();
}//程序结束