学步园

/*
* 使用回溯法解决n皇后问题
*/
#include <stdio.h>
#include <math.h>

#define NUM 8 //皇后的数目
int chess[NUM]; //依次表示每个皇后所在的列数
int count = 0;//总的解数 

//表示能否在第i行value列放置皇后，行数是从0开始
bool canPlaced(int i,int value)
{
	//第0行的皇后可以任意摆放
	if (i==0)
	{
		return 1;
	}
	//依次检测之前的皇后，是否冲突
	for (int j=0;j<i;j++)
	{
		//列冲突
		if (chess[j]==value)
		{
			return false;
		}

		//对角线冲突
		if (abs(i-j)==abs(chess[j]-value))
		{
			return false;
		}
	}
	return true;
}

//打印出结果
void showResult()
{
	int k;
	for (int j=0;j<NUM;j++)
	{
		for (k=0;k<chess[j];k++)
		{
			printf("*");
		}

		printf("Q");

		for (k=k+1;k<NUM;k++)
		{
			printf("*");
		}
		printf("\n");
	}
	printf("\n");
}

//采用递归回溯法
void backTrack(int t)
{
	int i;
	//皇后数目超出棋盘，摆放完毕
	if (t>=NUM)
	{
		printf("\n");
		showResult();
		count++;
		return;
	}
	else
	{
		//依次检测能否摆放
		for (i=0;i<NUM;i++)
		{
			if (canPlaced(t,i))
			{
				chess[t] = i;
				//若能够摆放，则摆放下一个
				backTrack(t+1);
			}
		}
	}
}


int main()
{
	backTrack(0);
	showResult();
	printf("%d皇后问题共有%d个解\n",NUM,count);
	return 0;
}