eightqueue.cpp

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

int s[9],a[9],b[17],c[17];//如果a[j]=1且b[i+j]=1且c[i-j+9]=1证明(i,j)是安全的;


#include <stdio.h>





int main()
{
	void print(),movequeen(),eightqueen();
	
	eightqueen();
        return 1;
}


void print()
{
	int k;
	printf("\n行号：    1    2    3    4    5    6    7    8\n");
	printf("列号：");
	for(k=1;k<=8;k++)
	{
		printf("%5d",s[k]);
		
	}
}

void movequeen(int i,int j)//移开(i,j)点的queue，使(i,j)安全；
{
	a[j]=1;
	b[i+j]=1;
	c[i-j+9]=1;
}



void eightqueen()
{
	int i,j;
        
        for(i=2;i<=16;i++)
	{
		if(i>=2&&i<=9)a[i-1]=1;
		b[i]=1;
		c[i]=1;
	}//清棋盘；
	

        i=1;j=1;
	
		
		
	while(i>=1)//不符合要求就退栈，所以当i=0时终止循环；
	{
		while(j<=8)//在当前行i上寻找安全位置；
		{
			if(a[j]&&b[i+j]&&c[i-j+9])break;
			j++;
		}
		if(j<=8)//找到安全位置(i,j);
		{
			a[j]=0;
			b[i+j]=0;
			c[i-j+9]=0;//标志(i,j)点不安全;
			s[i]=j;//皇后位置j入栈；
			
            
			
			if(i==8)//i=8时,说明已经找到一个解,输出解;
			{
				print();
				getchar();//等待字符输入,可以是结果分行显示(一共有92组结果);
				movequeen(i,j);
				i=i-1;j=s[i];//退栈，回溯到上一个皇后；
				movequeen(i,j);
				j++;//修改栈顶皇后的位置；
			}
			else
			{
				i++;j=1;//准备放置下一个皇后；
			}
		}
		else
		{
			i--;//退栈；
			if(i>=1)//栈不空，移去皇后；
			{
				j=s[i];
				movequeen(i,j);
				j++;
			}
		}
	}
}