八皇后問題描述

問題： 國際象棋棋盤是8 * 8的方格，每個方格里放一個棋子。皇后這種棋子可以攻擊同一行或者同一列或者斜線（左上左下右上右下四個方向）上的棋子。在一個棋盤上如果要放八個皇后，使得她們互相之間不能攻擊（即任意兩兩之間都不同行不同列不同斜線），求出一種（進一步的，所有）布局方式。

首先，我們想到遞歸和非遞歸兩類算法來解決這個問題。首先說說遞歸地算法。

很自然的，我們可以基于行來做判斷標準。八個皇后都不同行這是肯定的，也就說每行有且僅有一個皇后，問題就在于皇后要放在哪個列。當然八個列下標也都不能有相同，除此之外還要保證斜線上不能有重疊的皇后。

第一個需要解決的小問題就是，如何用數學的語言來表述斜線上重疊的皇后。其實我們可以看到，對于位于(i,j)位置的皇后而言，其四個方向斜線上的格子下標分別是 (i-n,j+n), (i-n,j-n), (i+n,j-n), (i+n,j+n)。當然i和j的±n都要在[0,7]的范圍內，保持不越界。暫時拋開越界限制不管，這個關系其實就是： 目標格子(a,b)和本格子(i,j)在同一條斜線上 等價于 |a - i| == |b - j| 。

然后，從遞歸的思想來看，我們在從第一行開始給每一行的皇后確定一個位置。每來到新的一行時，對本行的所有可能位置（皇后放在這個位置和前面所有已放置的皇后無沖突）分別進行遞歸地深入；若某一行可能的位置數為0，則表明這是一條死路，返回上一層遞歸尋找其他辦法；若來到的這一行是第九行（不存在第九行，只不過是說明前八行都已經正確配置，已經得到一個解決方案），這說明得到解決方案。

可以看到，尋找一行內皇后應該擺放的位置這是個遞歸過程，并且在進入遞歸時，應該要告訴這個過程的東西包括兩個： 1. 之前皇后放置的狀態， 2. 現在是第幾行。

所以，遞歸主體函數可以設計為 EightQueen(board, row)，其中board表示的是當前棋盤的狀態（比如一個二維數組，0表示未放置，1表示放有皇后的狀態）。另外還可以有一個check(board,pos)，pos可以是一個(x,y)元組，check函數用來返回以當前的board棋盤狀態，如果在pos再放置一個皇后是否會有沖突。

基于上面的想法，初步實現如下：

def check(board,pos): # check函數暫時先不實現 passdef EightQueen(board,row): blen = len(board) if row == blen: # 來到不存在的第九行了  print board  return True # 一定要return一個True，理由在下面 for possibleY in range(blen):  if check(board,(row,possibleY)):   board[row][possibleY] = 1 # 放置一個Queen   if not EightQueen(board,row+1): # 這里其實是本行下面所有行放置皇后的遞歸入口。但是如果最終這條路沒有找到一個解，那么    # 此時應該將剛才放置的皇后收回，再去尋找下一個可能的解    board[row][possibleY] = 0   else:    return True return False