七十八、 回溯法解决八皇后问题

「@Author：Runsen」

八皇后问题

「八皇后问题」是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。

来自百度百科，皇后的走法是可以横竖斜着走任意格。

国际象棋棋盘是8 * 8的方格，每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线（左上左下右上右下四个方向）上的棋子。在一个棋盘上如果要放八个皇后，使得她们互相之间不能攻击（即任意两两之间都不同行不同列不同斜线），求出一种所有布局方式。

八皇后问题，是一个古老而著名的问题，是经典又脍炙人口的典型编程问题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，计算机语言可以解决此问题。

好了我们来解决这个八皇后的问题，下面介绍是回溯法

回溯法

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

说到底，就是一个一个的试错，在第一行第一个列放皇后，然后在第二行放皇后，一直将整个棋盘放满。如果发现放不了，就回到上一行放皇后的地方，选择其他位置放皇后。

回溯法就是不断的试错，有错了就回到上一行放皇后，直到整个棋盘放满。

下图是八皇后问题的一个解：

首先定义一个冲突函数，如下，ps是positions 的缩写，表示之前摆放的皇后位置，是一个list，每个元素代表第几列放的，比如上图所有的皇后可以表示为

state 这里理解元组，就是之前放回皇后的位置，nextX表示新皇后要放的横坐标，conflict函数就是检测新皇后放的位置和之前的皇后在位置上是否有冲突，有的话返回True。

再定义一个queens函数， 这里我们用Python的生成器来存储我们的结果

list(queens(8))就是我们的结果，下面我们定义一个preetyprint打印美观先

完整代码

整个代码中包含了三个方法，分别是conflict、queens、preetyprint。

❝本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。 ❞

Reference

[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100

- END -