快捷導(dǎo)航

Python解決八皇后問題示例

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

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

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

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

這是一個(gè)典型的回溯算法，我們可以將問題進(jìn)行分解：

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

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

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

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

具體代碼如下：

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

運(yùn)行結(jié)果：