[Algorithm] 使用遞迴解八皇后 (8-queen) 問題
最近在重讀資料結構和演算法的書…
其實以前在學校裡學資料結構和演算法時,就覺得自己學得不是很好,
然後又看到了 Homebrew 作者去 Google 面試被刷下來的新聞,
覺得還是得好好的去補修一下學分才是…
(話說我好像也沒學過反轉二元樹啊… 是我蹺掉的課嗎? =_=)
在書裡看到了可以用堆叠 (stack) 來解八皇后的問題,
直覺來說,應該會先想到用遞迴的方式來解決 (當然遞迴事實上也用到堆叠就是了…)~
就用 python 來實作一個 N-皇后的程式吧~
首先定義一個 Queen 的類別,這個部分其實可有可無,因為目前裡面只放一個位置的資訊,
但如果之後裡面還會放上皇后的圖案或不同屬性的話,用個 class 來放還是比較方便:
class Queen(object): def __init__(self, pos): self.pos = pos def __repr__(self): return str(self.pos)
接著定義一個棋盤的 Board 類別,先記錄棋盤的大小:
class Board(object): def __init__(self, num_row): self._num_row = num_row
重點的解題部分交給 solve() 函式,它本身則是呼叫一個遞迴的 _solve() 函式,
如果 queen_list 已經擺滿了所有的皇后,那就印出來後結束,
否則就會試著在目前的橫列中,找一個可以放的位置,
接著再遞迴呼叫 _solve() 讓它把剩下幾個橫列的位置都找出來:
def solve(self): return self._solve([]) def _solve(self, queen_list): print "Trying", queen_list # Check if all queens are placed if len(queen_list) >= self._num_row: print "Solution", queen_list sys.exit(0) # Select a position for next queen, # recursive for the rest. for pos in xrange(self._num_row): queen = Queen(pos) if self._can_place(queen, queen_list): self._solve(queen_list+[queen])
至於怎樣叫可以擺的位置呢?
八皇后的規則,如果是 N*N 的棋盤,那就會有 N 個皇后,所有的皇后都得放在棋盤上,
但不能有任兩個皇后出現在同一直行、橫列、或對角線上~
我們當然不會蠢到在同一橫列上擺兩個皇后,
因此每次擺新的皇后,一定是在下一個橫列上找個位置放,
因此我的 queen_list 是記錄第 0 列開始,每個皇后所在的行數,
計算對角線也很簡單,上一列的話看看行數是不是目前位置的 +-1,
上兩列的話看看行數是不是目前位置的 +-2,以此類推:
def _can_place(self, queen, queen_list): for (i, existing_queen) in enumerate(reversed(queen_list)): # Check if there are other queens with same x-axis if existing_queen.pos == queen.pos: return False # CHeck if there are other queens on the diagonal lines if existing_queen.pos in (queen.pos-(i+1), queen.pos+(i+1)): return False return True
這邊是完整的程式:
#!/usr/bin/env python import sys class Queen(object): def __init__(self, pos): self.pos = pos def __repr__(self): return str(self.pos) class Board(object): def __init__(self, num_row): self._num_row = num_row def solve(self): return self._solve([]) def _solve(self, queen_list): print "Trying", queen_list # Check if all queens are placed if len(queen_list) >= self._num_row: print "Solution", queen_list sys.exit(0) # Select a position for next queen, # recursive for the rest. for pos in xrange(self._num_row): queen = Queen(pos) if self._can_place(queen, queen_list): self._solve(queen_list+[queen]) def _can_place(self, queen, queen_list): for (i, existing_queen) in enumerate(reversed(queen_list)): # Check if there are other queens with same x-axis if existing_queen.pos == queen.pos: return False # CHeck if there are other queens on the diagonal lines if existing_queen.pos in (queen.pos-(i+1), queen.pos+(i+1)): return False return True if __name__ == "__main__": board = Board(8) board.solve()
我們在程式裡印出 queen_list 的改變過程,可以看到長度會突然縮回去,
像是我們擺了 0, 2, 4, 1, 7 這個位置之後,發現下一列上不管擺哪裡都會衝到,
因此會回到上一層的遞迴,將前一個皇后 (本例中為位置 1) 的位置改變再試試看,
這也是一種稱為 backtracking 的方式:
Trying [] Trying [0] Trying [0, 2] Trying [0, 2, 4] Trying [0, 2, 4, 1] Trying [0, 2, 4, 1, 3] Trying [0, 2, 4, 1, 7] Trying [0, 2, 4, 6] Trying [0, 2, 4, 6, 1] Trying [0, 2, 4, 6, 1, 3] Trying [0, 2, 4, 6, 1, 3, 5] Trying [0, 2, 4, 6, 3] Trying [0, 2, 4, 7] Trying [0, 2, 4, 7, 1] Trying [0, 2, 4, 7, 1, 3] Trying [0, 2, 4, 7, 1, 3, 5] Trying [0, 2, 4, 7, 3] Trying [0, 2, 5] Trying [0, 2, 5, 1] Trying [0, 2, 5, 1, 6] Trying [0, 2, 5, 1, 6, 4] Trying [0, 2, 5, 7] Trying [0, 2, 5, 7, 1] Trying [0, 2, 5, 7, 1, 3] Trying [0, 2, 5, 7, 1, 4] Trying [0, 2, 6] Trying [0, 2, 6, 1] Trying [0, 2, 6, 1, 3] Trying [0, 2, 6, 1, 3, 7] Trying [0, 2, 6, 1, 7] Trying [0, 2, 6, 1, 7, 4] Trying [0, 2, 7] Trying [0, 2, 7, 1] Trying [0, 2, 7, 1, 3] Trying [0, 2, 7, 1, 6] Trying [0, 2, 7, 5] Trying [0, 2, 7, 5, 1] Trying [0, 2, 7, 5, 3] Trying [0, 2, 7, 5, 3, 1] Trying [0, 2, 7, 5, 3, 1, 4] Trying [0, 3] Trying [0, 3, 1] Trying [0, 3, 1, 4] Trying [0, 3, 1, 4, 2] Trying [0, 3, 1, 4, 7] Trying [0, 3, 1, 6] Trying [0, 3, 1, 6, 2] Trying [0, 3, 1, 7] Trying [0, 3, 1, 7, 2] Trying [0, 3, 1, 7, 2, 6] Trying [0, 3, 1, 7, 5] Trying [0, 3, 1, 7, 5, 2] Trying [0, 3, 5] Trying [0, 3, 5, 2] Trying [0, 3, 5, 7] Trying [0, 3, 5, 7, 1] Trying [0, 3, 5, 7, 1, 4] Trying [0, 3, 5, 7, 1, 4, 2] Trying [0, 3, 5, 7, 1, 6] Trying [0, 3, 5, 7, 1, 6, 2] Trying [0, 3, 5, 7, 2] Trying [0, 3, 5, 7, 2, 4] Trying [0, 3, 5, 7, 2, 6] Trying [0, 3, 6] Trying [0, 3, 6, 2] Trying [0, 3, 6, 2, 5] Trying [0, 3, 6, 2, 5, 1] Trying [0, 3, 6, 2, 5, 1, 4] Trying [0, 3, 6, 2, 7] Trying [0, 3, 6, 2, 7, 1] Trying [0, 3, 6, 2, 7, 1, 4] Trying [0, 3, 6, 4] Trying [0, 3, 6, 4, 1] Trying [0, 3, 6, 4, 2] Trying [0, 3, 6, 4, 7] Trying [0, 3, 6, 4, 7, 1] Trying [0, 3, 7] Trying [0, 3, 7, 2] Trying [0, 3, 7, 4] Trying [0, 3, 7, 4, 1] Trying [0, 3, 7, 4, 2] Trying [0, 4] Trying [0, 4, 1] Trying [0, 4, 1, 5] Trying [0, 4, 1, 5, 2] Trying [0, 4, 1, 5, 2, 6] Trying [0, 4, 1, 5, 2, 6, 3] Trying [0, 4, 1, 7] Trying [0, 4, 1, 7, 2] Trying [0, 4, 1, 7, 2, 6] Trying [0, 4, 1, 7, 2, 6, 3] Trying [0, 4, 1, 7, 5] Trying [0, 4, 1, 7, 5, 2] Trying [0, 4, 1, 7, 5, 3] Trying [0, 4, 6] Trying [0, 4, 6, 1] Trying [0, 4, 6, 1, 3] Trying [0, 4, 6, 1, 3, 7] Trying [0, 4, 6, 1, 5] Trying [0, 4, 6, 1, 5, 2] Trying [0, 4, 6, 1, 5, 7] Trying [0, 4, 7] Trying [0, 4, 7, 1] Trying [0, 4, 7, 1, 3] Trying [0, 4, 7, 1, 3, 6] Trying [0, 4, 7, 1, 3, 6, 2] Trying [0, 4, 7, 1, 6] Trying [0, 4, 7, 1, 6, 2] Trying [0, 4, 7, 1, 6, 2, 5] Trying [0, 4, 7, 5] Trying [0, 4, 7, 5, 2] Trying [0, 4, 7, 5, 2, 6] Trying [0, 4, 7, 5, 2, 6, 1] Trying [0, 4, 7, 5, 2, 6, 1, 3] Solution [0, 4, 7, 5, 2, 6, 1, 3]
當 N 是 16 時,程式不到一秒就能結束,
但 N 是 32 時,就要跑非常久了 (這種實作法的時間複雜度是 O(N^N)),
因此在 N 比較大的時候,應該是得找其他的演算法來試試看囉…
PS: 非遞迴版本可以參考 使用堆叠解八皇后 (8-queen) 問題