1460题-[蓝桥杯][基础练习VIP]2n皇后问题-题解(C语言描述)--------详细带图解释皇后系列问题，适合新人

每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
通知：目前比赛栏的权限已经完全开放，支持老师、个人随时抽题创建比赛，需达到P2等级
比赛名称建议包含学校/组织名称，具有辨识度。不友好名称可能会被屏蔽，请大家知晓！
肺炎疫情，在家就是对社会最大的贡献！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
比赛创建功能已经完全开放，需要达到P2等级，写博客要达到P2等级
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

李华

私信TA

用户名：2645479600

访问量：1051

签　名：

qq:2645479600，欢迎共同探讨

等　　级
排　　名	1080
经　　验	1665
参赛次数	1
文章发表	17
年　　龄	0
在职情况	学生
学　　校	广大华软
专　　业	电子信息工程

　　自我简介：

C/C++程序设计蓝桥杯新人，欢迎探讨

TA的其他文章

1435题-[蓝桥杯][历届试题]国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：89

1440题-[蓝桥杯][2013年第四届真题]带分数-题解(C语言描述) ------------纯C语言,,思路非常简单
浏览：85

1873题-[蓝桥杯][2017年第八届真题]合根植物-题解(C语言描述)-----C语言
浏览：21

你可能喜欢

题解1036：C语言程序设计教程（第三版）课后习题9.1 （C语言描述）
浏览：492

题解1161：【回文数(二)】（C语言描述）
浏览：1201

题解1066：2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言描述）
浏览：343

题解1016：C语言程序设计教程（第三版）课后习题6.6 （C++描述）
浏览：485

题解1668：printf基础练习2 （C语言描述）
浏览：2771

优质题解 1460题-[蓝桥杯][基础练习VIP]2n皇后问题-题解(C语言描述)--------详细带图解释皇后系列问题，适合新人

　　作者: 李华　　　　发表时间：2020-03-03 21:54:09 浏览：232　|　评论：4　

原题链接：[蓝桥杯][基础练习VIP]2n皇后问题

本题与经典递归问题八皇后类似，只需要先放置完白皇后再放置黑皇后即可
解题思路:
1.先放置白皇后，再考虑第二个皇后
2.那么白皇后要怎么放呢，皇后不能同行同列，不能在同一条左斜线和右斜线。我们的递归函数是从第一行递归到最后一行，所以我们不需要标记行，那么我们拿三个数组分别标记列和两个斜线的占用情况。列的标记很容易理解，那么怎么标记左斜线和右斜线的占用情况呢？我们以左斜线为例子，请看图
![](/image_editor_upload/20200303092207_74969.png)
我们很容易可以发现黄线路径的每个格子行和列之和是相等的，比如（1,4）（2,3）的和都是5。同理观察一下红线，可以发现红线路径的格子行和列之和都为9。可以知道，左斜线的规律就是同一条斜线的格子，行列之和是相等的！

接下来请看右斜线：
![](/image_editor_upload/20200303092832_86855.png)
同样可以发现红线路径上的每个格子行和列之差是相等的，比如(1,1)(2,2)的差都是0。同理观察一下黄线，可以发现行列之差都是5。但是这里有一个坑点，请观察一下绿线，绿线路径的点行和列之差是-5，是一个负数，我们开数组的时候，下标不能为负数，这里我们只需要每次计算行列之差的时候，结果都给他加上一个n即可，下标就不可能出现负数了。比如（1,6）的差是-5，我们只需要在数组为（-5+8）=3的位置标记上就可以了。当然你不加n也可以，你可以加一个很大的数字也是同理（比如1000）的，但是这样的话你数组要开大一点。
##### 具体的标记数组命名可以看代码第四行，第五行。
3.我们先放白皇后，白皇后要考虑的总共有4个条件，列不能被占用，左斜线不能被白皇后占用，右斜线不能被占用，准备下的格子不能为‘0’。（行不能被占用不需要考虑，因为我们的递归函数是从第一行放到最后一行，不可能出现行重复）
##### 具体的判断代码可以看代码第三十六行
4.当白皇后完成了1~n行放置的一种情况，我们就可以开始尝试这种情况能不能完美放置黑皇后了。
##### 转入判断黑皇后的代码在第三十一行，子函数的参数是行数
5.接下来我们看判断黑皇后能不能完美放置。黑皇后要考虑的条件比白皇后条件多一个，有5个。首先列不能被同样的黑皇后占用，左斜线不能被占用，右斜线不能被占用，准备下的格子不能为‘0’，准备下的格子不能已经被白皇后占用。
##### 具体的判断代码可以看代码第十五行
6.当黑皇后考虑完了最后一行即已经完成了一种情况，让ans加一。

