n皇后问题(C语言实现)_用栈求解n皇后问题c语言

算法核心：

（1）递归：从第一行开始，不断地递归处理下一行，直到处理到n+1行就停止。
（2）回溯：若该行的任意位置均不能满足条件，则进行回退，退到上一行的下一个状态。

算法步骤：

对于每一行而言：

1. 先判断该行是不是第n行，如果是，则说明现在栈数组g[]中保存着一个可行的解法，进行输出。
2. 若不是，则从该行的下一个状态开始(每一行的状态为0,1,2…n-1，初始状态为0)，
   （1） 若该点满足，则存储该点的位置，并进行下一行的递归，同时，在每一个递归的后面要进行出栈(因为输出不止一个解法)；
   （2） 若不满足，则继续取下一个状态。

实现代码

//定义数据结构
typedef struct{
	int m;
	int n;
}Dian; //m是行，n是列
Dian g[20];  //模拟一个栈，栈用来存储现在满足条件的点
int top=-1,k=1;
1
2
3
4
5
6
7

//出栈和入栈操作
void Push(Dian a){
	top++;
	g[top]=a;
}

Dian Pop(){
	Dian t;
	t=g[top];
	top--;
	return t;
}
1
2
3
4
5
6
7
8
9
10
11
12

//输入数据
int Input(){
	int n;
	printf("请输入n值:");
	scanf("%d",&n);
	return n;
}
1
2
3
4
5
6
7

//判断该点是否满足要求
bool Can(Dian a){
	int i;
	for(i=0;i<=top;i++)
	{
		if(a.n==g[i].n)  //同一列不满足
			return false;
		if(abs(a.m-g[i].m)==abs(a.n-g[i].n)) 
			return false;	//同一条斜线也不满足
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

//格式化输出
void Output(int n){
	int graph[20][20]={0},i,j;
	printf("第%d种摆放为:\n",k++);
	for(i=0;i<=top;i++)
		graph[g[i].m][g[i].n]=1;
	for(i=0;i<n;i++)
	{ 
		for(j=0;j<n;j++)
			printf("%d ",graph[i][j]);
		printf("\n"); 
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//n皇后递归函数
void NQueen(int n,int m){
	int i;
	Dian t;
	if(m==n)  //当处理完行之后，进行输出
	{
		Output(n);
		return;
	}
	else
	{
		for(i=0;i<n;i++)  //依次尝试每一种状态
		{
			t.m=m;
			t.n=i;
			if(Can(t))  //满足条件则入栈
			{
				Push(t);
				NQueen(n,m+1); //处理下一行
				Pop(); //寻找其他可能
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//主函数
int main(){
	int n;
	n=Input();
	NQueen(n,0);
	return 0;
}
1
2
3
4
5
6
7

运行结果