C# 用BFS解8-Puzzle問題

之前因為8-Puzzle問題卡了一段時間,之後才了解其實用BFS解的話,難度就降到跟解迷宮差不多了。

 

前言

先來簡單的介紹一下什麼是8-Puzzle。

數字推盤遊戲(n-puzzle)是最早一種的滑塊類遊戲,常見的類型有十五數字推盤遊戲和八數字推盤遊戲等。也有以圖畫代替數字的推盤遊戲。

如上圖所示,滑塊只能往空位移動。

大概了解遊玩方法後,就來試著解決8-Puzzle問題吧!

 

解法的步驟大概是這樣 :

  1. 先完成移動判斷和節點狀態的儲存結構
  2. 用BFS窮舉狀態,並把當前狀態記錄下來篩選重複路徑
  3. 只要有一組路徑符合結果,該路徑就是最佳解(因BFS的特性)
  4. 否則搜尋完畢後皆沒有找到符合的狀態,無解
  5. 最後透過父節點的回溯取得輸出路徑,即可得到最短路徑和分解步驟

 

儲存結構和移動判斷

首先是儲存狀態,用二維陣列來儲存比較直觀,但是用一維陣列來儲存的話,我覺得在一些處理上比較方便,所以我採用一維陣列。

像是上面的這個狀態這樣,將0表示為空格,可以儲存成 { 8, 6, 4, 0, 7, 2, 5, 1, 3}。

 

因為要透過BFS搜尋來取得路徑,所以需要建立一個節點的結構,這樣才能儲存當前狀態,並紀錄上個狀態 :

 

再來是移動判斷,滑塊在移動時,可以看成是空白方塊在移動。

如上圖,0 可以往上、右、下移動,但是不能往左,那麼要如何判斷0能往哪個方向走呢?

 

如上圖,當 index = 3 時,可以得知在二維時座標是 (0, 1)。

 

能取得對應位置後,就能夠寫出移動判斷,像是當空位在最左邊時Col = 0,那麼就不能往左走,因為在最左邊了,在最下面時Row = 2,不能往下走,因為已經到底了。

所以可以得出:

  • Col != 0,可以往左走
  • Col != 2,可以往右走
  • Row != 0,可以往上走
  • Row != 2,可以往下走

 

但是只有判斷能不能走還不夠,因為當空格移動時,必須跟那個位置的數字交換,並記錄下原本的狀態 :

在交換前要先複製一份,因為陣列參數是傳參考,直接交換會修改到原本的狀態,所以要先Clone後再傳給新狀態做交換。

而上面程式碼中 new Node(next, now),意思是建立一個新節點next,而他的前一個狀態是剛剛傳進來的now。

如上圖,假設now是根結點,而next是下個節點,那麼new Node(next, now)後就會像這樣。

 

 

用BFS窮舉狀態

有了移動判段後,接下來的解法就跟用BFS解迷宮差不多了 :

路徑的儲存使用SortedList而不是正常的List,因為List在加入物件時並不會特別處理,所以在搜尋時就只能慢慢比較,而SortedList的結構類似二元搜尋樹,在新增資料時就會依照設定的Key值做排序後再插入,所以在搜尋時的複雜度就能夠降到O(log2 n),想了解更多的話請看最後的參考資源。

到這邊大概就能了解為什麼要用ToSequence()來儲存路徑了,因為資料不會重複,所以搭配SortedList就比List快的多。

 

使用方法:

給定原本面狀態跟輸出狀態,即可得到最短路徑的List,而輸出路徑只要走訪一遍Path即可得到。

 

其實執行的原理很簡單,就是一直窮舉所有狀態,直到符合結果為止

 

測試結果

 

雖然用BFS就能解了,但效率很差,之後會再研究看看A*演算法。

 

如有錯誤請指證

 

參考資源:

What’s the difference between SortedList and SortedDictionary? : here

SortedList<TKey, TValue> Class : here

各Collection陣列個別特性列表 : here

樹搜尋、回溯與分支定界- 國立中央大學課程簡報 : here

Solvability of the Tiles Game : here

8-Puzzle : here

ACM 15-puzzle : here

Inndy GitHub : here

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *