IT公司面试题收集整理-C相干-八皇后详解

IT公司面试题收集整理---C相关---八皇后详解

八皇后详解，有人可能看不懂上一篇帖子，我又特别整理了一下，尽量弄得简单易懂。注释很详细，基本上都有注释。

先贴一张图，看图看程序比较容易

贴上详细代码

#include<stdio.h>
#define ROW 8//代表列，坐标是x
#define COL 8//代表行，坐标是y
#define NUM 7//八皇后问题，数组下标0-7

#define TRUE 0//真
#define FALSE 1//假

#define YES 1//有皇后
#define NO 0//没有皇后

#define NO_BACK 0//表示不需要回溯
#define BACK 1//表示需要回溯


int a[ROW][COL];//默认值都是0，表示坐标没有皇后，如果改为1，表示这个坐标有皇后
int k=0;//表示第k中情况

//n代表遍历的列的下标，即X值。ROW
int queens(int n)
{
	int i, j;
	//输出八皇后棋盘
	if(n>NUM)
	{
		printf("----------%06d----------\n",++k);
		for(i=0;i<ROW;i++)
		{
			for(j=0;j<COL;j++)
				printf("%s",a[i][j]==1?"○":"●");//为0说明不是皇后，为1说明是皇后
			printf("\n");
		}
		printf("--------------------------\n\n");
		return BACK;//表示正常返回，进行回溯
	}
	//如果没有遍历完全，
	for(j=0;j<COL;j++)//遍历Y值0->COL
	{
		int flag=TRUE;
		//这个循环遍历的是X值，就是Y值不变，X值变化
		for(i=0;i<n;i++)//根据传过来的列的下标X值，ROW值，进行遍历
		{
			//如果【同行】【左斜角，东北西南方向】【右斜角，西北东南方向】出现了皇后的话，则推出此次循环，进行下次循环
			if(a[i][j]==YES||((i+j-n)>=0&&a[i][i+j-n]==YES)||((j+n-i<COL)&&a[i][j+n-i]==YES))
			{
				flag=FALSE;
				break;
			}
		}
		if(flag==TRUE)//如果刚才的循环没有出现这种情况
		{//那么此处放置皇后
			a[n][j]=YES;
			if(queens(n+1)==BACK)
			{//如果下层遍历需要进行回溯
				a[n][j]=NO;//此处不放置皇后
			}else{//如果下层遍历不需要回溯的话，返回
				return NO_BACK;
			}
		}
	}
	//遍历Y值的时候，一直没有出现合适的，出现了flag=FALSE;那么说明下级不能放置皇后，那么进行回溯
	return BACK;
	
}
int main(void)
{
	queens(0);
	return 0;
}

1楼nemo14538分钟前: 写的很好，搜藏了

IT公司面试题收集整理-C相干-八皇后详解

相关推荐