N皇后问题（C语言）

N皇后问题（C语言）

内容：

   N皇后问题应如何完成。即在N*N的棋盘上摆放N个皇后，使其不在同一列，同一行，也不在同一条斜线上。即可成为该问题的一个解。

步骤：

1.算法分析：

       直观的做法是暴力枚举将N个皇后放置在N*N的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。但是暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。

       显然，每个皇后必须位于不同行和不同列，因此将N个皇后放置在N*N的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。

       回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后，每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并且更新数组中的当前行的皇后列下标。当N个皇后都放置完毕，则找到一个可能的解。当栈到一个可能的解之后，值+1

      由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有N列可以选择，第二个皇后最多有N-1列可以选择，第三个皇后最多有N-2列可以选择，如果考虑到不能在同一条斜线，可能的选择更少，因此所有可能的情况不会超过N!种，遍历这些情况的时间复杂度是O(N!).  

2.概要设计

主要函数及类型：bool()main()

3.程序的流程图

4.源代码（vc++6.0）：

#include
#include
int rank[20];
bool vis[20];
int n,cnt=0;
void dfs(int pos){
	if(pos==n+1){//递归边界条件 
		cnt++;
		return;
	}
	for(int i=1;i<=n;i++){//枚举每行 
		if(vis[i]==false){
			bool flag=true;
			for(int j=1;j 
 5.样例测试
 
5.1  8皇后
 
 
 
 
 
 
 
5.3  11皇后
 
 
     N皇后问题基本完成，所谓回溯，实际上就是一次次尝试，对于失败的进行返回，尝试下一个，相较于暴力法来说更加巧妙。占用内存小。但是代码比较繁琐。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/3970580.html