在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。


这是一个典型的回溯问题(当然也有更好的方法,但此处不讨论),首先我们在第一行为一个皇后选定位置,然后在第二行选定第二个皇后的位置······当发现无法选择后,回溯到前一个皇后,再次选择位置······直到尝试过所有的可能性。
当然,我们也有效率更高的方法,例如位运算,不过这里不作详细讨论。
首先,我们要检测放置后的皇后是否会有冲突:

def conflict(state,nextx):
    nexty=len(state)
    for i in range(nexty):
        if(abs(state[i]-nextx) in (0,nexty-i)):
            return True
        return False

水平距离为0或与竖直距离相等,就为真。
我们还要生成一个皇后:

def 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,)+result
for sol in queens(8):
    print(sol)

只剩下最后一个皇后,就遍历所有位置。num为皇后总数,state为放好皇后的位置元组。