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

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

之前用遞迴解八皇后 (8-queen) 問題,基本上遞迴應該都能改成某種非遞迴型式,

就來試試教科書上原本建議的堆叠 (stack) 吧~

 

程式大體和原本遞迴版的差不多,只是將 solve() 和 _solve() 合併了,

改成了不用遞迴的版本:

    def solve(self):
queen_list = []
is_backtracking = False
backtracking_queen_pos = -1
try:
while True:
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
is_backtracking = True
for pos in xrange(backtracking_queen_pos+1, self._num_row):
queen = Queen(pos)
# If a position is found, next iteration won't do backtracking.
if self._can_place(queen, queen_list):
queen_list.append(queen)
is_backtracking = False
backtracking_queen_pos = -1
break
# If no position could be found for next queen,
#   pop up last queen, so that we may continue with another position.
if is_backtracking:
backtracking_queen_pos = queen_list.pop().pos
except IndexError:
# When no solution could be found, at last queen_list would become [],
#   and queen_list.pop() would raise IndexError
print "No solution could be found!"

 

可以看到程式裡面用了一個 is_backtracking 的旗標,

假設我們沒辦法為下一個皇后找到位置放的話,

就將最後一個皇后取出來,試著將它的位置往右移動看看,

如果這樣也不行,迴圈就會不斷地將最後一個皇后拿出來,移動它的位置,

等到全都拿出來後也找不到適當位置放的時候,就算是失敗了~

 

從程式可以看出來非遞迴版本的比較複雜,也比較不太容易理解,

不過通常效率是會比較好的喔 (應該是因為少了遞迴函式呼叫的 overhead 吧)~

 

(本頁面已被瀏覽過 286 次)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

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