在英式33孔孔明棋中,空出正中間開局時,最後能留下一顆的孔只有5個(怎麼留在正中間的文章)。其他28個孔,不管走得多巧妙都留不住。
為什麼能這麼斷言呢?這篇文章用把棋盤斜向塗成3種顏色的方法,來說明理由。
把棋盤斜向塗成3種顏色
把孔塗成紅、藍、金3種顏色,排成從右上往左下延伸的斜帶。帶子的顏色,從左上往右下依序重複紅、藍、金、紅、藍、金…。
孔的邊緣的顏色,就是塗的顏色。看直向或橫向連續排列的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種顏色來想。
這個也是正中間的 d4 是紅色的孔,理由相同,最後一顆只能留在紅色的孔。
兩種塗法都是紅色的孔,只有以下5個。
正中間的 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孔從正中間開局,無法減到一顆。
不過,用這種著色知道「有可能」的孔,不一定都能實際留下。著色是找出「做不到的事」的工具,能不能實際留下,還必須找出步驟來驗證。
