[ Algorithm ] 8 puzzle problem with Historical and Heuristic solution

前言 :
因為上完 AI 後, 對 8 puzzle 的問題念念不忘, 就在想怎麼解這個問題. 在下面的 "補充說明" 的 8 puzzle game 使用 A* search 的解法, 另外還有使用 "manhattan approach" 的方法. 但這邊我使用了更直覺的方法, 使用 heuristic 與 historical 的組合, 找出可能的路徑.

方法說明 :
首先第一步便是 puzzle 的 representation 的問題, 這邊我使用 number sequence 來代表, 當兩個 sequence 相等, 我便可以認定這兩個 puzzles 是相同的, 至於如何對應 puzzle 到 number sequence, 可以參考下面圖示:


第一所謂的 historical 就是我從答案往回推 n 步, 並找出所有可能的 path 可以到達的組合. 因此當我在解問題時當目前的 puzzle 的 sequence 有 hit 到這些 historical 走到的 puzzle 的 sequence, 我們便可以依據 historical 告訴我們怎麼走回去到答案(Goal).

第二所謂的 heuristic, 就是如何從 Initial State 走到 historical 看過的解法或 State, 這邊我使用 Breadth-First Search 去找所有從目前的 State 可以走得到的 State, 一直到找到 historical 看過的 sequence 為止, 如此我們便可以確認這個 algorithm 或是 Search 是 Complete 的!

上述的流程可以參考下面的 Flow:


代碼說明 :
根據上面的說明, 底下針對實作的部分進行使用的說明. 第一步便是產生 Historical answer path. 可以參考類別 c3.puzzle8.GenPS 的 main 函數:

view plaincopy to clipboardprint?

1. public static void main(String[] args) {  
2.     Puzzle p = new Puzzle(1, 2, 3, 4, 5, 6, 7, 8, 0);  // 決定表準答案的長相  
3.     // 1 | 2 | 3  
4.     // 3 | 5 | 6  
5.     // 7 | 8 | 0  
6.     System.out.printf("\t[Test] Puzzle:\n%s\n", p);  // 顯示 Puzzle 長相  
7.       
8.     Set pSet = new TreeSet();         
9.     for(int i=1; i<=13; i++)  
10.     {  
11.         pSet.clear();  
12.         GenPS(i, p, pSet);  // 所以第 i步走的到的 sequence 都會記錄到 pSet 中.  
13.         output(i, pSet);    // 將 第 i步的 sequences 輸出到檔案.  
14.         System.out.printf("===============%d===============\n", i);  
15.         p.restore();  
16.     }  
17. }  

執行後會產生一對 "?Step.txt" 檔案, 那個問號說明是第 ? 步可以走到的 sequence path. 如果是前一步 "1Step.txt" 內容會像:

#123456780->123450786
123450786
#123456780->123456708
123456708

也就是說只走一步, 可能的 Puzzle sequence 只有 "123450786" 與 "123456708".

接著便是如何在代碼定義 Puzzle 與執行, 代碼可以參考類別 c3.puzzle.Puzzle 的 main 函數:

view plaincopy to clipboardprint?

1. public static void main(String args[])  
2. {  
3.     // 7 | 2 | 4  
4.     // 5 | 0 | 6  
5.     // 8 | 3 | 1  
6.     //Puzzle p = new Puzzle(7,2,4,5,0,6,8,3,1);  
7.     Puzzle p = new Puzzle("132406578");  
8.     p.answerSeq = "123456780"; // 決定  Goal 或是  Answer 的 sequence.  
9.     p.answer(100);  // 最多只跑 100 步.  
10.   
11. }  

執行結果如下:

[Test] Load in 823880 history steps... # 共載入 823880 historical sequence paths
1 3 2
4 0 6
5 7 8
132406578

[Test] Suggest path='21' with cost=14! # 使用 BFS 找到最接近的 Historical Sequence
1 0 2
4 3 6
5 7 8

0 1 2
4 3 6
5 7 8

4 1 2
0 3 6
5 7 8
...(略)...

1 2 3
4 5 6
7 8 0

Done(14)! # 共花了 14 步.

問題說明 :
這個方法還是有幾個缺點, 一是如果你的 Goal/Answer 變動時, 你就要從跑一次 Historical 的結果; 再來是在使用 heuristic 去找 historical path 時基本上是暴力解法 ><".
另外我們可以堆算 puzzle 所有可能的 sequence 會是 9!. 也就是說如果在產生 Historical 的 paths 時, 到某 n 步時所有 paths 的總數等於 9!, 我們便可以大膽說最多只要走 n 步, 一定可以回到 Goal. 這時候的問題便是秒殺了 ^^".
最後整個專案代碼可以到 這裡 下載.

補充說明 :
* What is 8 puzzle?

The 8 puzzle is a simple game which consists of eigth sliding tiles, numbered by digits from 1 to 8, placed in a 3x3 squared board of nine cells. One of the cells is always empty, and any adjacent (horizontally and vertically) tile can be moved into the empty cell. The objective of the game is to start from an initial configuration and end up in a configuration which the tiles are placed in ascending number order...

* 8 puzzle game

The 8-puzzle - also known as the sliding-block puzzle or tile-puzzle - is one of the most popular instruments in the artificial intelligence (AI) studies. It belongs to AI exercises commonly referred as toy-problems...

* Java source code for 8 puzzle solution using manhattan approach

The following java example shows how to solve a 8 puzzle problem by using manhattan approach...

This message was edited 20 times. Last update was at 04/10/2012 10:46:31