孔明棋

關於孔明棋的流傳，有許多的傳説，有人説是三國時代孔明所發明的益智棋，失傳後輾轉流傳至日本、歐美，成為外國普及的益智遊戲。另外也有一種説法，説它真正的名字叫做十字棋，據傳是發明於法國，是一個被囚的法國貴族，在獄中為了打發時光，而想出來的。後來在18世紀末期傳至英國，才漸漸流行至世界各地。

這種遊戲的魅力在於，玩法非常簡單，但是其中變化卻是數不盡的，解法更是不只一種，所以不論其形式如何變化，總是能帶給人們無窮的樂趣。

由於其它種排法都是孔明棋的變形，所以我們在研究的時候，就專注於孔明棋上面，並推廣孔明棋的問題，想找出是否任意空一格，而不只是研究空在中央的時候，因為若只是空在中央那一格，用暴力法也可以很快找到答案，但是當我們把問題推廣之後，便需要應用一些演算方法，才能夠解決，也希望藉由問題的推廣，讓這個演算法能夠適用更多任何類似棋類問題的解決。

基本上人類在玩這類遊戲的時候，多半是依據直覺，或者依據着經驗法則，會有一些策略來決定如何下棋，例如有人會決定要把棋子都儘量的往中間跳，也有人會依照着自己的喜好順序來跳，不論如何，大多是以隨機的方式來決定如何走下一步的。

但是當用電腦來處理這種問題時，就不會用這種隨機的方式來作，而是會以更有系統的方法找出可能的下一步，然後嘗試着走過這些可能的路徑，去找到最後的解答，由於電腦可以準確並大量記憶的特性，所以我們可以讓電腦記憶走過的路徑，所以，當電腦走到無法再走下去的情況時，可以退回到之前的盤面，改下另一種可能的走法，而繼續嘗試找出解答來。當然，電腦在選擇可能的下一步時，也可以有一些策略來判斷，要嘗試哪一步才可以比較快找到解答。

由於孔明棋的盤面有33格，每一格可分為有棋子和沒有棋子二種可能，因此，所有可能的盤面組合，高達2^33，相當於有80億種以上的盤面組合，由此可以想見其盤面變化之多。所以，要是隻用暴力法去展開這整個樹來求解，而每走一步會少一顆棋子，總共32顆棋子需要31步才能求得解答，也就是説，這棵樹最深會到31層，每一層又可能會有很多條分枝，由此可以想見這棵樹的龐大。當然，這樹中間是有很多重複的節點，是表示同樣的盤面，所以，我們努力的方向就是在於要如何減少經過這些重複的節點，來減少搜尋的空間與時間。

假設每一種盤面用一個bit來表示，那2^33種盤面組合就得用2^33bits，相當於1GB的空間來紀錄。因此在應用上我們使用了硬碟來記錄走過並且確定展開下去會無解的盤面，而利用Hashing的方法，把每個盤面對應到一個bit，但是，因為硬碟大量的讀寫動作，所以造成在執行時的速度變慢。為了解決這個問題我們應用了一些策略。

同時，因為它有對稱關係，所以我們每一種盤面，經過旋轉和翻轉的組合，相當於有八種盤面，因此，我們每經過一個盤面，相當於經過了八個盤面。同樣的道理，在解各種盤面的時候，也可以應用這種對稱的關係，來減少需要解的盤面。