[ InAction Note ] Ch1. Meet Lucene - A simple application

Lucene in action: a sample application : 
To show you Lucene’s indexing and searching capabilities, we’ll use a pair of command-line applications: Indexer and Searcher. First we’ll index files in a directory; then we’ll search the created index. Before we can search with Lucene, we need to build an index, so we start with our Indexer application. 

- Creating an index 
A simple class called Indexer, which indexes all files in a directory ending with the .txt extension. When Indexer completes execution, it leaves behind a Lucene index for its sibling, Searcher (presented next in section 1.4.2). After the annotated code listing, we show you how to use Indexer; if it helps you to learn how Indexer is used before you see how it’s coded, go directly to the usage discussion that follows the code. 

USING INDEXER TO INDEX TEXT FILES 
Listing 1.1 shows the Indexer command-line program, originally written for Erik’s introductory Lucene article on java.net. It takes two arguments: 

* A path to a directory where we store the Lucene index
* A path to a directory that contains the files we want to index

Listing 1.1 Indexer, which indexes .txt files 

view plaincopy to clipboardprint?

1. package ch1;  
2.   
3. import java.io.File;  
4. import java.io.FileFilter;  
5. import java.io.FileReader;  
6. import java.io.IOException;  
7.   
8. import org.apache.lucene.analysis.standard.StandardAnalyzer;  
9. import org.apache.lucene.document.Document;  
10. import org.apache.lucene.document.Field;  
11. import org.apache.lucene.index.IndexWriter;  
12. import org.apache.lucene.store.Directory;  
13. import org.apache.lucene.store.FSDirectory;  
14. import org.apache.lucene.util.Version;  
15.   
16. public class Indexer {  
17.     private IndexWriter writer;  
18.   
19.     private static class TextFilesFilter implements FileFilter {  
20.         public boolean accept(File path) {  
21.             // 6) Index .txt only.  
22.             return path.getName().toLowerCase().endsWith(".txt");  
23.         }  
24.     }  
25.   
26.     public Indexer(String indexDir) throws IOException {  
27.         Directory dir = FSDirectory.open(new File(indexDir));  
28.         // 3) Create Lucene IndexWriter.  
29.         writer = new IndexWriter(dir, new StandardAnalyzer(Version.LUCENE_30),  
30.                 true, IndexWriter.MaxFieldLength.UNLIMITED);  
31.     }  
32.       
33.     public void close() throws IOException {  
34.         // 4) Close IndexWriter  
35.         writer.close();  
36.     }  
37.       
38.     public int index(String dataDir, FileFilter filter) throws Exception {  
39.         File[] files = new File(dataDir).listFiles();  
40.         for (File f : files) {  
41.             if (!f.isDirectory() && !f.isHidden() && f.exists() && f.canRead()  
42.                     && (filter == null || filter.accept(f))) {  
43.                 indexFile(f);  
44.             }  
45.         }  
46.         return writer.numDocs(); // 5) Return the number of indexed docs.  
47.     }  
48.       
49.     protected Document getDocument(File f) throws Exception {  
50.         Document doc = new Document();  
51.         doc.add(new Field("contents", new FileReader(f))); // 7) Index file content.  
52.         doc.add(new Field("filename", f.getName(), Field.Store.YES, Field.Index.NOT_ANALYZED)); // 8) Index filename  
53.         doc.add(new Field("fullpath", f.getCanonicalPath(), Field.Store.YES, Field.Index.NOT_ANALYZED)); // 9) Index full path  
54.         return doc;  
55.     }  
56.       
57.     private void indexFile(File f) throws Exception {  
58.         System.out.println("Indexing " + f.getCanonicalPath());  
59.         Document doc = getDocument(f);  
60.         writer.addDocument(doc); // 10) Add doc to Lucene index  
61.     }  
62.       
63.     public static void main(String[] args) throws Exception {  
64.         if (args.length != 2) {  
65.             throw new IllegalArgumentException("Usage: java "  
66.                     + Indexer.class.getName() + " ");  
67.         }  
68.         String indexDir = args[0];  // 1) Create index in this directory  
69.         String dataDir = args[1];   // 2) Index *.txt from this directory  
70.         long start = System.currentTimeMillis();  
71.         Indexer indexer = new Indexer(indexDir);  
72.         int numIndexed;  
73.         try {  
74.             numIndexed = indexer.index(dataDir, new TextFilesFilter());  
75.         } finally {  
76.             indexer.close();  
77.         }  
78.         long end = System.currentTimeMillis();  
79.         System.out.println("Indexing " + numIndexed + " files took "  
80.                 + (end - start) + " milliseconds");  
81.     }  
82. }  

