四、八、N皇后问题(数据结构C语言)

欢迎交流346282925

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<conio.h>

#define Max 20/*定义棋盘的最大值*/

int a[Max];

int show(int S)/*定义输出函数*/

{

int i;

int p,q ;

int b[Max][Max]={0};/*定义并初始化b[][]输出数组*/

static t=1;

for(i=1;i<=S;i++)/*按横列i顺序输出a[i]数组坐标*/

{

b[i][a[i]]=1;

printf("(%d,%d)\t",i,a[i]);

}

printf("\n");

for(p=1;p<=S;p++)/*按棋盘的横列p顺序标明皇后的位置*/

{

for(q=1;q<=S;q++)

{

if(b[p][q]==1) /*在第p行第q列放置一个皇后棋子*/

printf("●");

else

printf("○");

}printf("\n");

}

return 0;

}

int check(int n)/*定义check函数*/

{

int i;

for(i=1;i<n;i++)

{

if((a[i]==a[n])||(a[i]-a[n]==n-i)||(a[i]-a[n]==i-n)) /*检查是否有多个皇后在同一条直线上*/

{

return 0;

}

}

return 1;

}

void check_m(int so)/*定义函数*/

{

int k=1,count=0;

printf("The possible configuration of N queens are:\n");

a[k]=1;

while(k>0)

{

if(k<=so&&a[k]<=so)/*从第k行第一列的位置开始，为后续棋子选择合适位子*/

{

if(check(k)==0)/*若满足函数check()==0，a[k]+1继续循环*/ {

a[k]++;

}

else

{

k++;/*确定第K行的棋子位置，继续寻找第k+1行棋子位置*/ a[k]=1;

}

}

else

{

if(k>so)/*若满足输出数组的要求则输出该数组*/

{

count++;

printf("[%d]: ",count);

show(so);/*调用输出函数show()*/

}

k--;/*棋子位置不符合要求，则退回前一步*/

a[k]++;/*继续试探下一列位置*/

}

}

printf("The count is: %d \n",count);

}

int main()

{

int N;

int d;

system("color 2a");

do

{

printf("********************N皇后问题系统*********************\n\n"); printf(" 1. 四皇后问题 \n"); printf(" 2. 八皇后问题 \n"); printf(" 3. N 皇后问题(N<20) \n"); printf(" 4. 退出 \n"); printf("******************************************************\n"); printf("\n 从数字1-4之间的数选择需要的操作\n\n"); /*提示输入选项*/ printf(" 请输入你要选择的功能选项:__\n");

scanf("%d",&d);

switch(d)

{

case 1:

check_m(4);/*4皇后问题*/

break;

case 2:

check_m(8);/*8皇后问题*/

break;

case 3:

printf("请输入N的值：_");

fflush(stdin);/*清除缓冲*/

scanf("%d",&N);

printf("\n");

if(N>0&&N<20)

{

check_m(N);/*N皇后问题*/

break;

}

else

{

printf("输入错误，请从新输入：");

printf("\n\n");

break;

}

case 4:

exit(0); /*程序结束*/

}

}while(1);

return 0;

}