暴力搜索法
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，分开处理，是一个值得学习的东西。
