流离之人追逐幻影

用户名：pwj666

访问量：60259

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13962
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：188

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

n皇后（非递归回溯）-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-07-16 23:25:30 浏览：828　|　评论：0　

一般来说递归的效率比较差，下面重点讨论一下该问题的非递归实现。
```
非递归方法的一个重要问题是何时回溯及如何回溯的问题。
```
下面写出同一个思路的不同表达
一：
```
1.初始化棋盘，即建立一个一维数组，储存一个初值（不是0到N-1就行）；
```
```
2.寻找N皇后：
	a.判断皇后是否可以放置...而要想让皇后可以被放置，就必须满足皇后与皇后之间没有行冲突，列冲突，对角线冲突。那么首先想到的思路就是将你放置在该行该列的皇后与前面已经放置的皇后进行冲突检测，只要有一个冲突了，则该皇后就不能被放置。
	b.回溯...如果该皇后不能在当前行当前列放置，则应该将该皇后往后移，直到当前行的所有列都检测完了，还不能放置皇后的话，就应该回溯到上一行，将上一行的皇后往后移，如果后移的皇后不能放置的话，继续回溯，直到可以被放置。一旦放置成功就顺推，直到最后一行。
	c.结束...当顺推到最后一行时，回溯从最后一行开始，逐步将每一行的所有列都进行检测，直到回溯到第一行，则说明已经找到所有解。
```
二：
```
1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
```
```
2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
```
```
3) 在当前位置上满足条件的情形：

在当前位置放一个皇后，若当前行是最后一行，记录一个解；

若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；

若当前行是最后一行，当前列不是最后一列，当前列设为下一列；

若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；

以上返回到第2步
```
```
4) 在当前位置上不满足条件的情形：

若当前列不是最后一列，当前列设为下一列，返回到第2步;

若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 
```
图示：
![](/image_editor_upload/20190716112434_95691.jpg)
代码：
```
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
#define Queen 8
#define CHUZHI -1
 
int a[Queen];
void init(){//第一步完成棋盘的初始化
	int *p;
	for(p=a;p<a+Queen;++p)
		*p=CHUZHI;
}
 
int valid(int row,int col){//判断皇后是否可以放置
	for(int i=0;i<=row;i++) //检测前row行，不必每次检测Queen行
		if(a[i]==col||abs(a[i]-col)==abs(row-i))//判断行冲突和列冲突
			return 0;
	return 1;
}
 
void print(){ //规范打印出N皇后位置
	for(int i=0;i<Queen;i++){
		for(int j=0;j<Queen;j++)
			if(a[i]!=j)
				printf("%c ",'.');
			else
				printf("%c ",'#');
		printf("\n");
	}
	for(int i=0;i<Queen;i++)
		printf("%d ",a[i]);
	printf("\n");
	printf("--------------------------------------\n");
	
}
 
void queen(){//寻找N皇后
	int n=0;
	int i=0,j=0;
	while(i<Queen){
		while(j<Queen){
			if(valid(i,j)){ //能放置皇后，进入if
				a[i]=j; // 储存第I行的第j列位置的皇后（每行有且只有一个皇后）
				j=0;  //将j置零，以便于下一行从第一列检测
				break;//这一行找到皇后，立马跳出第二层循环，到下一行检测
			}
			else//不能放置皇后,则将这一行的皇后往后移一列
				++j;
		}
		if(a[i]==CHUZHI){ //如果这一行没有位置能放置皇后的话，进入If
			if(i==0)   //如果被回溯到第一行，说明已经找到了所有的解，
				break;//跳出循环，结束程序
			else{
			--i;  //否则，回溯到上一行
			j=a[i]+1;//将上一行皇后的位置往后移
			a[i]=CHUZHI;//原来位置置为初值
			continue;//跳过下面代码部分，直接进入下一次循环
			}
		}
		if(i==Queen-1){
			printf("找到第%d组解\n",++n); //已经找到一组解
			print();//还没完，我们要找到所有的解，所以要把这一行的每一列都遍历
			j=a[i]+1;//这一行的皇后位置往后移
			a[i]=CHUZHI;//原来位置置为初值
			continue;//跳过下面代码部分，直接进入下一次循环
		}
		++i;
	}
		
}
int main(void){
	init();
	queen();
	system("pause");
	return 0;
}
```
![](/image_editor_upload/20190716113101_63445.png)

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

剪格子（C语言代码）

小九九（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

n皇后（非递归回溯）-----每日PAT

评论区

精彩推荐

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

大小写转换（C语言代码）

Pascal三角（C语言代码）格式错误

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

输入输出格式练习（C语言代码）

简单的a+b （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

剪格子 （C语言代码）

小九九 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

n皇后（非递归回溯）-----每日PAT

评论区

精彩推荐

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

大小写转换 （C语言代码）

Pascal三角 （C语言代码）格式错误

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

输入输出格式练习 （C语言代码）

简单的a+b （C语言代码）

剪格子（C语言代码）

小九九（C语言代码）

C二级辅导-分段函数（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

　　评论区

大小写转换（C语言代码）

Pascal三角（C语言代码）格式错误

【亲和数】（C语言代码）

输入输出格式练习（C语言代码）