用栈求解n皇后问题

问题描述：
编写一个程序求解n皇后问题，即在m×n的方格棋盘上放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线，下图是八皇后问题的一个解。（1）皇后个数n由用户输入，其值不能超过20，输出所有的解。（2）采用类似于用栈求解迷宫问题的方法。

代码展示：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct
{	int col[MaxSize];				
	int top;						
} StackType;						
void dispasolution(StackType St)   		
{	static int count=0;				
	printf("  第%d个解:",++count);
	for (int i=1;i<=St.top;i++)
		printf("(%d,%d) ",i,St.col[i]);
	printf("\n");
}
bool place(StackType St,int k,int j)
{	int i=1;
	if (k==1) return true;				
	while (i<=k-1)					
	{	if ((St.col[i]==j) || (abs(j-St.col[i])==abs(i-k)))
			return false;			
		i++;
	}
	return true;						
}
void queen(int n)					
{
	int k;
	bool find;
	StackType St;						
	St.top=0;						
	St.top++; St.col[St.top]=0;			
	while (St.top!=0)				
	{	k=St.top;					
		find=false;						
		for (int j=St.col[k]+1;j<=n;j++)
			if (place(St,k,j))			
			{	St.col[St.top]=j;	
				find=true;				
				break;				
			}
		if (find)					
		{	if (k==n)				
				dispasolution(St);
			else						
			{	St.top++;
				St.col[St.top]=0;	
			}
		}
		else						
			St.top--;				
	}
}
int main()
{	int n;							
	printf("皇后问题(n<20) n=");
	scanf("%d",&n);
	if (n>20)
		printf("n值太大\n");
	else
	{	printf(" %d皇后问题求解如下：\n",n);
		queen(n);
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

运行结果：

（截取最后部分）