利用C语言实现N皇后

内容：

在n*n格的国际象棋棋盘上，安放n个皇后，要求，没有一个皇后能够“吃掉”任何其他皇后，即任意两个皇后不能处于同一行、同一列或同一对角线上，这样的格局成为一个解。写出一个程序可以求出所有解。

步骤

1.算法分析

程序中需要的三个重要函数：

        函数check（）用来判断皇后所放的位置（row，column）是否可行；

        函数output（）用来输出可行解，即输出棋盘；

        函数Nqueen（）采用递归算法实现在row行放置皇后。

        对于八皇后问题的求解可采用回溯算法，从上至下依次在每一行放置皇后，进行探索，若在某一行的任意一列放置皇后均不能满足要求，则不能再向下搜索，而进行回溯，回溯至有其他列可以放置皇后的一行，再向下进行搜索，直至搜索至最后一行，找到可行解，输出结果。

2.代码

#include
#include
typedef int boolean;
#define true 1
#define false 0
int num = 0;
int n;
char m[100][100] = { '*' };


boolean Check(int row, int column)
{
	int i, j;
	if (row == 1) return true;
	for (i = 0; i <= row - 2; i++)
	{
		if (m[i][column - 1] == 'Q')return false;
	}	
	
	i = row - 2;
	j = i - (row - column);
	while (i >= 0 && j >= 0)
	{
		if (m[i][j] == 'Q')return false;
		i--;
		j--;
	}
	
	i = row - 2;
	j = row + column - i - 2;
	while (i >= 0 && j <= 7)
	{
		if (m[i][j] == 'Q')return false;
		i--;
		j++;
	}
	return true;
}
void Output()
{
	int i, j;
	num++;
	printf("可行解 %d:n", num);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			printf("%c", m[i][j]);
		}
		printf("n");
	}
}


void NQueen(int row)
{
	int j;
	for (j = 0; j < n; j++)
	{
		m[row - 1][j] = 'Q';
		if (Check(row, j + 1) == true)
		{
			if (row == n)Output();
			else NQueen(row + 1);
		 
		}
		m[row - 1][j] = '*';

	}
}

void main()
{
	printf("100皇后以后无法运算n");
	printf("请输入需要的皇后数；");
	scanf_s("%d", &n);
	if (n <= 100) {
		NQueen(1);
	}
	else
		printf("无法运算！！！！");
}

3.流程图

4.效果图