算法求解思路培養-2. 八皇後問題(說說遞歸）
按道理來說，遞歸是很簡單的。例如求斐波那契數的公式，
fibonaci(N) = fibonaci(N-1)+fibonaci(N-2) 不複雜吧，再比方，階乘公式：
Factorial(N) = N*Factorial(N-1) 有啥難的呢？
但真正在面試、比賽或者工作中遇到的題目是這樣的。
1、八皇後問題（面試）：
在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問一共有多少種擺法。
2、遞歸周遊檔案夾（工作）
3、列印一個數組的全排列（面試）
4、棋盤覆寫問題（競賽）
那麼，如何求解這些問題呢？
還是先從簡單的解法入手引出遞歸。下面我們以八皇後來舉例。其暴力求解方法如下：
def is_valid(position):
dim = len(position)
for i in range(dim):
for j in range(i+1,dim):
if position[i] == position[j]: #在同一列的情況
return False
if abs(position[i]-position[j]) == abs(i-j): #在同一個對角線的情況
return False
return True
def eight_queen():
solution_count = 0
for c1 in range(0,8):
for c2 in range(0,8):
for c3 in range(0,8):
for c4 in range(0,8):
for c5 in range(0,8):
for c6 in range(0,8):
for c7 in range(0,8):
for c8 in range(0,8):
if is_valid([c1,c2,c3,c4,c5,c6,c7,c8]):
solution_count+=1
else:
pass
return solution_count
print("八皇後解法總數:",eight_queen())def is_valid(position): 最後程式輸出解法總數為92。
這裡有必要解釋一下is_valid函數，該函數判斷給定的8個棋子布局是否滿足題目中的要求，也就是不能互相攻擊。
大家需要注意的是，eight_queen(）程式中，傳遞給is_valid函數的[c1,c2,c3,c4,c5,c6,c7,c8] 代表了第一行在第c1列放皇後，第二行在第c2列放皇後，第三行在第c3列放皇後，以此類推。
也就是說，這種擺法已經避免了出現2個皇後 在同一行的局面。
是以，is_valid函數主要判斷這8個皇後的位置是否在同一列，或者同一條斜線上。
判斷兩個棋子是否在同一列比較簡單，隻需要判斷position[i]是否等于position[j]即可。
那麼，如何判斷兩個棋子是否在同一條斜線上呢？我們探索一些在同一斜線的情形：
圖1-向右下方的斜線
圖2-向右上方的斜線
一共有兩種情況，一種是向右下方的斜線，一種向右上方的斜線。
看看向右下方的斜線，
圖3-點P右下方的斜線
假設第一個皇後的位置是P，其坐标為(i,j),則向下傾斜時，該斜線上下一個位置的坐标是(i+1,j+1），第二個位置的坐标是（i+2,j+2）,不失一般性，第n個位置的坐标是（i+N,j+N）
從上可知，點P和與其在一條斜線上的點K的坐标分别是（i,j),(i+k,j+k)，下面嘗試找到這兩個位置的坐标有什麼關聯，也就是找這些幾個整數的關聯，我們從加減乘除的角度來考慮。
先試着把二者的坐标進行相加，得到：
x坐标相加得到結果X= i+i+k = 2*i + k
y坐标相加得到結果Y= j+j+k = 2*j + k
發現2個結果都有k,基于直覺，把二者相減，得到2*（j-i）,猜測，是否Y-X是(j-i)的倍數，就說明二者在一條斜線上呢？很可惜猜錯了，例如點（4,2）和（6,6），二者雖然不在一條斜線上，卻有Y-X=2 ，是點（4，2）的y和x的內插補點的倍數。
看起來加法的嘗試失敗了。
減法呢？P和K這兩點的X和Y坐标分别相減，得到
（i+k-i, j+k-j）= (k,k)，就是說減法得到的結果，其X和Y值相等。
我們試了幾個不在這條斜線上的點，發現這些點的值與P的x和y坐标相減，得到的X和Y确實不相等，是以，我們認推測如果某點Q(m,n)在（i,j）所在的向下斜線上，其x和y坐标值和點P的x,y坐标值相減後，m-i = n-j，即X和Y相等。
本結論實際上也很容易證明。
假設一個點Q在從P開始的從左到右向下傾斜的線上，其坐标表示為(i+k,j+k)，由于這個斜線與Q所在的行隻有Q一個交點（兩條直線最多一個交點），隻需要證明Q所在行的其他點不滿足X=Y即可。
不失一般性，假設與Q在同一行的另一個點S的坐标是(i+k,j+m）,這裡m≠k（否則S和Q是同一個點），則S和P坐标相減後，X=i+k-i=k, Y=j+m-j=m，由于剛才的結論m≠k，得到X≠Y。
到這裡，可以得到如下結果：
結論①：一個點K的坐标x和y分别減去P的坐标x和y，如果相等，則說明K在從P出發向右下方傾斜的斜線上。
下面研究向右上方傾斜的斜線。
圖4-點P向右上方的直線
我們發現K-P的結果是(k,-k),x和y坐标相反，大家也可以結合前面的分析，驗證這個結論：
結論②：一個點K的坐标x和y分别減去P的坐标x和y，如果結果相反，則說明K在從P出發從左到右向上傾斜的斜線上。
彙總結論①和②，得到如下結論：
結論③：一個點K的坐标x和y分别減去P的坐标x和y，如果絕對值相等，則說明K在從P出發的斜線上。
注意：這裡斜線的斜率都是±1（八皇後題目中限制了斜率為±1）
條件判斷代碼很好寫，如下：
if abs(position[i]-position[j]) == abs(i-j): #在同一條斜線的情況
return False 下面我們看下主流程代碼：
solution_count = 0
for c1 in range(0,8):
for c2 in range(0,8):
for c3 in range(0,8):
for c4 in range(0,8):
for c5 in range(0,8):
for c6 in range(0,8):
for c7 in range(0,8):
for c8 in range(0,8):
if is_valid([c1,c2,c3,c4,c5,c6,c7,c8]):
solution_count+=1
else:
pass 同樣分析，這段代碼很容易了解，但是擴充性上就很差了。如果問題改成100個皇後，就得改成100重循環，這可是很大的工作量，更主要的是，代碼顯得太醜陋了。
有什麼解決辦法呢？
我們這樣分析，假設第一行已經放好了一個皇後（這個皇後放哪個列無所謂）。那麼，剩下的七個皇後實際上也要滿足“不能處于同一行、同一列或同一斜線上”的條件，也就是說假設我們有個eight_queen_2函數，實作了八皇後的解法，那麼該函數同樣也能夠實作剩下的七皇後問題，就是說我們完全可以複用這個eight_queen2函數來完成剩下的七皇後問題，這也是遞歸的常見用法。
那麼，這裡的七皇後和八皇後的問題有什麼聯系呢？七皇後除了滿足自身的七個皇後不在同一行、同一列或同一斜線上的條件外，唯一的聯系就是這七個皇後不能和第一行的皇後在同一行、同一列或者統一斜線上。于是，我們得到的遞歸實作如下：
'''八皇後問題'''
occupied=[]
dim =8
solutions = 0
def is_valid(x,y,occupied):
global dim
for pos in occupied:
if pos[1] == y or abs(x-pos[0])==abs(y-pos[1]):
return False
return True
def sol_eight_queen(cur_row):
global occupied,solutions
if cur_row >= dim:
solutions+=1
return True
for j in range(dim):
if is_valid(cur_row,j,occupied):
occupied.append([cur_row,j])
sol_eight_queen(cur_row+1)
del occupied[-1]
def test_eight_queen():
sol_eight_queen(0)
print("total valid answers is:",solutions) 運作test_eight_queen()函數，程式輸出為92。
下面我們看看代碼。判斷布局是否符合要求的代碼見is_valid程式，代碼比較容易了解，這裡不再詳細介紹。
核心是sol_eight_queen(cur_row）程式。
其中，global eight_queen,occupied,dim,solutions定義了一些全局變量，用全局變量大多數時候不是很好的程式設計習慣，筆者這裡為了簡化代碼編寫采用了全局變量的方式。occupied儲存了從第1行到目前行的王後擺放位置。solutions儲存了可以成功擺放8個王後的布局數，也就是我們要求的結果。
if cur_row == dim:
solutions += 1
return True 這裡是遞歸退出條件，可以了解成當擺放到棋盤的第9行時，認為前面已經成功拜訪完畢前8行的王後。為此我們将solution加1。
for j in range(dim):
if is_valid(cur_row,j,occupied):
occupied.append([cur_row,j])
sol_eight_queen(cur_row+1)
del occupied[-1] 這一段代碼是核心邏輯。
for j in range(dim):
意味着我們對于目前行cur_row的每一列，執行下面的操作：
首先通過is_valid(cur_row,j,occupied)來判斷在第cur_row行的第j列擺放王後，是否和之前擺放的王後沖突，如果沖突，則繼續判斷第j+1列；如果不沖突，則調用如下三行代碼：
occupied.append([cur_row,j])
sol_eight_queen(cur_row+1)
del occupied[-1] 通過occupied.append([cur_row,j])表明本行我們在（cur_row,j）位置擺放王後，然後遞歸調用sol_eight_queen(cur_row+1)進入下一行，也就是cur_row+1行；遞歸調用結束後，需要清理現場，也就是這裡的del occupied[-1],即删除occupied數組中的最後一個元素。為什麼呢？
如果不把[cur_row,j]這個位置的王後拿走，大家可以想象，後續放王後時相當于憑空多了這個不應該存在的限制條件，導緻程式無解。大家可以自行删除del occupied[-1]後再運作，程式輸出解的個數為0。
到這裡，讓我們暫停下，首先整理一下遞歸和循環的關系：
一、遞歸程式本身相當于1個循環，像這種：
factorial(n) = n*factorial(n-1) 等價于：
result =1
for i in range(1,n+1):
result *= i 二、2個遞歸調用，相當于順序執行2個循環，例如：
factorial(n)+factorial(k) 三、一個循環内部調用了遞歸，例如上述的八皇後問題，則相當于N重循環。再例如下面的檔案夾周遊程式：
import os
def browser_dir(rootDir):
for lists in os.listdir(rootDir):
path = os.path.join(rootDir, lists)
if os.path.isfile(path):
print(path)
else:
browser_dir(path) 可以看出，循環内調用遞歸可以等價于多重循環的效果。大家自己寫下代碼好好體會下。
四、多重循環内部調用了遞歸，常見于圖相關類型的題目，例如：
有一個H*W大小的遊戲闆，由黑白兩種格子組成。現要用3個機關格子的L狀闆塊把白色格子全部覆寫掉。闆塊可以自由旋轉，但不能重疊覆寫黑色格子，或超出遊戲版。
基本上能遇到的就是這些了，大家要銘記的是對于不同的題目，應用不同的循環+遞歸的政策。
建議大家好好體會下
for j in range(dim):
if is_valid(cur_row,j,occupied):
occupied.append([cur_row,j])
sol_eight_queen(cur_row+1)
del occupied[-1] 這段代碼，一個循環，一個進入下層遞歸的條件，同時注意恢複現場。