6. Python3 解决八皇后问题

暴力搜索法

def conflict(i1,i2,i3,i4,i5,i6,i7,i8):
    x = list(range(8));
    y = [i1,i2,i3,i4,i5,i6,i7,i8];
    for i in range(8):
        for j in range(i+1,8):
            if  (x[i] == x[j]) or (y[i]==y[j]) or (x[i]- y[i] ==x[j]- y[j])  or  (x[i]+ y[i] == x[j]+ y[j]) :
                return  True
            else:
                pass
    return False
            
num = 0;
for i1 in range(8):
    for i2 in range(8):
        for i3 in range(8):
            for i4 in range(8):
                for i5 in range(8):
                    for i6 in range(8):
                        for i7 in range(8):
                            for i8 in range(8):
                                if conflict(i1,i2,i3,i4,i5,i6,i7,i8):
                                    pass
                                else:
                                    num +=1;
                                    print(num,(i1,i2,i3,i4,i5,i6,i7,i8))

• 共92种方案，其中包括了许多对称结构。
• 这种很多for循环的方法貌似不是很美观，如果是10皇后，100皇后，无法想象代码会嵌套成什么样子。所以才有了递归的方法

递归的方法

>>> 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
... 
>>> def queens(num =8, state=()):
...     for pos in range(num): # all posible positions for the next queen
...         if not conflict(state,pos): #得到的值不冲突
...             if len(state) == num-1:# The last queen，到达树的叶子节点（第八号值）
...                 yield (pos,)             
...             else: # NOT the last queen, we need try to place the other queens
...                 for result in queens(num, state+(pos,)): 
...                     yield (pos,) + result # 把第i号值 添加到result的前面
... 
>>> print(list(queens(8)))
[(0, 4, 7, 5, 2, 6, 1, 3), (0, 5, 7, 2, 6, 3, 1, 4),...]

• 这么聪明的方法和简单的代码当然是从书上抄下来的
• 第八号皇后妥善安置后，才会触发yield语句，最后的for循环才有值，才会触发前面的皇后的yield语句。
• 将state变量和pos，分开处理，是一个值得学习的东西。