八皇后问题思路

文章目录

• 问题描述
• 基本思路
• 搜索过程

在8*8的棋盘上，放置八个皇后，要求任意两个皇后不能在同一行、同一列、对角线上。

规则：

1. 棋盘上有八个棋子
2. 所有棋子不能相互攻击

状态：棋盘上棋子的分布情况，可以用含有八个分量的一维向量来表示，如[1,5,8,6,3,7,2,4]可以用来表示上图棋子的分布，第i个分量的取值为j，代表棋盘的第i列第j行放有棋子。

初始状态，棋盘上没有棋子，用[0,0,0,0,0,0,0,0]表示；目标状态就是符合游戏规则的棋子分布情况，我们不能直接确定它，但是可以通过规则来检验给定的状态是否为目标状态。

搜索：在众多状态中通过规则的检验找到答案

棋盘状态是有限的，通过搜索，我们已经可以找到问题的答案了。

接下来的内容，就和搜索效率相关。

既然我们要从众多状态中进行搜索，就需要考虑：应该以什么顺序进行搜索？

先从结果反向思考：

假如我们想要获得[1,5,8,6,3,7,2,4]这样的解，可以考虑在[1,5,8,6,3,7,2,0]的基础上搜索。[1,5,8,6,3,7,2,0]已经符合规则2即所有棋子不能相互攻击，只要在第8列的不同行加入棋子，找到满足规则2的情况即可。同理，想获得[1,5,8,6,3,7,2,0]这样的状态，可以考虑在[1,5,8,6,3,7,0,0]的基础上搜索，在第7列的不同行加入棋子，找到满足规则2的情况。以此类推，最终会回到初始棋盘上没有棋子的状态。

搜索的顺序：

与上面的过程相反，我们从空棋盘[0,0,0,0,0,0,0,0]开始逐列放置棋子，先在第一列放置棋子，共八种放置方式，此时[1,0,0,0,0,0,0,0]~[8,0,0,0,0,0,0,0]都满足规则2的要求，我们可以在其中任意一种状态的基础上进行扩展。于是，我们需要把这些满足规则2的状态存储起来，并选择其中的一种进行扩展。此时待扩展状态均只在第一列放置了棋子，并不需要考虑顺序问题。假设我们选择了[1,0,0,0,0,0,0,0]进行扩展，在第二列放置棋子仍有八种情况，符合规则2的状态为[1,3,0,0,0,0,0,0]~[1,8,0,0,0,0,0,0]，也将其存储起来。接下来就涉及到了顺序问题。我们是从两列的状态扩展，还是从一列的状态进行扩展？

此时待扩展节点的存储为[[2,0,0,0,0,0,0,0]~[8,0,0,0,0,0,0,0],[1,3,0,0,0,0,0,0]~[1,8,0,0,0,0,0,0]]，深度优先搜索从两列的状态开始扩展，而广度优先搜索从一列的状态进行扩展。前者使用栈来存储待扩展节点，而后者使用队列实现。

对于深度优先的办法，随着层数加深，如果找到解，问题就结束了，如果未能找到解，需要回到上一层继续扩展，直到找到解为止或者该问题没有解。