快捷導(dǎo)航

Python解決八皇后問題示例

更新時間：2018年04月22日 14:27:07 作者：wangbowj123

這篇文章主要介紹了Python解決八皇后問題,簡單描述了八皇后問題的原理并結(jié)合實例形式分析了Python基于遞歸算法解決八皇后問題的相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Python解決八皇后問題的方法。分享給大家供大家參考，具體如下：

八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)閚1×n1，而皇后個數(shù)也變成n2。而且僅當 n2 = 1 或 n1 ≥ 3 時問題有解。

這是一個典型的回溯算法，我們可以將問題進行分解：

首先，我們要想到某種方法來解決沖突檢測問題，即不能令棋子處于能相互吃掉的位置——相鄰、左右對角線。

其次，運用回溯的方法，求得問題的解。此處具體為函數(shù)的遞歸調(diào)用，當調(diào)用到棋盤的最后一行，便跳出，求得解。

最后，將我們的解打印出來。難點在于對遞歸調(diào)用函數(shù)的理解。

這僅僅是思路，是我們必須要解決的問題，但并不代表程序的運行流程。

具體代碼如下：

#-*- coding:utf-8 -*-
import random
#沖突檢查，在定義state時，采用state來標志每個皇后的位置，其中索引用來表示橫坐標，基對應(yīng)的值表示縱坐標，例如： state[0]=3，表示該皇后位于第1行的第4列上
def conflict(state, nextX):
  nextY = len(state)
#  print(nextY),
  for i in range(nextY):
    #如果下一個皇后的位置與當前的皇后位置相鄰（包括上下，左右）或在同一對角線上，則說明有沖突，需要重新擺放
    if abs(state[i]-nextX) in (0, nextY-i):
#縱坐標減去下一個皇后的橫坐標的絕對值 處于 0到下一皇后縱坐標減i則沖突
      return True
  return False
#采用生成器的方式來產(chǎn)生每一個皇后的位置，并用遞歸來實現(xiàn)下一個皇后的位置。
def queens(num, state=()):
  #num = 8
#  print("%d "%len(state)),
  for pos in range(num):
    if not conflict(state, pos): #如果沒有沖突
      #產(chǎn)生當前皇后的位置信息
      if len(state) == num-1:
        yield (pos, ) #生成元組
      #否則，把當前皇后的位置信息，添加到狀態(tài)列表里，并傳遞給下一皇后。
      else:
        for result in queens(num, state+(pos,)):
          yield (pos, ) + result
          #result這個變量代表的是quees返回的元組
#若是最后一行 對于 pos in range(num)調(diào)用conflict(state, num) ,
#如果沒有沖突,生成元組
#若不是最后一行 對于pos in range(num)調(diào)用conflict(state, pos),
#如果沒有沖突,state更新,遞歸調(diào)用queens(num, state) state將更新
#為了直觀表現(xiàn)棋盤，用X表示每個皇后的位置
def prettyprint(solution):
  def line(pos, length=len(solution)):
    return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
  for pos in solution:
    print line(pos)
if __name__ == "__main__":#來判斷是否是在直接運行該.py文件
  prettyprint(random.choice(list(queens(8))))

運行結(jié)果：