开心程序吧

八皇后问题！!- -

                                      

八皇后问题：即在国际象棋的那样棋盘中（八行八列），放八个皇后，要求她们不在同一行或同一列或同一条斜线上。
方法1：
#include "stdafx.h"
#define M 8
char eig[M+1][M+1];
int stack[M+2];
int top=1;

void display()
{

int i,j;
for(i=1;i<=top;i++)
{
printf("(%d,%d)",stack[i],i);
}
printf("\n");
for(i=1;i<=M;i++)
for(j=1;j<=M;j++)
eig[i][j]='o';
for(i=1;i<=top;i++)
eig[stack[i]][i]='*';
for(i=1;i<=M;i++)
{
printf(" ");
for(j=1;j<=M;j++)
printf("%c",eig[i][j]);
printf("\n");

}
}
int put(int x,int y)//根据x,y坐标判断此位置是否可以放置
{
int i,flag=1;
for(i=1;flag&&i<=top;i++)
if(stack[i]==x)
flag=0;
for(i=1;flag&&i<=top;i++)
if ((x-stack[i]==y-i)||(stack[i]-x==y-i))
flag=0;
if(flag)
return 1;
else
return 0;
}

int main(int argc, char* argv[])
{
int l,flag=1;
stack[top]=1;
l=1;
while(flag) // 标志1 循环
{
while(l<=M)
if (put(l,top+1)) //此位置是否可放
break;
else
l++; //不可放，找下一个位置
if(l<=M)
{
stack[++top]=l; //找到可以放置的位置，且在棋盘内部。把此位置存入到栈中

if(top==M) // 栈满了
{
display();//显示

l=stack[top--]+1; //这里是寻找下一种可能的方案。
}
else
l=1; //找到后，接着找++top,l=1;

}
else
{
l=stack[top--]+1; //没找到，回朔
if(top==0&&l>M)
flag=0;
}
}
printf("Hello World!\n");
return 0;
}

方法2
#include

#define available 1 //用来标志该位是否可用，availabel表示可用，unailable表示不可
用

#define unavailable 0

#define true 1

#define false 0

int j,top=-1,flag,i,is_pop,total=0;
　　// top用来保存栈顶指针，flag用来说明该次是否成功下了一个皇后
　　　　//is_pop用来说明是否把栈弹出,total用来保存共有多少种下法
　　　　//i用来保存下一次皇后应下的列

int stack[8],a[15],b[15],c[7];
　　　//stack保存皇后的位置，a,b,c三个数住用来保存该位是否可以下皇后

void init(void);//初始化各位状态，使之可以下皇后

void release (void);//当该列都不能下皇后，则解除上次下皇后试对相关位的锁定

main()

{

　　cout<
　　init();

　　is_pop=false;//初始化

　　for( ; ;)

　　{

　　　do {

　　　　for (j=is_pop? stack[i]+1:0;j<=7;j++)

　　　　　if (a[i+j]&&b[i-j+7]&&c[j])//判断该位是否可用
　　　　　　{//若可用，则栈顶指针上移，在该位存入皇后号

　　　　　　top++;

　　　　　　stack[top]=j;

　　　　　　a[i+j]=b[i-j+7]=c[j]=unavailable;//并把相关位设为不可用

　　　　　　i++;//i指向下一个应填入皇后德列

　　　　　　flag=true;//设标志，说明成功

　　　　　　is_pop=false;

　　　　　　break;//则直接退出循环

　　　　　}

　　　　if (!flag)//若不成功，则释放被锁定的位

　　　　　release();

　　　　flag=false;

　　　　if (stack[0]+1==8&&top==-1)//若第一列也没有位置可以放皇后，

　　　　　　goto END; //则说明没有其他的放法了，则退出

　　　}

　　　while (top!=7);

　　　for (int k=0;k<=7;k++)

　　　　cout

}

- 作者： 刘加开 访问统计：　2005年03月16日, 星期三 17:13 加入博采