在英式33孔孔明棋中,空出正中間開局時,最後能留下一顆的孔只有5個(怎麼留在正中間的文章)。其他28個孔,不管走得多巧妙都留不住。

為什麼能這麼斷言呢?這篇文章用把棋盤斜向塗成3種顏色的方法,來說明理由。

把棋盤斜向塗成3種顏色

把孔塗成紅、藍、金3種顏色,排成從右上往左下延伸的斜帶。帶子的顏色,從左上往右下依序重複紅、藍、金、紅、藍、金…。

abcdefg1234567

孔的邊緣的顏色,就是塗的顏色。看直向或橫向連續排列的3個孔,會發現一定是紅、藍、金各一個。

一步之後,3種顏色的數量各變一個

孔明棋的一步,會用到直向或橫向排列的3個孔(要移動的球、被跳過的球、目的地的孔)。這3個孔,剛好是3種顏色各一個。

走一步之後,

  • 要移動的球的顏色: 減少1個
  • 被跳過的球的顏色: 減少1個(被吃掉)
  • 目的地的孔的顏色: 增加1個

每一種顏色,球的數量都是增加1個或減少1個。也就是說,每走一步,3種顏色全部的球數的奇偶都會對調。

不會改變的東西

3種顏色的奇偶,每走一步會3個一起對調。所以,「3種顏色的奇偶的組合」,只會是

  • 和開局相同的組合,或
  • 把開局的3個全部翻轉的組合,

這兩者之一。

在英式33孔空出正中間開局時,球數是紅10顆、藍11顆、金11顆(正中間的 d4 是紅色的孔)。用奇偶來寫的話,

時間點紅藍金
開局偶數奇數奇數
翻轉之後奇數偶數偶數

不管走了多少步,棋盤都是這兩種組合的其中一種。

最後一顆只能留在紅色的孔

最後只剩一顆球時,只有那顆球的顏色是1顆(奇數),另外2種顏色是0顆(偶數)。

  • 如果留在紅色的孔,是「奇數、偶數、偶數」,和表的第2行相同。有可能。
  • 如果留在藍色或金色的孔,是「偶數、奇數、偶數」或「偶數、偶數、奇數」,和表中的任何一行都不符。不可能。

也就是說,最後一顆只能留在紅色的孔。

反方向的斜向也一樣

同樣的事,也用反方向的斜帶(從左上往右下延伸的帶子)塗成的3種顏色來想。

abcdefg1234567

這個也是正中間的 d4 是紅色的孔,理由相同,最後一顆只能留在紅色的孔。

兩種塗法都是紅色的孔,只有以下5個。

abcdefg1234567

正中間的 d4,以及棋臂末端正中間的 d1、a4、g4、d7。這就是最後一顆能留下的5個孔。這5個孔實際上都能留下,已經用搜尋步驟的程式驗證過了。

法式37孔解不開的理由

在英式的四個內角加上4個孔的法式37孔,已知如果空出正中間開局,不管怎麼走都無法把球減到一顆。這也能用同樣的著色看出來。

空出正中間之後的36顆球,紅12顆、藍12顆、金12顆。3種顏色都是偶數。走了幾步之後,會變成「偶數、偶數、偶數」或「奇數、奇數、奇數」其中之一。

然而,只剩一顆球的棋盤,不管留在哪個孔,都是「1種顏色是奇數,2種顏色是偶數」。兩者都不符,所以從正中間開局的法式,無法減到一顆。

空出其他孔開局的情況,也能用同樣的計算來調查。在法式37孔中,37個孔當中有21個孔,空出它們開局的話,只靠兩個方向的著色,就能知道「無法減到一顆」。

App 裡也用到的想法

App「孔明棋」的「提示」,在尋找下一步時,用到了這種三色著色。不管怎麼走都留不到目標孔的盤面,在往後預想之前就知道「無解」,所以不必再往下調查。

整理

  • 把棋盤斜向塗成3種顏色,每走一步,3種顏色全部的球數的奇偶都會對調。
  • 所以,最後一顆能留下的孔,在開局的棋盤就已經決定了。
  • 英式33孔從正中間開局,能留下的只有 d4、d1、a4、g4、d7 這5個。
  • 法式37孔從正中間開局,無法減到一顆。

不過,用這種著色知道「有可能」的孔,不一定都能實際留下。著色是找出「做不到的事」的工具,能不能實際留下,還必須找出步驟來驗證。