python 基础算法之八皇后问题

解决思路：递归/回溯

• 首先是从数据结构的角度考虑如何记录摆放：
  既然就是棋盘，就很容易想到用二维元祖来解这个问题，但是再仔细想想，其实一维元组也是可以记录摆放方式的
  例如我用state[0] = 4 state[1] =2 表示第一行的皇后在第4列，第二行的皇后在第1列

算法思想

• 创建一个ret=[]，把所有成功的state都包进去，最后求ret
• 关键就是state怎么求
• 如果有八个子，我肯定每个位置都放一下，所以最外层应该是for循环
• 放之前，我先想想这个位置能不能放，判断的函数用conflict()来表示
  －如果能放的话，我就放下来
  －看是不是最后一个子，如果不是，那么我这次的子后面的所有能放的都传给我
  －如果是最后一个子，那么我就这个结果yield回去

代码实现

def conflict(state,nextx):
    '定义冲突函数,state为元组，nextx为下一个皇后的水平位置，nexty为下一个皇后的垂直位置'
    nexty = len(state)
    for i in range(nexty):
        if abs(state[i]-nextx) in (0,nexty-i):#若下一个皇后和前面的皇后列相同或者在一条对角线上，则冲突
            return True
    return False

def queens(num=8,state=()):
    '八皇后问题，这里num表示规模'
    for pos in range(num):
        if not conflict(state,pos):#位置不冲突
            if len(state) == num - 1:#若是最后一个皇后，则返回该位置
                yield (pos,)
            else:#若不是最后一个皇后，则将该位置返回到state元组并传给后面的皇后
                for result in queens(num,state + (pos,)):
                    yield (pos,) + result