摘要：八皇后問題是十九世紀著名的數(shù)學家高斯年提出。同時可以擴展為九皇后，十皇后問題。解決方案回溯與遞歸。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況。

八皇后問題是十九世紀著名的數(shù)學家高斯1850年提出 。以下為python語言的八皇后代碼，摘自《Python基礎教程》，代碼相對于其他語言，來得短小且一次性可以打印出92種結果。同時可以擴展為九皇后，十皇后問題。

問題：在一個8*8棋盤上，每一行放置一個皇后旗子，且它們不沖突。沖突定義：同一列不能有兩個皇后，每一個對角線也不能有兩個皇后。當然，三個皇后也是不行的，四個也是不行的，憑你的智商應該可以理解吧。

解決方案：回溯與遞歸。

介紹：

1.回溯法

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。參見百度百科

2.遞歸法

階乘 n! = 1 x 2 x 3 x ... x n

用函數(shù)fact(n)表示，可以看出：

fact(1) = 1

fact(n) = n!

           = 1 x 2 x 3 x ... x (n-1) x n

           = (n-1)! x n

           = fact(n-1) x n

于是，fact(n)用遞歸的方式寫出來就是：

def fact(n):
  if n==1:
    return 1
  return n * fact(n - 1)

如果計算fact(5)，結果如下：

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

使用遞歸函數(shù)需要注意防止棧溢出。在計算機中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結構實現(xiàn)的，每當進入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會導致棧溢出。可以試試fact(1000)：

>>> fact(1000)
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 4, in fact
  ...
  File "", line 4, in fact
RuntimeError: maximum recursion depth exceeded

解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化。

尾遞歸是指，在函數(shù)返回的時候，調(diào)用自身本身，并且，return語句不能包含表達式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況。如：

def factorial(n, acc=1):
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

函數(shù)返回時只調(diào)用了它本身factorial(n-1, n*acc)

問題是Python標準的解釋器沒有針對尾遞歸做優(yōu)化，任何遞歸函數(shù)都存在棧溢出的問題。

python源碼：

# -*- coding: utf-8 -*-
#python默認為ascii編碼，中文編碼可以用utf-8
import random
#隨機模塊

def conflict(state,col):
    #沖突函數(shù)，row為行，col為列
    row=len(state)
    for i in range(row):
        if abs(state[i]-col) in (0,row-i):#重要語句
            return True
    return False
    
def queens(num=8,state=()):
    #生成器函數(shù)
    for pos in range(num):
        if not conflict(state, pos):
            if len(state)==num-1:
                yield(pos,)
            else:
                for result in queens(num, state+(pos,)):
                    yield (pos,)+result

def queenprint(solution):
    #打印函數(shù)
    def line(pos,length=len(solution)):
        return ". "*(pos)+"X "+". "*(length-pos-1)
    for pos in solution:
        print line(pos)
        

for solution in list(queens(8)):
    print solution
    
print "  total number is "+str(len(list(queens())))
print "  one of the range is:
"
queenprint(random.choice(list(queens())))

結果：

