[Algorithm] 使用遞迴解八皇后 (8-queen) 問題

[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) 問題

 

(本頁面已被瀏覽過 2,807 次)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料