This example intentionally focuses on plain text files with .txt extensions to keep things simple, while demonstrating Lucene’s usage and power. In chapter 7, we’ll show you how to index other common document types, such as Microsoft Word or Adobe PDF, using the Tika framework. Before seeing how to run Indexer, let’s talk a bit about the Version parameter you see as the first argument to StandardAnalyzer. 

VERSION PARAMETER 
This class defines enum constants, such as LUCENE_24 and LUCENE_29, referencing Lucene’s minor releases. When you pass one of these values, it instructs Lucene to match the settings and behavior of that particular release. Lucene will also emulate bugs present in that release and fixed in later releases, if the Lucene developers felt that fixing the bug would break backward compatibility of existing indexes. For each class that accepts a Version parameter, you’ll have to consult the Javadocs to see what settings and bugs are changed across versions. It hows seriously the Lucene developers take backward compatibility. 

Let’s use Indexer to build our first Lucene search index! 

RUNNING INDEXER 
假設你在當前目錄下有目錄 ./data 要進行 Indexing (有文件 doc1.txt, doc2.txt), 並打算將 index 的結果放在 ./index. 可以使用如下代碼利用類別 Indexer 進行 Indexing: 

view plaincopy to clipboardprint?

1. package ch1;  
2.   
3. import ch1.Indexer.TextFilesFilter;  
4.   
5. public class IndexerEx1 {  
6.     public static void main(String[] args)  throws Exception{  
7.         String indexDir = "./index";    // 1) Create index in this directory  
8.         String dataDir = "./data";      // 2) Index *.txt from this directory  
9.         long start = System.currentTimeMillis();  
10.         Indexer indexer = new Indexer(indexDir);  
11.         int numIndexed;  
12.         try {  
13.             numIndexed = indexer.index(dataDir, new TextFilesFilter());  
14.         } finally {  
15.             indexer.close();  
16.         }  
17.         long end = System.currentTimeMillis();  
18.         System.out.println("Indexing " + numIndexed + " files took "  
19.                 + (end - start) + " milliseconds");  
20.   
21.     }  
22. }  

執行結果: 

Indexing C:\John\EclipseNTNUProj\LuceneLab\data\doc1.TXT
Indexing C:\John\EclipseNTNUProj\LuceneLab\data\doc2.TXT
Indexing 2 files took 223 milliseconds

In our example, each of the indexed files was small, but roughly 0.8 seconds to index a handful of text files is reasonably impressive. Indexing throughput is clearly important, and we cover it extensively in chapter 11. But generally, searching is far more important since an index is built once but searched many times. 

- Searching an index 
Searching in Lucene is as fast and simple as indexing; the power of this functionality is astonishing, as chapters 3, 5, and 6 will show you. For now, let’s look at Searcher, a command-line program that we’ll use to search the index created by Indexer. 

USING SEARCHER TO IMPLEMENT A SEARCH 
The Searcher program, originally written for Erik’s introductory Lucene article on java.net, complements Indexer and provides command-line searching capability. Listing 1.2 shows Searcher in its entirety. It takes two command-line arguments: 

* The path to the index created with Indexer
* A query to use to search the index

Listing 1.2 Searcher, which searches a Lucene index 

view plaincopy to clipboardprint?

