算法之----回溯算法（小白看不懂打我，以N皇后问题为案例，带你看回溯过程）一、回溯算法的定义

83 阅读 0 评论 55 点赞

我是靠谱客的博主慈祥铃铛，最近开发中收集的这篇文章主要介绍算法之----回溯算法（小白看不懂打我，以N皇后问题为案例，带你看回溯过程）一、回溯算法的定义，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

如果这篇文章能够让你更进一步了解回溯算法，哪怕一点点也行，希望留下个赞

文章目录

一、回溯算法的定义
- 二、回溯算法的深入理解
- - 三、N皇后问题案例驱动讲解
  - - 四、分享与交流

一、回溯算法的定义

百度定义：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。点它直达
我的定义：根据题目要求的条件，假设某个“点”、“状态”符合条件，不断的往深度试探，不行就回退到上级，直到所有的假设都完成了
那它跟穷举法又有什么本质区别呢？区别在于，它能够回溯。

二、回溯算法的深入理解

在分享这篇文章之前，我查看了很多csdn博主的文章，希望能够找到回溯算法的深入理解的文章，但都是无功而返，然后我去百度，发现百度的理解，符合我对这个算法的理解，所以我希望大家直接看百度的就行，虽然有点难懂，但没事，后面我会演示说明给大家看
在此我做了回溯算法的经典案例：迷宫问题、数独问题、8皇后问题；如果需要java完整实现代码，下方留言或者关注微信公众号，我可以亲自发给大家，每一步都有详细的解释，不怕你不懂
百度的深入理解：从开始结点（根结点）出发，以深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。
如果你真的理解了第三点，我相信你的肯定理解了回溯算法的原理，强烈建议看看第三点（虽然很臭很长）

所谓的模板套路？

套路是别人总结的，你连回溯都不知道怎么回溯，你怎么用人家的模板？
如果你真想彻底搞定这个回溯算法，那就自己走一遍，做几道经典案例题，然后自己总结模板，别一上来就什么模板不模板的。

三、N皇后问题案例驱动讲解

纸上谈兵终觉浅，得知此事要躬行，如果你想真的搞懂这个算法，那就去做经典案例

N皇后案例：
这里我用4皇后案例问题来讲解回溯算法的回溯过程，带你看看怎么回溯的，说了大半天的回溯，到底是如何回溯的。

规则：
4×4 格的国际象棋上摆放4个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法

这里放上4*4的棋盘，为每个格子编上序号：(这里用表格来模拟)

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

回溯过程：（希望你跟着我跑之前，自己先跑一下，要怎么放皇后才能够解决问题）
看图说话： ---->

走起：

每次放置皇后都是放在行开头第一个位置
每放置一个皇后都要先判断是否是和已放的皇后冲突
第一个皇后可以放在16格中的任意位置，但是为了不移漏，所以肯定先放1号
第二个皇后放5号，不行，6号不行，7号可以，（此时的8号还未探测，因为7号节点符合条件，所以还要往下探测）
第三个皇后放9号，不行，10号不行，11,12都不行（此时回到第四步的7号节点，这就是回溯，也就是递归返回来了，因为第五步走完走不通）
那第二个皇后就放到8号格子，然后又开始放第三个皇后，9号不行，10号行（11、12还未探测，因为10满足条件，所以又往下探测）
放第四个皇后，13. 14. 15. 16都不行，回溯到第三个皇后的10号
第三个皇后开始放11号格，然后又开始第七步的操作，发现又不行，然后第三个皇后放12号，又重复第7步，还是不行，所以回溯到第二个皇后的8号节点，再回溯到1号节点
至此1号节点的所有路径都已经探测完，没有通路（符合条件的路），所以把第一个皇后放置在2号节点，又重复上述操作，这就是回溯算法的执行过程

小提示：回溯的过程是用栈来实现的，因为栈的特性是后进先出（所以如果你不是很了解这个过程，那可以把每次调用递归函数都压入栈，然后走一下过程）

如果上述说的你真的懂了，那写代码真的就不难了，附上源代码

源代码

package digui;
/**
 *  回溯法来解决8皇后问题
 *(核心思想就是递归，不断的探测递归)
 * @author 1710269824
 *
 */

public class Huanghou {
	//定义一个max表示共有多少个皇后
	int max = 4;
	//定义数组array, 保存皇后放置位置的结果,比如 arr = {1 3 0 2 } 
	int[] array = new int[max];
	//设置一个变量，用来限制解集
	static int limit = 0;
	public static void main(String[] args) {
		Huanghou queue = new Huanghou();
		queue.check(0);
	}
	
	
	
	//编写一个方法，放置第n个皇后
	//特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
	private void check(int n) {
		if(n == max) {  //n = 8 , 其实8个皇后就既然放好
			print();
			return;
		}
		//依次放入皇后，并判断是否冲突
		for(int i = 0; i < max; i++) {
			//先把当前这个皇后 n , 放到该行的第1列
			array[n] = i;
			//判断当放置第n个皇后到i列时，是否冲突
			if(judge(n)) { // 不冲突
				//接着放n+1个皇后,即开始递归
				check(n+1); //  
			}
			//如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
		}
	}
	
	//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
	/**
	 * 
	 * @param n 表示第n个皇后
	 * @return
	 */
	private boolean judge(int n) {
		for(int i = 0; i < n; i++) {
			// 说明
			//1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
			//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
			// n = 1  放置第 2列 1 n = 1 array[1] = 1
			// Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
			//3. 判断是否在同一行, 没有必要，n 每次都在递增
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
				return false;
			}
		}
		return true;
	}
	
	//写一个方法，可以将皇后摆放的位置输出
	private void print() {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}

}