python回朔アルゴリズムは八皇后の問題を解く
983 ワード
八皇后問題の解題構想:
碁盤の皇后は、次の行の前に碁盤に置かれた皇后が同業者同列同対角線でない点を判断し、同業者同列同対角線が存在する場合は、前の行に遡り、再び値を取って適切な点を探す.
全部で92種類の解法がありますが、ここでは例を挙げます.
碁盤の皇后は、次の行の前に碁盤に置かれた皇后が同業者同列同対角線でない点を判断し、同業者同列同対角線が存在する場合は、前の行に遡り、再び値を取って適切な点を探す.
全部で92種類の解法がありますが、ここでは例を挙げます.
def place(x, k): #
for i in range(1, k):
#x[i] == x[k]
# abs(x[i] - x[k]) == abs(i - k) k
if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k):
return False
return True
def queens(n):
k = 1 #
x = [0 for row in range(n + 1)]# x 0
while k > 0:
x[k] = x[k] + 1 #
while (x[k] <= n) and (not place(x, k)): # ,
x[k] = x[k] + 1
if x[k] <= n:# ,
if k == n:# ,
break
else: # ,
k = k + 1 #
x[k] = 0 # ,
else:#n ,
x[k] = 0 #
k = k - 1 #
return x[1:] # 1-8
print(queens(8))