(0, 4, 7, 5, 2, 6, 1, 3)
(0, 5, 7, 2, 6, 3, 1, 4)
(0, 6, 3, 5, 7, 1, 4, 2)
(0, 6, 4, 7, 1, 3, 5, 2)
(1, 3, 5, 7, 2, 0, 6, 4)
(1, 4, 6, 0, 2, 7, 5, 3)
(1, 4, 6, 3, 0, 7, 5, 2)
(1, 5, 0, 6, 3, 7, 2, 4)
(1, 5, 7, 2, 0, 3, 6, 4)
(1, 6, 2, 5, 7, 4, 0, 3)
(1, 6, 4, 7, 0, 3, 5, 2)
(1, 7, 5, 0, 2, 4, 6, 3)
(2, 0, 6, 4, 7, 1, 3, 5)
(2, 4, 1, 7, 0, 6, 3, 5)
(2, 4, 1, 7, 5, 3, 6, 0)
(2, 4, 6, 0, 3, 1, 7, 5)
(2, 4, 7, 3, 0, 6, 1, 5)
(2, 5, 1, 4, 7, 0, 6, 3)
(2, 5, 1, 6, 0, 3, 7, 4)
(2, 5, 1, 6, 4, 0, 7, 3)
(2, 5, 3, 0, 7, 4, 6, 1)
(2, 5, 3, 1, 7, 4, 6, 0)
(2, 5, 7, 0, 3, 6, 4, 1)
(2, 5, 7, 0, 4, 6, 1, 3)
(2, 5, 7, 1, 3, 0, 6, 4)
(2, 6, 1, 7, 4, 0, 3, 5)
(2, 6, 1, 7, 5, 3, 0, 4)
(2, 7, 3, 6, 0, 5, 1, 4)
(3, 0, 4, 7, 1, 6, 2, 5)
(3, 0, 4, 7, 5, 2, 6, 1)
(3, 1, 4, 7, 5, 0, 2, 6)
(3, 1, 6, 2, 5, 7, 0, 4)
(3, 1, 6, 2, 5, 7, 4, 0)
(3, 1, 6, 4, 0, 7, 5, 2)
(3, 1, 7, 4, 6, 0, 2, 5)
(3, 1, 7, 5, 0, 2, 4, 6)
(3, 5, 0, 4, 1, 7, 2, 6)
(3, 5, 7, 1, 6, 0, 2, 4)
(3, 5, 7, 2, 0, 6, 4, 1)
(3, 6, 0, 7, 4, 1, 5, 2)
(3, 6, 2, 7, 1, 4, 0, 5)
(3, 6, 4, 1, 5, 0, 2, 7)
(3, 6, 4, 2, 0, 5, 7, 1)
(3, 7, 0, 2, 5, 1, 6, 4)
(3, 7, 0, 4, 6, 1, 5, 2)
(3, 7, 4, 2, 0, 6, 1, 5)
(4, 0, 3, 5, 7, 1, 6, 2)
(4, 0, 7, 3, 1, 6, 2, 5)
(4, 0, 7, 5, 2, 6, 1, 3)
(4, 1, 3, 5, 7, 2, 0, 6)
(4, 1, 3, 6, 2, 7, 5, 0)
(4, 1, 5, 0, 6, 3, 7, 2)
(4, 1, 7, 0, 3, 6, 2, 5)
(4, 2, 0, 5, 7, 1, 3, 6)
(4, 2, 0, 6, 1, 7, 5, 3)
(4, 2, 7, 3, 6, 0, 5, 1)
(4, 6, 0, 2, 7, 5, 3, 1)
(4, 6, 0, 3, 1, 7, 5, 2)
(4, 6, 1, 3, 7, 0, 2, 5)
(4, 6, 1, 5, 2, 0, 3, 7)
(4, 6, 1, 5, 2, 0, 7, 3)
(4, 6, 3, 0, 2, 7, 5, 1)
(4, 7, 3, 0, 2, 5, 1, 6)
(4, 7, 3, 0, 6, 1, 5, 2)
(5, 0, 4, 1, 7, 2, 6, 3)
(5, 1, 6, 0, 2, 4, 7, 3)
(5, 1, 6, 0, 3, 7, 4, 2)
(5, 2, 0, 6, 4, 7, 1, 3)
(5, 2, 0, 7, 3, 1, 6, 4)
(5, 2, 0, 7, 4, 1, 3, 6)
(5, 2, 4, 6, 0, 3, 1, 7)
(5, 2, 4, 7, 0, 3, 1, 6)
(5, 2, 6, 1, 3, 7, 0, 4)
(5, 2, 6, 1, 7, 4, 0, 3)
(5, 2, 6, 3, 0, 7, 1, 4)
(5, 3, 0, 4, 7, 1, 6, 2)
(5, 3, 1, 7, 4, 6, 0, 2)
(5, 3, 6, 0, 2, 4, 1, 7)
(5, 3, 6, 0, 7, 1, 4, 2)
(5, 7, 1, 3, 0, 6, 4, 2)
(6, 0, 2, 7, 5, 3, 1, 4)
(6, 1, 3, 0, 7, 4, 2, 5)
(6, 1, 5, 2, 0, 3, 7, 4)
(6, 2, 0, 5, 7, 4, 1, 3)
(6, 2, 7, 1, 4, 0, 5, 3)
(6, 3, 1, 4, 7, 0, 2, 5)
(6, 3, 1, 7, 5, 0, 2, 4)
(6, 4, 2, 0, 5, 7, 1, 3)
(7, 1, 3, 0, 6, 4, 2, 5)
(7, 1, 4, 2, 0, 6, 3, 5)
(7, 2, 0, 5, 1, 4, 6, 3)
(7, 3, 0, 2, 5, 1, 6, 4)
  total number is 92
  one of the range is:

X . . . . . . . 
. . . . . . X . 
. . . X . . . . 
. . . . . X . . 
. . . . . . . X 
. X . . . . . . 
. . . . X . . . 
. . X . . . . . 

源碼解析：

主要利用沖突函數(shù)檢測沖突，如果沖突則回溯，遞歸用到python的yield語句，該語句涉及python的生成器。

沖突函數(shù)：

def conflict(state,col):
  #沖突函數(shù)，row為行，col為列
  row=len(state)
  for i in range(row):
    if abs(state[i]-col) in (0,row-i):#重要語句
      return True
  return False

