#include <stdio.h> 
#include <conio.h> 
#include <math.h> 

define QUEENS 4; 

//!記錄解的序號的全局變量。 
int iCount = 0; 

//!記錄皇后在各列上的放置位置的全局數組。 
int Site[QUEENS]; 

//!遞歸求解的函數。 
void Queen(int n); 

//!輸出一個解。 
void Output(); 

//!判斷第n個皇后放上去之后，是否有沖突。 
int IsValid(int n); 

/*----------------------------Main：主函數。----------------------------*/ 
void main() 
{
	Queen(1);
	//!按任意鍵返回。 
	getch(); 
} 

/*-----------------Queen：遞歸放置第n個皇后，程序的核心!----------------*/ 
void Queen(int n) 
{ 
	int i; 
	//!參數n從0開始，等于8時便試出了一個解，將它輸出并回溯。 
	if(n == QUEENS) 
	{ 
		Output(); 
		return; 
	} 
	//!n還沒到8，在第n列的各個行上依次試探。 
	for(i = 1 ; i <= QUEENS ; i++) 
	{ 
		//!在該列的第i行上放置皇后。 
		Site[n] = i; 
		//!如果放置沒有沖突，就開始下一列的試探。 
		if(IsValid(n)) 
			Queen(n + 1); 
	} 
} 

/*------IsValid：判斷第n個皇后放上去之后，是否合法，即是否無沖突。------*/ 
int IsValid(int n) 
{ 
	int i; 
	//!將第n個皇后的位置依次于前面n－1個皇后的位置比較。 
	for(i = 0 ; i < n ; i++) 
	{ 
		//!兩個皇后在同一行上，返回0。 
		if(Site[i] == Site[n]) 
			return 0; 
		//!兩個皇后在同一對角線上，返回0。 
		if(abs(Site[i] - Site[n]) == (n - i)) 
			return 0; 
	} 
	//!沒有沖突，返回1。 
	return 1; 
} 

/*------------Output：輸出一個解，即一種沒有沖突的放置方案。------------*/ 
void Output() 
{ 
	int i; 
	//!輸出序號。 
	printf("No.%-5d" , ++iCount); 
	//!依次輸出各個列上的皇后的位置，即所在的行數
	for(i = 0 ; i < QUEENS ; i++) 
		printf("%d " , Site[i]);
	printf("\n"); 
}