## 2012年10月3日 星期三

### [ Algorithm ] 8 puzzle problem with Historical and Heuristic solution

1. public static void main(String[] args) {
2.     Puzzle p = new Puzzle(123456780);  // 決定表準答案的長相
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. }

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

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");
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 步.

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

### [ FP In Python ] Ch4. Higher-Order Functions

Preface   In the  last chapter  we saw an iterator algebra that builds on the  itertools  module. In some ways,  higher-order functions  (...