数据结构课程设计八皇后的求解

#include <stdio.h> #include <conio.h> #include <math.h> #include <stdlib.h> #include <iostream.h> #define QUEENS 8 int iCount = 0; //!记录解的序号的全局变量。 int Site[QUEENS]; //!记录皇后在各列上的放置位置的全局数组。 void Queen(int n); //!递归求解的函数。 void Output();//!输出一个解。 int IsValid(int n); //!判断第n个皇后放上去之后，是否有冲突。 void main() /*----------------------------Main：主函数。----------------------------*/ { int j; printf("title 肖灵杰——递归算法八皇后问题 \n"); printf("\n\t 查 询 菜 单\n"); printf("\n\t*****************************************************"); printf("\n\t* 1--------查看结果 *"); printf("\n\t* 0--------退 出 *"); printf("\n\t******************************************************"); printf("\n\n请选择菜单号(0--1)："); scanf("%d",&j); switch(j) { case 1: printf("\n\t八皇后放置位置的结果(共92种)\n\n"); Queen(0); //!从第0列开始递归试探。 break; case 0: break; default: printf("\n\t\t菜单选择错误，请重新输入!\n"); } } void Queen(int n) /*-----------------Queen：递归放置第n个皇后，程序的核心!----------------*/ { int i; if(n == QUEENS) //!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 { Output(); return; } for(i = 1 ; i <= QUEENS ; i++) //!n还没到8，在第n列的各个行上依次试探。 { Site[n] = i; //!在该列的第i行上放置皇后。 if(IsValid(n)) //!如果放置没有冲突，就开始下一列的试探。 Queen(n + 1); } } int IsValid(int n) /*------IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/ { int i; 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()/*------------Output：输出一个解，即一种没有冲突的放置方案。------------*/ { int i; printf("No.%-5d" , ++iCount); //!输出序号。 for(i = 0 ; i < QUEENS ; i++)//!依次输出各个列上的皇后的位置，即所在的行数。 printf("%d " , Site[i]); printf("\n"); }