在 App「孔明棋」的「題目」模式中,每次按「新遊戲」,都會產生形狀不同的棋盤。即使如此,每一個棋盤都一定有解。這篇文章介紹其中的機制。

普通的做法,不知道有沒有解

如果隨便決定孔的形狀和球的擺法,會做出很多無解的棋盤。要確認有沒有解,必須調查所有的步,球一多就很花時間。

所以 App 使用的是從答案倒著製作題目的方法。

倒著跳

孔明棋的一步,是「球跳過相鄰的球,落到空孔,並吃掉被跳過的球」的動作。把它倒過來,就變成

球退回到2格外的空孔,並在中間的空孔放上一顆球

這個動作。每倒著走一步,球就增加一顆。

從一顆王球開始

把倒著的步,從只剩一顆王球的棋盤(也就是已經過關的棋盤)開始疊加。用小例子來看看。

首先是只有王球的棋盤。

第1次: 把王球往上退回2格,並在中間放一顆球。

第2次: 把中間放的球往左退回2格,並在它們之間放一顆球。

第3次: 把王球往右退回2格,並在中間放一顆球。

這樣就做出了4顆球的題目。

倒著走的步,就是答案

把做出來的步,從最後一步依序用正常方向走,就直接成為答案。上面的例子中,只把用到的孔當作棋盤的孔,做成題目的棋盤,就能像下面這樣解開。

  1. 第 1 步 e1→c1
  2. 第 2 步 a2→c2
  3. 第 3 步 c1→c3
  4. 第 3 步之後 剩餘 1 顆

倒著做出來的步驟,原本就是從已過關的棋盤開始,所以用正常方向走,一定會只剩王球。因此可以保證每道題目至少有一個答案。

App 的巧思

App 在這個做法上,又加了幾項巧思。

  • 重複利用孔: 選擇倒著的步時,讓它比較容易選到再次使用已經用過的孔的步。這樣步驟會互相交錯,比較不會變成只是排成一直線的題目。
  • 整理棋盤的形狀: 做好的棋盤有一半,會補上孔,變成左右對稱的形狀。其餘的則在棋盤邊緣補上1~2個空孔,改變形狀。即使補上空孔,原本的答案還是照樣能走,所以有解這件事不變。
  • 同一個種子產生同樣的題目: 題目是從稱為「種子」的數字製作的,所以相同的種子和難度,不管在 iPhone 還是 Android 上,都會做出同樣的題目。

調查難度,不合就重做

倒著做出來的題目,一定有答案。但光是這樣,可能太簡單,也可能太難。

所以 App 會調查做好的題目,在答案步驟的途中,有多少步走了就再也留不住王球(陷阱步)。陷阱步的比例,會重做最多24次,直到落入★1~★5各自的範圍(範圍請看難度的文章)。

即使是★5宗師的題目(27~32顆球),製作所需的時間,在開發用的 Mac 上平均也只要0.6秒左右。此外,每個難度都預先做好了3題備用,用掉之後會在背景補做,所以玩的人幾乎不用等待。

答案不一定只有一個

倒著做出來的步驟,只是答案的其中之一。同一個棋盤,常常還有好幾種別的答案。在瀏覽器遊玩的頁面的「王球練習」的棋盤,也是用同樣的想法做的,16顆球的棋盤有超過300萬種解法(解法有幾種?)。

App 的「提示」記得製作時的答案,所以只要在答案的路上,就能馬上告訴你下一步。偏離了那條路時,會由尋找解法的程式找出另一條路(用電腦解題)。