#include <iostream>
using namespace std;
#define STACK_INIT_SIZE 8
struct point
{
int x;
int y;
};
struct SqStack
{
point * base ;
point * top ;
int stacksize ;
};
// 构造空栈
void InitStack ( SqStack &S )
{
S.base = new point [STACK_INIT_SIZE];
S.top=S.base;
if ( !S.base )
{
cout << "申请空间失败.\n" ;
exit (0) ;
}
S.stacksize = STACK_INIT_SIZE ;
cout << "构造空栈成功.\n";
}
// 销毁栈
void DestroyStack ( SqStack &S )
{
delete ( S.base ) ;
S.stacksize = 0 ;
S.base = NULL ;
S.top = NULL ;
cout << "销毁栈成功.\n";
}
// 置空栈
void ClearStack ( SqStack &S )
{
S.top=S.base;
cout << "置空栈成功.\n";
}
// 栈的长度
int StackLength ( SqStack S )
{
int i;
i=S.top-S.base;
return i;
}
// 插入新元素
void Push ( SqStack &S , point e )
{
S.top->x = e.x;
S.top->y = e.y;
S.top++;
}
// 删除元素
void Pop ( SqStack &S , point &e )
{
S.top-- ;
e.x = S.top->x ;
e.y = S.top->y ;
}
// 输出元素
void StackTraverse ( SqStack S )
{
point *t;
cout << "解决方案如下："
for ( t=S.base ; t!=S.top ; t++ )
{
cout << "( " << t->x+1 << "," << t->y+1 << " )" << endl;
}
}
// 判断该点能否入栈
bool judger ( SqStack S , point e )
{
point *t;
for ( t=S.base ; t!=S.top ; t++ )
{
if ( ( e.x==t->x ) || ( e.y==t->y ) || ( e.x-e.y==t->x-t->y ) || ( e.x+e.y==t->x+t->y ) )
return false ;
}
return true ;
}
// 八皇后解决方案
void solver ( SqStack &S , point e0 )
{
Push(S,e0);
int count=(e0.x+1)%8;
point e;
while ( count != e0.x )
{
e.x = count ;
for ( e.y=0 ; e.y<8 ; e.y++ )
{
if ( judger(S,e) )
{
Push(S,e);
count=(count+1)%8;
break;
}
}
while ( e.y==8 )
{
Pop(S,e);
count=(count+8-1)%8;
for ( e.y=e.y+1 ; e.y<8 ;e.y++ )
{
if ( judger(S,e) )
{
Push(S,e);
count=(count+1)%8;
break;
}
}
}
}
}
int main()
{
point e0 ;
SqStack S;
InitStack(S);
cout << "e0.x=" ;
cin >> e0.x ;;
while ( e0.x>8 || e0.x<1 )
{
cout << "输入错误请重输：" ;
cin >> e0.x ;
}
cout << "e0.y=" ;
cin >> e0.y ;;
while ( e0.y>8 || e0.y<1 )
{
cout << "输入错误请重输：" ;
cin >> e0.y ;
}
e0.x--;
e0.y--;
solver (S,e0);
StackTraverse(S);
return 0;
}
评论0