C 언어 N 황후 문제.

1445 단어
/*
*  author :wxg
*/

#include<stdio.h>
#include<string.h>
#define N 8
/*
* flag=1     ,flag=-1       
*/
int isOK(int a[N][N],int n,int x,int y){
	int flag=1;
	int i,j;
	for(i=0;i<n;i++){
		if(a[x][i]==1||a[i][y]==1)
			flag=-1;
	}
	i=x;j=y;
	while(i<n-1&&j>0)	{
		if(a[++i][--j]==1) flag=-1;
	}
	i=x;j=y;
	while(i>0&&j<n-1){
		if(a[--i][++j]==1) flag=-1;
	}
	i=x;j=y;
	while(i>0&&j>0){
		if(a[--i][--j]==1) flag=-1;
	}
	i=x;j=y;
	while(i<n-1&&j<n-1){
		if(a[++i][++j]==1) flag=-1;
	}
	return flag;
}

void searchQueen(int a[N][N],int n){
	int i=0,j=0,flag=-1;
	int stack[N],top=0;        //                 (    :  ) 
	while(i<N){
		for(j=0;j<N;){
			flag=isOK(a,N,i,j);
			if(flag==1){
				stack[top]=j;
				top++;
				a[i][j]=1;j=0;i++;
				if(i==N)break;           //     N          ,      
			}
			else if((flag==-1)&&(j==N-1)){ //         ,    , 
				top--;
				int tmp=stack[top];
				j=tmp+1;
				i--;
				a[i][tmp]=0;
				while((top>=0)&&(tmp==N-1)){    //          ,     
					top--;tmp=stack[top];
					i--;
					a[i][tmp]=0;
					j=tmp+1;
				}
				
			}
			else j++;
		}

	}
}
int main(){
	int a[N][N];
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			a[i][j]=0;
	searchQueen(a,N);
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(a[i][j]==1)
				printf("i=%d  j=%d
",i,j); return 0; }

좋은 웹페이지 즐겨찾기