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

2016-07-05 ephrain Comments 0 Comment

最近在重讀資料結構和演算法的書…

其實以前在學校裡學資料結構和演算法時，就覺得自己學得不是很好，

然後又看到了 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,774 次)

EPH 的程式日記

記錄程式設計生活的點點滴滴

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

2016-07-05 ephrain Comments 0 Comment

發佈留言取消回覆

發佈留言 取消回覆

發佈留言取消回覆