问题描述

这是一个经典的计算机科学问题——
假设一个8 × 8的棋盘上放置八个皇后（国际象棋，皇后只能沿斜线行走任意步数）
要求八个皇后位与不同行不同列不能发生矛盾（也就是不相威胁），要我们找出所有放置方案

解决思路

遍历所有放置位置并判断是否符合要求

• 相关概念——回溯（借助递归实现）
  比如进一个大厅有两个门，进入左边的门后发现不是你要的房间，那么我们就要退回（回溯）大厅，重新选择大门
• 位置的记录，采用列表，“索引-值”对代表“行-列”对，注意：我们规定序号从0计起
• 位置的获取，通过生成器生成

遍历是一种“蠢”方法，只能解决皇后数量不多的情况，更多高效算法，参考
www.cit.gu.edu.au/~sosic/nqueens.html

#冲突判断
def conflict(state, nextX): 
    '''
    判断新皇后与已知的皇后是否发生冲突
    state参数接受一个已知的位置元组
    nextX参数接受下一个列位置
    '''
    nextY = len(state)          #nextY通过state长度得到下一个行位置
    for i in range(nextY):           #遍历0～nextY - 1行（即已放置的所有行）
        if abs(state[i] - nextX) in (0, nextY - i):      
            #皇后沿斜线行走，如果行数差值与列数差值相等，说明存在矛盾
            #如果行数差值为0，说明该列已被其他皇后占用，不符合要求
            return True
    return False

#递归，位置生成器
def queens(num = 8, state = ()):
    '''
    产生皇后的位置并判断是否符合要求，如果符合要求则生成各个皇后的位置组成了元组
    num表示皇后个数（和棋盘规格num × num）
    state表示已知的皇后个数，因为最开始是没有放置好的皇后的，所以给它一个默认值()空元组，方便后面的元组连接
    '''
    for pos in range(num):          #遍历0～num - 1列（即所有列）
        if not conflict(state, pos):       #判断当前位置（len(state)行，pos列）是否冲突
            if len(state) == num - 1:              #如果是最后一个皇后（最里层的递归）
                yield (pos,)                              #直接生成该皇后位置，方便外层递归的连接，而且必须写成元组的形式（必须加上逗号和括号代表它是元组）
            else:                                                                      #如果不是最后一个皇后（外层递归）
                for result in queens(num, state + (pos,)):         #递归调用，加入当前位置，放置下一个皇后（进入下一层递归）
                                                                                           #遍历所有剩下的皇后都符合的位置
                    yield (pos,) + result                                       #追加当前位置，返回到上一层递归，直到位置都整合到同一个元组里

#整理打印
def prettyprint(solution):
    '''
    用形象的方式打印棋盘，_代表空格，X表示皇后的位置
    solution表示某一个解决方案（元组）
    '''
    def line(pos, lenth=len(solution)):              #助手函数，打印一行，因为其他外部函数用不着，索性嵌套在该函数内
        return '_ ' * (pos) + 'X' + '_ ' * (lenth-pos-1)
    for pos in solution:
        print line(pos)
    
    #也可以直接写成——
    #for pos in solution:
    #    print '_ ' * (pos) + 'X' + '_ ' * ( len(solution) - pos - 1 )

list( queens(4) )          #四个皇后的情况

[(1, 3, 0, 2), (2, 0, 3, 1)]

len( list( queens(8) ) )          #八皇后的可能数

92

from random import choice

prettyprint(   choice(  list( queens(8) )  )   )          #随机选取八皇后的一种方案并打印

_ X_ _ _ _ _ _ 
_ _ _ _ _ X_ _ 
_ _ _ _ _ _ _ X
_ _ X_ _ _ _ _ 
X_ _ _ _ _ _ _ 
_ _ _ X_ _ _ _ 
_ _ _ _ _ _ X_ 
_ _ _ _ X_ _ _