暴力搜索法
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種方案父泳，其中包括了許多對(duì)稱結(jié)構(gòu)澈吨。
- 這種很多for循環(huán)的方法貌似不是很美觀，如果是10皇后燥爷，100皇后蜈亩，無法想象代碼會(huì)嵌套成什么樣子。所以才有了遞歸的方法
遞歸的方法
>>> 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前翎，到達(dá)樹的葉子節(jié)點(diǎn)（第八號(hào)值）
... 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號(hào)值 添加到result的前面
...
>>> print(list(queens(8)))
[(0, 4, 7, 5, 2, 6, 1, 3), (0, 5, 7, 2, 6, 3, 1, 4),...]
- 這么聰明的方法和簡(jiǎn)單的代碼當(dāng)然是從書上抄下來的
- 第八號(hào)皇后妥善安置后稚配，才會(huì)觸發(fā)yield語(yǔ)句，最后的for循環(huán)才有值港华，才會(huì)觸發(fā)前面的皇后的yield語(yǔ)句道川。
- 將state變量和pos，分開處理立宜，是一個(gè)值得學(xué)習(xí)的東西冒萄。
