用代码求解八皇后问题
《数据结构》——邓俊辉版本 读书笔记
今天学习了回溯法，有两道习题，一道N皇后，一道迷宫寻径。今天，先解决N皇后问题。由于笔者
擅长java，所以用java重现了八皇后问题。
注意是java实现版本，其实用什么语言，都一样。
写在前面的话，
如果想看代码，直接往下拉，注释写的很清楚，凭借注释应
该也能理解八皇后问题。
1. 首先知道什么是八皇后问题，不过，相信看到这里的同学，都应该知道八皇后
问题，简单概括为：每个皇后的势力范围如下图红线标注所示，也就是横纵轴、两条对角线 。在一个皇后的势力范围内，就不能再出现其他皇后了。
2. 这里选用经典的八皇后问题，想让八个皇后，在棋盘上相安无事。用代码怎么实现？首先，明白一件事，电脑就是小萌新啊，只会计算最简单的计算，2+3，它兴许都得差分为（1+1）+（1+1+1）来计算，唯一的优势就是计算的速度比我们快。
3. 刚看到回溯法的时候，想着要用代码，写出来。感觉无从下手，以为很难的，以为电脑不会笨的一个一个去尝试，以为有很神奇的方法存在。学完以后，才发现，很简单，发现回溯法，也是从穷举起手的，只不过带着一定的策略，说白了，优化过的暴力求解。以后，遇到各种听着很高大上的问题别慌，比如，动态规划、深度优先搜索。都是穷举！！只是加了一些策略。I can I believe !你之所能，是因为你想信你能！
解题思路：
都是文字讲解，主要是笔者没有图！！！诶，希望你们读完，能学会八皇后问题。如果文字看不下去。
可以直接去看代码，注释写的很详细。
一行只能有一个皇后，这个根据游戏规则中的皇后的势力就可以得知。
首先让皇后从起点开始摆放。因此，第一个皇后的位置先摆放在（0，0）上，第二个皇后根据游戏规则，只能在第二行寻找合适的位置。在第二个皇后的位置确定以后，再去第三行寻找第三个皇后的位置，以此内推。直到所有的皇后的位置都确定了，问题的一组解，就出来了！但是问题并不是这么简单。
比如现在有三个皇后A、B、C。A在第一行，B在第二行都找到合适的位置了，在第三行所有的位置都是A或者B皇后的势力范围。尴尬了，皇后之间要打架了。怎么办？聪明的你，可能会想到让B皇后，重新找一个合适的位置(这个合适的位置，从B当前的下一个位置开始寻找），然后再来为 C选择合适的位置。如果C还是没有合适的位置，就再次为B寻找合适的位置，循环往复这个动作。
细心的你，可能会有疑问，每次C皇后，找不到合适的位置，就去让B重新寻找合适的位置难道B皇后就一直会有新的合适的位置吗？答案是否定的，当B皇后在它所处的行，再也找不到合适的位置，就说明A皇后的位置，也需要变动了。A皇后的位置变动，跟其他皇后不一样，因为，当前B、C皇后都因为没有合适的位置，所有，就没有摆放在棋盘上。因此，这里棋盘上就一个皇后A，所有它只需要右移一个位置即可。A皇后位置更新以后，就再去为B皇后找合适位置，如果有合适位置，就再去为C皇后寻找合适的位置；如果B皇后没有合适的位置，就再次右移A皇后，循环上面的过程。
有的同学，可能会有疑问，照你说的，计算机就是通过穷举解决问题的，上面的解题过程，计算机确实也是笨笨的一个一个位置去寻找的。那么这算法有效率吗？答案是有效率的。不知你们发现没有，我们每个为下一个皇后寻找合适的位置的时候，都与之前存在的皇后做了比较。只有，有合适的位置，才会摆放皇后；这里寻找合适的位置，会排除没有意义的试探，比如，将皇后摆放在之前某个皇后的势力范围内。没有排除没意义的试探，才是正正的傻傻的穷举。我们的算法，是带着策略的穷举。
上述每次为下一个皇后，寻找合适的位置，就是试探。每次试探不到合理的位置，回头去改变前一个皇后的位置，就是回溯；排除没意义的试探，就是剪枝。上诉的解题过程，就是一个回溯法的思路。
用代码求解八皇后问题
回溯法，如何回溯？需要我们的栈结构，来保存我们每次已经找到合适位置的皇后的列坐标，坐标从0开始。为什么不保存行坐标呢？因为，一行只能有一个皇后，栈中皇后的下标，就是对应皇后的行坐标啦。
首先我们定义一个皇后类
在皇后类中，我们写了一个方法判断，两个皇后之间是否安全
/**
* 皇后类
*/
class Queen {
// 棋盘中的皇后下标,从0开始
int x;
int y;
public Queen(int x, int y) {
this.x = x;
this.y = y;
}
public Queen() {
}
/*
判断皇后所处位置是否相互安全，接收一个皇后对象
安全返回真，不安全返回假
*/
public boolean isSafe(Queen q) {
return !(this.x == q.x ||
this.y == q.y ||
this.x + this.y == q.x + q.y ||
this.x - this.y == q.x - q.y);
}
}
在测试类中定义一个方法，求新皇后应该放置的合理位置
这个方法中创建一个新皇后对象，与之前已经存在的皇后作比较。比较函数则是皇后类定义的方法。
找到合适位置，就返回合适的位置的列坐标；返回-1，代表没有合适位置。
/**
* 为皇后寻找合法位置
*/
public int setY(int N, ArrayList
Queen q;
Queen q_exist;
// 做个标记，
boolean flag ;
// 遍历一行的所有位置
for (int z = y; z < N; z++) {
// 为每个格子创建一个新的皇后
q = new Queen(list.size(), z);
// 起始标记为真
flag = true ;
for (int x = 0; x < list.size(); x++) {
// 创建之前存在的皇后
q_exist = new Queen(x, list.get(x));
// 安全 就返回真，循环作比较
if (!(q_exist.isSafe(q))) {
// 只要和之前存在的的任何一个皇后冲突，
// 并且说明当前皇后不是真的，将标记改为假
// 并跳出当前跳出循环，
flag = false;
break;
}
}
// 如果标记还为真，说明皇后是对滴，并返回新皇后的列坐标，结束函数
if (flag) {
list.add(q.y);
return q.y;
}
}
// 函数没有提前结束，说明没有合适的位置，返回-1；
return -1;
}
求出所有组解
跟着注释看，相信大家都能学会
/**
* 求解N皇后的问题，并给出所有的解,找到一组解，就让最后的皇后换位置，直达第一个皇后的角标越界
* 笔者认为 next_y 变量的动态赋值的 需要很好的理解
* @param N 表示一共有多少皇后，也是棋盘的规模 N x N
*/
private void placeQueen(int N) {
// 表示一共有多少种解法
int all = 1;
// 代表皇后的y坐标
int y = 0;
// 在当前行，下一个位置开始重新寻找合适的位置
int next_y = 0;
// 建立一个栈，用于回溯
// 栈中存放的是皇后的列坐标，也就是y坐标
ArrayList
// 定义一个皇后
Queen queen;
// 开始计算每种情况
while (true) {
// 先判断之前有没有皇后存在
if (list.size() == 0) {
// 创建一个皇后对象，从0开始摆放
queen = new Queen(0, y);
// 将皇后的y坐标记录下来，而x坐标就是栈的长度-1
list.add(queen.y);
// 下一次，栈再次空了，说明第一行的皇后需要右移
y++;
} else {
// 如果已经有皇后存在，既需要为当前皇后寻找合适的位置了
// 就是看setY()方法的返回值
// 在寻找当前皇后合适位置之前，我们先判断是否求出一组解
// 如果，求出一组解，我们打印当前的解
if (list.size() == N) {
System.out.print("第" + all + "组解: ");
all++;
for (int num : list) {
System.out.print(num + " ");
}
System.out.println();
// 当前一组解，已经打印完毕
// 需要重新寻找新的解
// 我们这里让栈顶的皇后，重新寻找位置
// 改变next_y的值就好了。
next_y = list.get(list.size() - 1) + 1;
// 记得弹出栈顶的皇后
list.remove(list.size() - 1);
// }
} else {
// *****************************************************
// 就是这里 我上午写了一个比较臃肿的方法
// 我下午回来，试着重构，结果改了3个小时，才改对了！
// 简直日了狗了，澡都没赶上洗，午觉也没睡成
// setY()方法中，寻找到合适的位置，就会自动添加到栈中
// 因此，这里只关注返回-1的情况
// 返回-1 ，表示需要回溯前一个皇后了
if (-1 == setY(N, list, next_y)) {
// 记录下，先开始的位置
// 这个next_y 很重要的
// 如果需要在当前行 重新寻找合适的位置
// 就需要从当前位置的下一个位置开始遍历寻找
// 因此next_y的值，为当前位置+1
next_y = list.get(list.size() - 1) + 1;
list.remove(list.size() - 1);
// 这里针对的是求出所有解的情况下，退出
// 当求出最后一组解的时候，再次将栈顶元素弹出，重新回溯的话
// 必然会回溯到最初的皇后，即第一个皇后，弹出第一个皇后的时候
// 栈为空。这里就需要作出判断了
// 第一个皇后的下一个位置，是否超出了N的限制
if (list.size() == 0) {
// 判断是右移还是退出
if (next_y < N) {
list.add(next_y);
next_y = 0;
} else {
break;
}
}
} else {
// 如果setY()没有返回-1，说明找到了合适的位置
// 就需要为下一个皇后寻找合适的位置了
// 在新的一行开始寻找，必然需要从0开始寻找位置
next_y = 0;
// ****************************************************
}
}
}
}
}
测试方法
不了解Junit测试框架的同学，这里将 placeQueen(6)；写到main函数里面即可。
@Test
public void test() {
placeQueen(6);
}
运行结果
六皇后问题一共有四组解
得出的解，只是皇后从0开始的 “列坐标” ，它们的行坐标，是0到N-1顺序排列；
比如 ： 1 3 5 0 2 4，就是下面的情况
列 行
1 0
3 1
5 2
0 3
2 4
4 5
下面运算一下经典的八皇后，看看一个有多少组解
在图中可以看出，一共有92组解。并且可以看到我们计算所有的解，只花费了0.026s。还是很快的。
八皇后问题，已经被我们解决了，用的就是回溯法，可能你
已经对回溯法，有了一定的了解，就是试探-剪枝-回溯。
希望你下次遇到什么新的算法策略。不要紧张，它们只是穷
举，带有策略的穷举，策略还需要你来写呢！
回溯法还有一个好玩的题，迷宫寻径。过几天，我在写一个关于迷宫寻径的博
客，题目有千千万，但是思想是一样的。希望大家和我，都能在解题过程中，对
回溯法有一个很好的掌握，下一次遇到问题的时候，能熟练使用回溯法解决它。
八皇后问题——列出所有的解，可推至N皇后的更多相关文章
Java 8新特性探究（八）精简的JRE详解
http://www.importnew.com/14926.html 首页 所有文章 资讯 Web 架构 基础技术 书籍 教程 Java小组 工具资源 - 导航条 - 首页 所有文章 资讯 ...
Android为TV端助力 转载:Android绘图Canvas十八般武器之Shader详解及实战篇(上)
前言 Android中绘图离不开的就是Canvas了,Canvas是一个庞大的知识体系,有Java层的,也有jni层深入到Framework.Canvas有许多的知识内容,构建了一个武器库一般,所谓十 ...
Android为TV端助力 转载：Android绘图Canvas十八般武器之Shader详解及实战篇(下)
LinearGradient 线性渐变渲染器 LinearGradient中文翻译过来就是线性渐变的意思.线性渐变通俗来讲就是给起点设置一个颜色值如#faf84d,终点设置一个颜色值如#CC423C, ...
Linux Shell系列教程之（八）Shell printf命令详解
本文是Linux Shell系列教程的第(八)篇,更多shell教程请看:Linux Shell系列教程 在上一篇:Linux Shell系列教程之(七)Shell输出这篇文章中,已经对Shell p ...
[转帖]Java 8新特性探究（八）精简的JRE详解
Java 8新特性探究(八)精简的JRE详解 https://my.oschina.net/benhaile/blog/211804 精简版的api 撸了今年阿里.网易和美团的面试,我有一个重要发 ...
(八)open函数的flag详解
3.1.4.open函数的flag详解13.1.4.1.读写权限:O_RDONLY O_WRONLY O_RDWR(1)linux中文件有读写权限,我们在open打开文件时也可以附带一定的权限说明(譬 ...
CoreCLR源码探索(八) JIT的工作原理(详解篇)
在上一篇我们对CoreCLR中的JIT有了一个基础的了解, 这一篇我们将更详细分析JIT的实现. JIT的实现代码主要在https://github.com/dotnet/coreclr/tree/m ...
JavaScript学习笔记（八）——变量的作用域与解构赋值
在学习廖雪峰前辈的JavaScript教程中,遇到了一些需要注意的点,因此作为学习笔记列出来,提醒自己注意! 如果大家有需要,欢迎访问前辈的博客https://www.liaoxuefeng.com/ ...
VS2010/MFC编程入门之三十八（状态栏的使用详解）
上一节中鸡啄米讲了工具栏的创建.停靠与使用,本节来讲解状态栏的知识. 状态栏简介 状态栏相信大家在很多窗口中都能见到,它总是用来显示各种状态.状态栏实际上也是一个窗口,一般分为几个窗格,每个窗格分别用 ...
随机推荐
QuartzNet 远程管理持久化job 项目, 源码在Github..希望对大家有所帮助
文章目录 为了方便大家去学习 QuartzNet 与 CrystalQuartz 更多信息请点击链接查看 简介 结构图 为了方便大家去学习 QuartzNet 与 CrystalQuartz 更多信息 ...
kubernetes 1.14安装部署helm插件
简单介绍: Helm其实就是一个基于Kubernetes的程序包(资源包)管理器,它将一个应用的相关资源组织成为Charts,并通过Charts管理程序包.再简单点说,可以当做RHEL/CentOS系 ...
element ui table组件自定义合计栏,后台给的数据
合计的数据是后台传的,所以用table组件自定义一行用来合计 Oracle中查询走索引的情况 1．对返回的行无任何限定条件,即没有where子句 2．未对数据表与任何索引主列相对应的行限定条件例如:在City-State-Zip列创建了三列复合索引,那么仅对State列限定条件不能使用这个索引 ... 微信小程序带cookie的request请求代码封装(小程序使用session) 微信小程序带cookie的request请求可,以使服务端知道是同一个客户端请求. session_id会不变,从而很好的使用服务端的session. 写一个工具函数,直接导入使用即可,接口同 wx. ... iTop汉化 阿里重磅开源在线分析诊断工具Arthas(阿尔萨斯) github地址: Arthas English version goes here. Arthas 是Alibaba开源的Java诊断工具,深受开发者喜爱. 当你遇到以下类似问题而束手无策时,Art ... 【Tomcat】Tomcat 基本使用（二） 上一章介绍了Tomcat原理[Tomcat]Tomcat 原理架构(一),本章介绍Tomcat的基本使用 Tomcat端口设置 tomcat端口设置,在tomcat的配置文件目录下的server.xm ... Flink 实现指定时长或消息条数的触发器 Flink 中窗口是很重要的一个功能,而窗口又经常配合触发器一起使用. Flink 自带的触发器大概有: CountTrigger: 指定条数触发 ContinuousEventTimeTrigger ... deployment.yaml 带同步时区 [root@lab2 dandang]# cat dandang.v1.yaml apiVersion: v1 kind: ReplicationController metadata: name: ...