什么是八皇后问题？
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。——【百度百科】
如下图所示的摆放方式就是一个满足要求的方案：
八皇后有多少种解？
前面引自百科的资料里也有提到，高斯认为有76种方案，还有人解出有92种方案。到底有多少种方案呢？高斯这么厉害的角色也会出错吗？我今天就想用一小段代码来求解这个问题。不过顺便说一句，人家高斯当年计算可没有计算机帮忙啊，能给出76种方案已经是非常人所能匹敌的。
思路
总思想：暴力破解
步骤一：罗列所有可能的摆放方式；
步骤二：检测某种摆放方式是否满足要求；
步骤一
方式一：罗列摆放方式，第一感觉需要一个矩阵来存储一种状态，因为棋盘是个8 * 8的方格，如果用一个8 * 8的矩阵，有皇后的用1表示，没有皇后的用0，然后再判断这个矩阵是否满足任意两个皇后没有处于同一行同一列或者同一个斜线上。这种表示方式直观，但是如果要罗列这个矩阵所有可能的状态，代价就太大了。因为每个格子都有2种可选状态，总共有64个格子，那么一共有 2^64个状态需要判断，明显这条路是走不通了，果断换一条路吧！
方式二：上面那种方式之所以不行，是因为我们没有充分利用限定条件。满足要求的摆放方式保证了每行每列都只有一个皇后，上面很多种罗列方式明显是不满足的。既然每一行都有一个皇后，那么我们用一个数组column_index[8]来存储每一行的皇后所在的列下标。也就是说 column_index[i]表示第i行的皇后所在的列。column_index如何填充呢？，只需看一下上面的图就知道，数组中必然包含0~7八个数字，而且每个数字必然出现一次，也就是说，一个状态就是0~7的一个排列。比如，上面八皇后的摆放用这种方式表示就是:
column_index = [5, 1, 6, 0, 3, 7, 4, 2]
那么有多少种排列就有多少种状态需要判断，很简单，8个不同数字的排列数有8！=40320种，也就是说我们将需要判断的状态从 2^64降到了四万多。好，四万多个状态对于计算机来说判断就很快了。进入下一步吧。
步骤二 判断是否合法
上面的罗列方式已经确保8皇后不在同一行不在同一列，因此只需要判断是否存在两个皇后在同一个对角线，而这个只需要判断 abs(i - j) == abs(column_index[i] - column_index[j])
好最后看一下代码吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import itertools
def is_valid_8_quene(col_index):
for i in range(8):
for j in range(8):
if i != j and abs(i-j) == abs(col_index[i] - col_index[j])
return False
return True
def count_8_quene_solutions():
return sum([1 for p in itertools.permutations(range(8)) if is_valid_8_quene(p)])
if __name__ == '__main__':
print (count_8_quene_solutions())
最后结果是多少呢？
我不会告诉你是92的
原文地址：http://jiangdapeng.github.io/blog/2014/03/07/eight-queen-problem/Written by Asuwill posted at http://jiangdapeng.github.io版权声明：自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0