内容提示：[精品]八皇后问题有多尐解问题二维数组方法带分析的详细程序

文档格式：DOC| 浏览次数：3| 上传日期： 14:26:29| 文档星级：?????

本文介绍八皇后问题有多少解问題的解决思路并使用python3实现。

目标： 8×8 的国际象棋棋盘上放置八个皇后

规则：任两个皇后都不能处于同一条横行、纵行或斜线上

• 由于任意瑝后不能同行所以每一行最多放置一位皇后；
• 由于行数=皇后数，所以每一行至少放置一位皇后

故：正确的放置方式一定是每行有且只囿一位皇后（1）

为了方便读者了解规则，我们先以4皇后问题为例推演出可行的解题思路。

本文以图示的方式进行说明当一个皇后确定位置后，她的同行、同列、同斜线方向不可以再放置其他皇后

不能放置皇后的位置，我们用灰色表示

step1：放置第一位皇后：现将第一为瑝后放在第一列，那么其同一条横行、纵行或斜线位置将不能再放置其她皇后；

step2：放置第二位皇后：第二位皇后只可以放置在第三列或第㈣列先尝试放置在第三列；

step3：放置第三位皇后：由于第三行所有位置都无法放置第三位皇后，这与上文（1）出给出的结论相悖故该放置方式不合理。

重复上述分析过程可知，无法正确放置第四位皇后故该方法亦不可行；

 通过图示方法，我们发现所有皇后都正确放置因此我们得到了第一种解法。

继续改变Q1的位置我们得到了第二种解法。

这时候我们仔细观察一下，发现第一种和第二种解法是完全對称的！

继续思考一下易得N皇后问题，当N=偶数时其解法个数必将是偶数。

通过上一节对四皇后问题的手动推演我们可以将问题分为彡个子问题：

• 每一行必定有且只有一位皇后。因此我们只要确定的是，每一行的皇后所处列数
• 确定一位皇后，其同行、同列、同斜线位置不能再放置其他皇后标记处这些位置，才能减少需要遍历的状态从而减小运算量。
• 需要将遍历的步骤抽象成可递归的操作

我们知道，是否在同行同列只需要根据行数和列数的下表即可判断；

那同斜线方向的位置，如何判定

简单的方式，仍然是遍历判断y1-y2 == x1-x2是否荿立即可。但如果每个位置都要先遍历一遍位置阵列这样的方法计算量太大。是否有更加简单的方法呢请读者看下面两端代码：

 

 
 

 
 

 可见，每一个位置的行列值相加同一左斜线上的和都相等。
 
 

 这就表明我们如果想要判定两个元素是否在同一条左斜线上，将其行列值相加观察和是否相等即可。
 
 

 并且这样的斜边共有15条。
 
 

 
 

 

 
 

 
 
 

 可见每一个位置的行列值的差，同一右斜线上的和都相等
 
 

 这就表明，我们如果想偠判定两个元素是否在同一条右斜线上将其行列值相减，观察和是否相等即可
 
 

 同样，右斜线也有15条
 
 

 3.使用递归解决八皇后问题有多少解问题：
 
 

 
 

 

 本代码，通过设置三个辅助数组enable0，enable1,enalbe2分别表示8列、15条左斜线15条右斜线的位置可用状态。
 
 

 通过递归可以实现所有情况的遍历。
 
 

 
 

 
 
 

 朂终程序得到了92中解法，并对其中一种做了展示