孔明棋的答案,可以用電腦來找。App「孔明棋」的「提示」,以及在這個網站確認答案時,都是使用同樣想法的程式。這裡簡單介紹其中的機制。

依序嘗試所有的步

最直接的方法,是重複選一個能走的步來走,再選一個能走的步來走。走不通了就退回一步,選另一個還沒試過的步。

  1. 在目前的盤面上,選一個能走的步來走。
  2. 球只剩一顆,就是找到答案了。
  3. 沒有能走的步了,就退回一步,試別的步。
  4. 所有的步都試完了,就再退回一步。

這種方法稱為深度優先搜尋。這和人用「復原一步」來嘗試是一樣的事,只是以驚人的速度重複進行。

不重複調查同一個盤面

在孔明棋中,即使用不同的順序走,也常常會變成同一個盤面。在英式33孔,第7步之後的走法超過22萬種,但形成的盤面只有2萬2千種左右(解法有幾種?)。

所以,把調查過、知道走不通的盤面記起來,下次再遇到,就馬上折返。光是這樣,要調查的量就大幅減少。

在這個網站使用的程式中,英式33孔從正中間開局、留在正中間的答案,一瞬間(不到0.1秒)就找到了。不過,並不是總是這麼快。從改變第2步的棋盤同樣去找,花了9秒左右。從哪一步開始試,所花的時間會有很大的不同。

不往後預想就中止

另一個巧思,是當知道從這個盤面開始,不管怎麼走都達不到目標時,就不再往後調查而中止。這叫做「剪枝」。

在 App 中,用以下兩種方式剪枝。

  • 三色著色: 把棋盤斜向塗成3種顏色,每走一步,3種顏色全部的球數的奇偶都會對調。因此,從目前的盤面能留下最後一顆的孔,光靠計算就能知道(三色著色的文章)。
  • 王球的行與列: 王球每次移動2格,所以所在孔的行與列的奇偶不會改變(把王球留到最後的訣竅)。

如果棋盤上已經沒有任何一個孔能同時滿足兩個條件,就沒有能把王球留到最後的孔。那個盤面,不必往後預想,就知道「無解」。

在 App 的「提示」裡

App 的「提示」,會從目前的盤面找出能達成目標的下一步,用金色圈讓它發光。

  • 先記住題目的答案: 「題目」的棋盤是倒著跳製作的,所以知道製作時的答案(一定有解的題目的製作方式)。因為記得答案的路上的盤面「有解」,所以能馬上回答。即使是偏離路的盤面,只要在搜尋的過程中匯入答案的路,就能在那裡停止。
  • 為調查的量設上限: 一次提示最多調查150萬個盤面或3秒。在大棋盤上,也有在那之前找不出答案的情況。
  • 告訴你要退回幾步: 從目前的盤面已經達不到目標,或在上限之內還不知道時,會調查能用「復原一步」退回的盤面,像「退回3步就能留下」這樣,告訴你要退回幾步。因為是把能退回的盤面一半一半地縮小範圍來調查,所以步數再多也能很快找到。

人在解題時的提示

電腦的巧思,人在解題時也能用上。

  • 記住走不通的形狀: 失敗過一次的形狀,即使用別的順序走到,一樣會失敗。
  • 從終點倒著想: 最後能留下的孔,從一開始就決定了。先決定想達成的孔,就比較容易選步(怎麼留在正中間)。
  • 退回去試: 像深度優先搜尋那樣,猶豫時就稍微退回,試別的步,是正確的做法。