nqueen.cpp

有关一个N皇后的问题。用户只要改变开始宏定义是的 QUEENS的值就可以验证 皇后的具体分布情况；如 8 皇后 则会输出具体的92中放置方法；

// nqueen.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h> 
#include <conio.h> 
#include <math.h> 
#include<stdlib.h>
#include "iostream"
#define QUEENS 8 

//!记录解的序号的全局变量。 
int iCount = 0; 

//!记录皇后在各列上的放置位置的全局数组。 
int Site[QUEENS]; 

//!递归求解的函数。 
void Queen(int n); 

//!输出一个解。 
void Output(); 

//!判断第n个皇后放上去之后，是否有冲突。 
int IsValid(int n); 

/*----------------------------Main：主函数。----------------------------*/ 
void main() 
{ 
//!从第0列开始递归试探。 
Queen(0); 

//!按任意键返回。 
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"); 
}