1. package ch1;  
2.   
3. import java.io.File;  
4. import java.io.IOException;  
5.   
6. import org.apache.lucene.analysis.standard.StandardAnalyzer;  
7. import org.apache.lucene.document.Document;  
8. import org.apache.lucene.queryParser.ParseException;  
9. import org.apache.lucene.queryParser.QueryParser;  
10. import org.apache.lucene.search.IndexSearcher;  
11. import org.apache.lucene.search.Query;  
12. import org.apache.lucene.search.ScoreDoc;  
13. import org.apache.lucene.search.TopDocs;  
14. import org.apache.lucene.store.Directory;  
15. import org.apache.lucene.store.FSDirectory;  
16. import org.apache.lucene.util.Version;  
17.   
18. public class Searcher {  
19.     public static void search(String indexDir, String q) throws IOException, ParseException {  
20.         // 3) Open index  
21.         Directory dir = FSDirectory.open(new File(indexDir));  
22.         IndexSearcher is = new IndexSearcher(dir);  
23.           
24.         // 4) Parser query  
25.         QueryParser parser = new QueryParser(Version.LUCENE_30, "contents",  
26.                 new StandardAnalyzer(Version.LUCENE_30));  
27.         Query query = parser.parse(q);  
28.           
29.         // 5) Search index  
30.         long start = System.currentTimeMillis();  
31.         TopDocs hits = is.search(query, 10);  
32.         long end = System.currentTimeMillis();  
33.           
34.         // 6) Write search stat  
35.         System.err.println("Found " + hits.totalHits + " document(s) (in "  
36.                 + (end - start) + " milliseconds) that matched query '" + q  
37.                 + "':");  
38.           
39.         // 7) Retrieve matching docs  
40.         for (ScoreDoc scoreDoc : hits.scoreDocs) {  
41.             Document doc = is.doc(scoreDoc.doc);  
42.             System.out.println(doc.get("fullpath"));  
43.         }  
44.           
45.         // 8) Close IndexSearcher  
46.         is.close();  
47.     }  
48.       
49.     public static void main(String[] args) throws IllegalArgumentException,  
50.             IOException, ParseException {  
51.         if (args.length != 2) {  
52.             throw new IllegalArgumentException("Usage: java "  
53.                     + Searcher.class.getName() + " ");  
54.         }  
55.         String indexDir = args[0];  // 1) Parser provided index directory  
56.         String q = args[1];         // 2) Parser provided query string  
57.         search(indexDir, q);  
58.     }  
59. }  

RUNNING SEARCHER 
接著我們可以使用下面代碼對剛剛 indexing 的結果進行查詢(index 的結果在 ./index), 假設我們的要找的文件有關鍵字 "John", 則可以參考下面代碼: 

view plaincopy to clipboardprint?

1. package ch1;  
2.   
3. public class SearcherEx1 {  
4.     public static void main(String[] args)  throws Exception{  
5.         Searcher.search("./index", "John");  
6.     }  
7. }  

執行結果: 

Found 1 document(s) (in 7 milliseconds) that matched query 'John':
C:\John\EclipseNTNUProj\LuceneLab\data\doc1.TXT

You can use more sophisticated queries, such as 'patent AND freedom' or 'patent AND NOT apache' or '+copyright +developers', and so on. Chapters 3, 5, and 6 cover various aspects of searching, including Lucene’s query syntax. 

Indexer’s parsing of command-line arguments and directory listings to look for text files and Searcher’s code that prints matched filenames based on a query to the standard output. But don’t let this fact, or the conciseness of the examples, tempt you into complacence: there’s a lot going on under the covers of Lucene. To effectively leverage Lucene, you must understand how it works and how to extend it when the need arises. The remainder of this book is dedicated to giving you these missing pieces. Next we’ll drill down into the core classes Lucene exposes for indexing and searching - Understanding the core searching/indexing classes

[ InAction Note ] Ch1. Meet Lucene

Preface : 
This chapter covers : 

* Learning about Lucene
* Understanding the typical search application architecture
* Using the basic indexing API
* Working with the search API

Lucene is a powerful Java search library that lets you easily add search to any application. In recent years Lucene has become exceptionally popular and is now the most widely used information retrieval library: it powers the search features behind many websites and desktop applications. 

In this chapter we cover the overall architecture of a typical search application and where Lucene fits. It’s crucial to recognize that Lucene is simply a search library, and you’ll need to handle the other components of a search application (crawling, document filtering, runtime server, user interface, administration, etc.) as your application requires. We show you how to perform basic indexing and searching with ready-to-use code examples. 
Note. 

Lucene is an active open source project. By the time you read this, likely Lucene’s APIs and features will have changed. This book is based on the 3.0.1 release of Lucene, and thanks to Lucene’s backward compatibility policy, all code samples should compile and run fine for future 3.x releases. If you encounter a problem, send an email to javauser@lucene.apache.org and Lucene’s large, passionate, and responsive community will surely help.

Dealing with information explosion : 
As you’ll soon discover, Lucene provides a simple yet powerful core API that requires minimal understanding of full-text indexing and searching. You need to learn about only a handful of its classes in order to start integrating Lucene into an application. Because Lucene is a Java library, it doesn’t make assumptions about what it indexes and searches, which gives it an advantage over a number of other search applications. Its design is compact and simple, allowing Lucene to be easily embedded into desktop applications. 

