8皇后问题
问题描述:
八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
解决方案：
八皇后需要注意的点:
(1)不能在同一行
(2)不能在同一列
(3)不能在同一对脚线(这就需要保证，到X和Y的距离不可以和前面的位置的X和Y相对应的距离相等)。
代码实现:
def conflict(state, nextX): nextY = len(state) for i in range(nextY): if abs(state[i] - nextX) in (0, nextY - i): return True return Falsedef queens(num = 8, state = ()): for pos in range(num): if not conflict(state, pos): if len(state) == num - 1: yield (pos, ) else: for result in queens(num, state + (pos, )): yield (pos, ) + resultprint list(queens()) print len(list(queens()))def prettyprint(solution): def line(pos, length = len(solution)): return '. ' * (pos) + 'X' + '. ' * (length - pos -1) for pos in solution: print line(pos)import randomprettyprint(random.choice(list(queens())))
