八皇后问题（扩展N皇后问题）

八皇后问题（扩展N皇后问题）

 

#include

#include

#include

#include

int QUEENS;

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

intSite[100]; //记录皇后在各行上的放置位置的全局数组。

void Queen(intn,int QUEENS); //递归求解的函数。递归放置第n个皇后，程序的核心。

void Output(intQUEENS); //输出一个解，即一种没有冲突的放置方案。

int IsValid(intn); //判断第n个皇后放上去之后，是否合法，即是否无冲突。

void main()

{

system("title megamirurutia--递归算法皇后问题 ");

int n,QUEENS;

printf("输入n(代表N皇后问题):");

scanf("%d",&n);

cout<

QUEENS=n;

printf(" 递归算法%d皇后的解法：\n",n);

cout<<" "<<"----------------------------------------"<

Queen(0,QUEENS); //从第0行开始递归试探。

}

void Queen(intn,int QUEENS)

{ int i;

if(n == QUEENS) //参数n从0开始，等于QUEENS时便试出了一个解，将它输出并回溯。

{ Output(QUEENS);

return;

}

for(i = 1 ; i <= QUEENS ; i++) //n还没到QUEENS，在第n行的各个列上依次试探。

{Site[n] = i; //在该行的第i列上放置皇后。

if(IsValid(n)) //如果放置没有冲突，就开始下一行的试探。

Queen(n + 1,QUEENS);

}

}

int IsValid(intn)

{ inti;

for(i = 0 ; i < n ; i++) //将第n个皇后的位置依次于前面n－1个皇后的位置比较。

{if(Site[i] == Site[n]) //两个皇后在同一列上，返回0。

return 0;

if(abs(Site[i] - Site[n]) == (n - i)) //两个皇后在同一对角线上，返回0。

return 0;

}

return 1; //没有冲突，返回1。

}

void Output(int QUEENS)

{

int i;

printf("No.%-5d", ++iCount); //输出序号。

for(i = 0 ; i 依次输出各个行上的皇后的位置，即所在的列数。

printf("%d" , Site[i]);

printf("\n");

}