C# 用BFS解8-Puzzle問題

Posted on: 2018-03-21 /
Categories: 程式筆記

之前因為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搜尋來取得路徑，所以需要建立一個節點的結構，這樣才能儲存當前狀態，並紀錄上個狀態 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Node
{
    public byte[] status; // 當前狀態
    public Node father; // 紀錄上個狀態，如果father = null 該點為根節點
    public Node(byte[] status, Node father)
    {
        this.status = status;
        this.father = father;
    }
 
    // 把陣列轉換成數字序列，比對時就不用兩將陣列元素一一檢查了
    // 像是 stauts = {8, 6, 4, 0, 7, 2, 5, 1, 3}，轉後後即可得到864072513
    public int ToToSequence()
    {
        int result = 0;
        for (int i = 0; i < status.Length; i++)
            result = result * 10 + status[i];
        return result;
    }
}

 

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

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

 

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

 

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

所以可以得出:

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

 

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
List<Node> GetNext(Node now)// 傳入當前版面，回傳0所有移動後的狀態
{
    int index = Array.IndexOf<byte>(now.status, 0);
    int col = index % 3;
    int row = index / 3;
 
    List<Node> nextPush = new List<Node>();
    byte[] next;
 
    if (row != 0) // Top
    {
        next = (byte[])now.status.Clone();        
        swap(ref next[index], ref next[index - 3]);// 跟上面交換        
        nextPush.Add(new Node(next, now));// 加入這個新狀態
    }
 
    if (col != 2) // Right
    {
        next = (byte[])now.status.Clone();        
        swap(ref next[index], ref next[index + 1]);// 跟右邊交換
        nextPush.Add(new Node(next, now));
    }
 
    if (row != 2) // Bottom
    {
        next = (byte[])now.status.Clone();        
        swap(ref next[index], ref next[index + 3]);// 跟下面交換
        nextPush.Add(new Node(next, now));
    }
 
    if (col != 0) // Left
    {
        next = (byte[])now.status.Clone();        
        swap(ref next[index], ref next[index - 1]);// 跟左邊交換
        nextPush.Add(new Node(next, now));
    }
    return nextPush;
}

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

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

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

 

 

用BFS窮舉狀態

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 傳入原本的版面和目標版面，回傳最短路徑
List<Node> Solve(byte[] source, byte[] goal)
{
    Queue<Node> queue = new Queue<Node>();
 
    // 使用狀態序列來儲存已走過的路徑，防止往回走
    SortedList<int, bool> book = new SortedList<int, bool>();
 
    Node end = new Node(goal, null);// 終點
    Node start = new Node(source, null);// 起點
 
    queue.Enqueue(start);// 推入起點
    book.Add(start.ToSequence(), true);// 標示起點已走過，防止走回頭路
 
    int endStatus = end.ToSequence();
    while (queue.Count > 0)
    {
        // 取得當前搜索狀態，並移出佇列
        Node now = queue.Dequeue();
 
        // 如果抵達終點，那就輸出路徑
        if (now.ToSequence() == endStatus)
            return PathTrace(now);
 
        // 取得能走的位置
        List<Node> nextPath = GetNext(now);                                
        foreach (var path in nextPath)
        {
            int sign = path.ToSequence();
 
            // 判斷當前節點狀態是否擴展過了
            if (!book.Keys.Contains(sign))
            {
                // 推入當前狀態，並標記該路徑已走過，因為每個狀態只需要擴展一次就夠了                
                queue.Enqueue(path);
                book.Add(sign, true);
            }
        }
    }
 
    // 如果窮舉完都沒找到，代表無解
    return null;
}
 
List<Node> PathTrace(Node now)
{
    // 回朔路徑
    List<Node> path = new List<Node>();
    while (now.father != null)
    {
        path.Add(now);
        now = now.father;
    }
    path.Reverse();
    return path;
}

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

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

 

使用方法:

1
2
3
4
5
6
byte[] source = new byte[] { 8, 6, 4, 0, 7, 2, 5, 1, 3 };
byte[] goal = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
 
List<Node> path = Solve(source, goal);
 
Console.WriteLine($"最少步驟為:{path.Count}");

給定原本面狀態跟輸出狀態，即可得到最短路徑的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

2 comments

  • 火柴

    厲害!

    比對的時候可以試試看使用 Hash
    例如內建的 HashSet 等，效能應該就會很快喔

    A* 在這種情形下可能會比較麻煩
    要想出方法估計兩個狀態間的距離

    ( 畢竟是比賽 也很難當場做這麼多吧XD )

    加油~

發佈留言

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