queens.cpp

scheme实现的把皇后问题解法。输出为矩阵形式

//*****************************************************************************/**************************
//程序名称：程序设计语言大作业--Scheme语言的八皇后问题
//程序内容：八皇后
//作者：张宏基 051221136
//日期：2008年4月1号
//*******************************************************************************************************
#include <stdio.h>
#include <math.h>

int i = 0;                 //for循环时使用；
static int k = 1;            //用于显示这是第几种解；
int unok=0;              //用来判断有没有发生冲突;
int t;                    //用于递归时传入参数,以确定在哪一行找可以放置皇后的列;

struct location{
		int yrow;
		int xrow;
}a[] ={{1,1},{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{1,8}};             //数组的初始化；

int check(struct location num1,struct location num2)                 //判断冲突;
{
	if(num1.yrow==num2.yrow)                                //在同一列上；
		return 1;
	else if(fabs(num1.xrow-num2.xrow) == fabs(num1.yrow-num2.yrow))  //在同一斜线上;
		return 1;
	else                                                             //否则不冲突；
		return 0;
}

void putfmember(int i)                                               //根据i的值输出一行;
{
	switch (i)
	{case 1:printf("(Q * * * * * * *)\n");break;
 	 case 2:printf("(* Q * * * * * *)\n");break;
	 case 3:printf("(* * Q * * * * *)\n");break;
	 case 4:printf("(* * * Q * * * *)\n");break;
	 case 5:printf("(* * * * Q * * *)\n");break;
	 case 6:printf("(* * * * * Q * *)\n");break;
	 case 7:printf("(* * * * * * Q *)\n");break;
	 case 8:printf("(* * * * * * * Q)\n");break;
	}
}

void showtop(int k)                                              //输出每一种结果前的标签;
{
	printf("Number.%d\n",k);
}

void outputf(struct location a[])                               //输出整体结果；
{
	showtop(k);
	k++;
	for(i=0 ; i < 8; i++)
		putfmember(a[i].yrow);                                       //根据a[i].yrow输出一行;
	printf("\n");                                                    //一种结果输出以后与下一种之间空一行；
}

void queens_equ(struct location a[],int a_num)
{
	if(a_num < 8)
	{
		for(int j=1;j<=8;j++)                                        //在该行中依次判断该行哪一列能放上一个皇后;
		{
			a[a_num].yrow = j;
			unok = 0;
			for(int m = a_num-1;m >=0;m--)
				unok +=check(a[a_num],a[m]);                        //与该行已经放好的前几行判断有没有冲突;
			if(!unok)
			{
				t=a_num+1;
				queens_equ(a,t);                                     //该行放好后,递归调用后面的几行;
			}
		}
	}
	else
	{
		outputf(a);                                              //8行都已经放好,即得到一种正确的结果,于是输出它;
	}
}

void queens()                               //main函数直接调用它，从而得到结果；
{
	queens_equ(a,0);
}

void main()                                  //程序入口；
{
	queens();
}