Lucene’s website, at http://lucene.apache.org/java, is a great place to learn more about the current status of Lucene. There you’ll find the tutorial, Javadocs for Lucene’s API for all recent releases, an issue-tracking system, links for downloading releases, and Lucene’s wiki (http://wiki.apache.org/lucene-java), which contains many community-created and -maintained pages. 

- What Lucene can do 
Lucene allows you to add search capabilities to your application. Lucene can index and make searchable any data that you can extract text from. Lucene doesn’t care about the source of the data, its format, or even its language, as long as you can derive text from it. 

- History of Lucene 
Lucene was written by Doug Cutting;it was initially available for download from its home at the SourceForge website. It joined the Apache Software Foundation’s Jakarta family of high-quality open source Java products in September 2001 and became its own top-level Apache project in February 2005. 

Lucene and the components of a search application : 
It’s important to grasp the big picture so that you have a clear understanding of which parts Lucene can handle and which parts your application must separately handle.A common misconception is that Lucene is an entire search application, when in fact it’s simply the core indexing and searching component. 

A search application starts with an indexing chain, which in turn requires separate steps to retrieve the raw content; create documents from the content, possibly extracting text from binary documents; and index the documents. Once the index is built, the components required for searching are equally diverse, including a user interface, a means for building up a programmatic query, query execution (to retrieve matching documents), and results rendering. Search engines generally share a common overall architecture, as shown in below figure: 
 

Let’s walk through a search application, one component at a time and we’ll also clearly point out which components Lucene can handle (the green background boxes from upper figure). We’ll then wrap up with a summary of Lucene’s role in your search application. 

- Components for indexing 
To search large amounts of text quickly, you must first index that text and convert it into a format that will let you search it rapidly, eliminating the slow sequential scanning process. This conversion process is called indexing, and its output is called an index. 

You can think of an index as a data structure that allows fast random access to words stored inside it. The concept behind it is analogous to an index at the end of a book, which lets you quickly locate pages that discuss certain topics. In the case of Lucene, an index is a specially designed data structure, typically stored on the file system as a set of index files. 

ACQUIRE CONTENT 

The first step, at the most right side of upper figure, is to acquire content. This process, which involves using a crawler or spider, gathers and scopes the content that needs to be indexed.

