[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 吧)~
(本頁面已被瀏覽過 563 次)