---
注意事项：当一种情况尝试到尽头也不能找到完美放置方法是要记得回溯，否则下次再想尝试这个格子就不能尝试了。所谓回溯，就是取消标记，避免下次递归无法尝试这个点。具体代码可以看第四十三行到第四十六行
**如果有不对的地方，请大佬指出。有疑问可以私信或者评论，谢谢！**
```c
#include <stdio.h>
int n,ans;
int a[10][10];	//棋盘
int vis_white_lie[10],vis_white_left[20],vis_white_right[20],white[10][10];	//用于标记白皇后的情况 
int vis_black_lie[10],vis_black_left[20],vis_black_right[20];
void dfs_black(int x)
{
	if(x==n+1)
	{
		ans++;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis_black_lie[i]&&!vis_black_left[x+i]&&!vis_black_right[x-i+n]&&a[x][i]!=0&&white[x][i]==0)//列,左斜线,右斜线未占用，格子不为0，不被黑皇后占用 
		{
			vis_black_lie[i]=1;
			vis_black_left[x+i]=1;
			vis_black_right[x-i+n]=1;
			dfs_black(x+1);
			vis_black_lie[i]=0;	//回溯 
			vis_black_left[x+i]=0;
			vis_black_right[x-i+n]=0;	
		}
	}
}
void dfs_white(int x)	//先考虑白皇后,再考虑黑皇后，每完成一种情况就dfs_black递归找黑皇后的情况 
{
	if(x==n+1)	//白皇后已经完成了n行,准备进入第n+1行就算白皇后已经放完了
	{
		dfs_black(1);	//递归调用黑皇后 
		return;
	}
	for(int i=1;i<=n;i++)	//依次尝试1~n列
	{
		if(!vis_white_lie[i]&&!vis_white_left[x+i]&&!vis_white_right[x-i+n]&&a[x][i]!=0)	//如果列,左斜线,右斜线都没有被占用，并且格子不为0 
		{
			vis_white_lie[i]=1;
			vis_white_left[x+i]=1;	//左斜线x,y坐标相加相等
			vis_white_right[x-i+n]=1;	//右斜线,x,y坐标相减相等
			white[x][i]=1;	//将白皇后占的格子标记上,用于禁止黑皇后同时占用
			dfs_white(x+1);	//然后尝试第x+1行
			vis_white_lie[i]=0;
			vis_white_left[x+i]=0;
			vis_white_right[x-i+n]=0;
			white[x][i]=0;
		} 
	} 
} 
//从main函数看起 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dfs_white(1);	//参数代表当前考虑的行
	printf("%d",ans);
	return 0;
}
```

0.0分

15 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

恋爱的犀牛

详细

2020-03-26 02:53:26 | |

parkt90

会不会在递归里面有死循环，比如输入的·矩阵很多点不能选，递归怎么跳出来？

2020-03-18 23:24:54 | |

小白

写的很详细。b(￣▽￣)d

2020-03-16 21:46:25 | |

为什么40行要写成x-i+n？

2020-03-03 22:09:58 | |

题解1053：2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言描述）浏览：317

题解1776：C语言程序设计教程（第三版）课后习题12.6 （C语言描述）浏览：529

题解1159：【偶数求和】（C++描述）浏览：515

题解1014：C语言程序设计教程（第三版）课后习题6.4 （C语言描述）浏览：400

题解1048：C语言程序设计教程（第三版）课后习题10.7 （C语言描述）浏览：383

题解1470：时间转换（Java描述）浏览：367

题解1536：最长单词（C语言描述）浏览：606

题解1012：C语言程序设计教程（第三版）课后习题6.2 （C语言描述）浏览：1225

题解1137：【C语言训练】求函数值（C语言描述）浏览：418

李华

TA的其他文章

你可能喜欢

优质题解 1460题-[蓝桥杯][基础练习VIP]2n皇后问题-题解(C语言描述)--------详细带图解释皇后系列问题，适合新人

评论区

精彩推荐

　　评论区