Lucene, as a core search library, doesn’t provide any functionality to support acquiring content. This is entirely up to your application, or a separate piece of software. A number of open source crawlers are available, among them the following: 
* Solr (http://lucene.apache.org/solr), a sister project under the Apache Lucene umbrella, has support for natively ingesting relational databases and XML feeds, as well as handling rich documents through Tika integration. (We cover Tika in chapter 7.) 
* Nutch (http://lucene.apache.org/nutch), another sister project under the Apache Lucene umbrella, has a high-scale crawler that’s suitable for discovering content by crawling websites. 
* Grub (http://www.grub.org) is a popular open source web crawler. 
* Heritrix is Internet Archive’s open source crawler (http://crawler.archive.org). 
* Droids, another subproject under the Apache Lucene umbrella, is currently under Apache incubation at http://incubator.apache.org/droids. 
* Aperture (http://aperture.sourceforge.net) has support for crawling websites, file systems, and mail boxes and for extracting and indexing text. 
* The Google Enterprise Connector Manager project (http://code.google.com/p/google-enterprise-connector-manager) provides connectors for a number of nonweb repositories. 

BUILD DOCUMENT 

Once you have the raw content that needs to be indexed, you must translate the content into the units (usually called documents) used by the search engine. The document typically consists of several separately named fields with values, such as title, body, abstract, author, and url. You’ll have to carefully design how to divide the raw content into documents and fields as well as how to compute the value for each of those fields.

Lucene provides an API for building fields and documents, but it doesn’t provide any logic to build a document because that’s entirely application specific. It also doesn’t provide any document filters, although Lucene has a sister project at Apache, Tika, which handles document filtering very well (see chapter 7). 

ANALYZE DOCUMENT 

No search engine indexes text directly: rather, the text must be broken into a series of individual atomic elements called tokens. This is what happens during the Analyze Document step. Each token corresponds roughly to a “word” in the language, and this step determines how the textual fields in the document are divided into a series of tokens.

Lucene provides an array of built-in analyzers that give you fine control over this process. It’s also straightforward to build your own analyzer, or create arbitrary analyzer chains combining Lucene’s tokenizers and token filters, to customize how tokens are created. The final step is to index the document. 

INDEX DOCUMENT 

During the indexing step, the document is added to the index. Lucene provides everything necessary for this step, and works quite a bit of magic under a surprisingly simple API. Chapter 2 takes you through all the nitty-gritty steps for performing indexing.

We’re done reviewing the typical indexing steps for a search application and now we will visit the steps involved in searching. 

- Components for searching 
Searching is the process of looking up words in an index to find documents where they appear. The quality of a search is typically described using precision and recallmetrics. Besides them, you must consider a number of other factors when thinking about searching. We already mentioned speed and the ability to quickly search large quantities of text. Support for single and multiterm queries, phrase queries, wildcards, fuzzy queries, result ranking, and sorting are also important, as is a friendly syntax for entering those queries. Lucene offers a number of search features, bells, and whistles—so many that we had to spread our search coverage over three chapters (chapters 3, 5, and 6). 

Let’s work through the typical components of a search engine, this time working top down in previous figure, starting with the search user interface. 

SEARCH USER INTERFACE 

The user interface is what users actually see, in the web browser, desktop application, or mobile device, when they interact with your search application.

Lucene doesn’t provide any default search UI; it’s entirely up to your application to build one. Once a user interacts with your search interface, she or he submits a search request, which first must be translated into an appropriate Query object for the search engine. 

BUILD QUERY 

When you manage to entice a user to use your search application, she or he issues a search request, often as the result of an HTML form or Ajax request submitted by a browser to your server. You must then translate the request into the search engine’s Query object. We call this the Build Query step.

Query objects can be simple or complex. Lucene provides a powerful package, called QueryParser, to process the user’s text into a query object according to a common search syntax. We’ll cover it and its syntax in chapter 3, but it’s also fully described at http://lucene.apache.org/java/3_0_0/queryparsersyntax.html. 

SEARCH QUERY 

Search Query is the process of consulting the search index and retrieving the documents matching the Query, sorted in the requested sort order.

This component covers the complex inner workings of the search engine, and Lucene handles all of it for you. Lucene is also wonderfully extensible at this point, so if you’d like to customize how results are gathered, filtered, sorted, and so forth, it’s straightforward. See chapter 6 for details. 

There are three common theoretical models of search: 
* Pure Boolean model—Documents either match or don’t match the provided query, and no scoring is done. In this model there are no relevance scores associated with matching documents, and the matching documents are unordered; a query simply identifies a subset of the overall corpus as matching the query. 
* Vector space model—Both queries and documents are modeled as vectors in a high dimensional space, where each unique term is a dimension. Relevance, or similarity, between a query and a document is computed by a vector distance measure between these vectors. 
* Probabilistic model—In this model, you compute the probability that a document is a good match to a query using a full probabilistic approach. 

Lucene’s approach combines the vector space and pure Boolean models, and offers you controls to decide which model you’d like to use on a search-by-search basis. Finally, Lucene returns documents that you next must render in a consumable way for your users. 

RENDER RESULTS 

Once you have the raw set of documents that match the query, sorted in the right order, you then render them to the user in an intuitive, consumable manner.

We’ve finished reviewing the components of both the indexing and searching paths in a search application. For the rest components in the previous figure, you can go into detail of the book "Lucene in Action". 

- Where Lucene fits into your application 
A modern search application can require many components. Yet the needs of a specific application from each of these components vary greatly. Lucene covers many of these components (Green part of previous figure) well, but other components are best covered by complementary open source software or by your own custom application logic. It’s possible your application is specialized enough to not require certain components. You should at this point have a good sense of what we mean when we say Lucene is a search library, not a full application. 

Now let’s see a concrete example of using Lucene for indexing and searching - A simple application tutorial 

Supplement : 
* Lucene：基於Java的全文檢索引擎簡介 

Lucene的作者：Lucene的貢獻者Doug Cutting是一位資深全文索引/檢索專家，曾經是V-Twin搜索引擎(Apple的Copland操作系統的成就之一)的主要開發者，後在Excite擔任高級系統架構設計師，目前從事於一些INTERNET底層架構的研究。他貢獻出的Lucene的目標是為各種中小型應用程序加入全文檢索功能...

* 利用Lucene制作中文搜尋應用 
* Chinese Word Segementer for Lucene - 看來像是加上中文斷詞的程式 
* Lucene 學習筆記(1), (2), (3) 
* Lucene Tutorial 
* Lucene中的基本概念 
* Lucene API Document 
* 深入 Lucene 索引機制 
* A Short Introduction to Lucene

[ 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