人工智能实现a*算法解决八数码_小白带你学--回溯算法

微信公众号：小白算法
关注可了解更多算法，并能领取免费资料。问题或建议，请公众号留言; 小白算法，简单白话算法，每个人都能看懂的算法
上一期算法回顾--贪婪法：https://mp.weixin.qq.com/s/978Tdplj3IaSG2dc-5F-aw

算法导读

本期算法讲解思路：
白话算法->算法思路->实例：八皇后问题->实例：01背包问题->算法教你玩数独

白话算法

回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

白话：回溯法可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个岔路口的去尝试找到目的地。如果走错了路，继续返回来找到岔路口的另一条路，直到找到目的地。

实例一：八皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后（棋子），使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

小白面试经：理解如何解决这个问题，回溯法的精髓已经get。如果只是想了解算法面试知识，知道解决这个问题就能完成你的算法积累了。 想快速掌握算法，可以直接查看解题思路的四个步骤。

八皇后问题解题思路：

问题简化：下面我们将八皇后问题转化为四皇后问题，并用回溯法来找到它的解 目的：在4x4棋盘上，使得4个皇后不能在同行同列以及同斜线上。

step1
尝试先放置第一枚皇后，被涂黑的地方是不能放皇后

step2
第二行的皇后只能放在第三格或第四格，比方我们放第三格，则：

此时我们也能理解为什么叫皇后问题了，皇后旁边容不下其他皇后。而在同一个房间放下四个皇后确实是个不容易的问题。