state為皇后的狀態(tài)，類型是一個元組，如(7, 3, 0, 2, 5, 1, 6, 4)，元組是不可變對象，一經(jīng)創(chuàng)建不能修改，元組是創(chuàng)建生成器的一種方法。

步驟：

假設第一行到第三行的皇后都沒沖突，這個時候要檢測第四行皇后是否沖突。如第一行皇后在第五列，第二行皇后在第八列，第三行皇后在第四列，檢驗第四行皇后放在哪一列不會沖突。

. . . . X . . . 
. . . . . . . X 
. . . X . . . . 

這時state=(4,7,3)，col=?

1.得出目前沒沖突行數(shù)row

   row=len(state)

2.從1~row行依次檢測是否與row+1行皇后沖突

 for i in range(row):

3.如果row+1行皇后所在的列col與其他行皇后的列相同或處于對角線，則沖突

if abs(state[i]-col) in (0,row-i):#重要語句
     return True

以上語句翻譯為（其他行所在的列-要求檢測所在行的列）相差范圍為0~row-i則沖突。

傻瓜式教學：

第一行與第四行沖突，要么在同一列，要么在對角線，當對角線時列數(shù)相差3(因為第一行與第二行對角線相差1，第二行與第三行對角線相差1，則第一行與第三行對角線相差2，以此類推，第一行與第四行沖突，則相差3)

當?shù)谒男兴诹衏ol=4，這時abs ( state[0]-4 ) in (0 , 3-0)為真，因為4-4=0,如：

. . . . X . . . 
. . . . . . . X 
. . . X . . . . 

. . . . X . . .  同列沖突

當?shù)谒男兴诹衏ol=7，這時abs ( state[0]-7 ) in (0 , 3-0)為真，因為abs (4-7)=3,如：

. . . . X . . . 
. . . . . . . X 
. . . X . . . .

. . . . . . . X 對角線沖突

你們這么聰明，該重要語句應該懂吧。

生成器函數(shù)：

def queens(num=8,state=()):
  #生成器函數(shù)
  for pos in range(num):
    if not conflict(state, pos):
      if len(state)==num-1:
        yield(pos,)
      else:
        for result in queens(num, state+(pos,)):
          yield (pos,)+result

生成器：

通過列表生成式，我們可以直接創(chuàng)建一個列表。但是，受到內(nèi)存限制，列表容量肯定是有限的。而且，創(chuàng)建一個包含100萬個元素的列表，不僅占用很大的存儲空間，如果我們僅僅需要訪問前面幾個元素，那后面絕大多數(shù)元素占用的空間都白白浪費了。所以，如果列表元素可以按照某種算法推算出來，那我們是否可以在循環(huán)的過程中不斷推算出后續(xù)的元素呢？這樣就不必創(chuàng)建完整的list，從而節(jié)省大量的空間。在Python中，這種一邊循環(huán)一邊計算的機制，稱為生成器（Generator）。

參考：生成器

步驟：

1.下面該語句為構建所有皇后擺放情況打下基礎。可以嘗試所有情況。

for pos in range(num):

2.如果不沖突，則遞歸構造棋盤。

if not conflict(state, pos):

3.如果棋盤狀態(tài)state已經(jīng)等于num-1，即到達倒數(shù)第二行，而這時最后一行皇后又沒沖突，直接yield，打出其位置(pos, )，Python在顯示只有1個元素的元組時，也會加一個逗號,，以免你誤解成數(shù)學計算意義上的括號。

否則遞歸，打印(pos , )+ result

  if len(state)==num-1:
    yield(pos,)
  else:
    for result in queens(num, state+(pos,)):
      yield (pos,)+result

傻瓜式教學：

例如pos=0，第一行放在第一列，這時不會沖突，但是不會進入if，因為還沒到達倒數(shù)第二行，進入else后，再調(diào)用queens(num, state+(pos,),這時進入第二行，再次遞歸展開則是queens(num,state+(pos, )+(pos, ) ),到達最后一行時返回(pos, )，再返回倒數(shù)第二行，再返回倒數(shù)第三行，最后到達最開始那層(pos, )+result, pos為第一行皇后所在列，result包含第二行皇后所在列和另一個result，就是這么復雜，希望好好琢磨。

優(yōu)美格式的打印函數(shù)就不講了。

講講打印所有結果

for solution in queens(8):
    print solution

queens(8)因為生成器函數(shù)的for循環(huán)，每一次循環(huán)都會yield一個元組出來，所以有很多種情況，可以把它全部打出來。

也可以用list包裝成列表再統(tǒng)計一下多少種數(shù)目。

print "  total number is "+str(len(list(queens()))

隨機優(yōu)美打印一個棋盤情況：

print "  one of the range is:
"
queenprint(random.choice(list(queens())))