解開排序拼圖,至少需要幾步呢?以 App「排序拼圖」★1(4 色、空 2 個)的大小來說,可以把配法全部檢查完。我們用「倒」的走法,數出了所有配法的最少步數。
調查方法
- 只檢查沒有同色連續 3 個以上的容器的「公平的配法」(App 出的題目只有這種配法)。
- 把只是容器順序對調的配法,或只是顏色換了的配法,視為相同。這樣就有 89,675 種(有幾種配法?)。
- 對每一種配法,把 1 步能到的局面、2 步能到的局面……全部展開,找出最先排好的步數(廣度優先搜尋)。
最少步數的分布
| 最少步數 | 配法的種類 |
|---|---|
| 5 步 | 3 |
| 6 步 | 8 |
| 7 步 | 124 |
| 8 步 | 741 |
| 9 步 | 3,523 |
| 10 步 | 11,070 |
| 11 步 | 21,321 |
| 12 步 | 26,778 |
| 13 步 | 19,271 |
| 14 步 | 6,635 |
| 15 步 | 197 |
| 16 步 | 4 |
最多的是 12 步,10~13 步就佔了全體的 8 成以上。5 步就能解開的配法只有 3 種,要花 16 步的配法只有 4 種。
(這裡的數字是「種類」。App 實際配出來的機率,依種類而稍有不同。)
最短的盤面(5 步)
每個容器都是同色疊了 2 個。用 2 個空容器,5 步就能排好。
最花步數的盤面(16 步)
第 1 個和第 2 個、第 3 個和第 4 個,排列完全一樣。每個容器裡相鄰的顏色都不同,紅色和黃綠色各自在 2 個容器的底部。
查看 16 步的走法
找出步數的下限
最少步數不用全部檢查,光看盤面就能知道下限(不會比這個數字更少)。
- 數容器裡顏色的交界數量。
- 如果同一種顏色在好幾個容器的底部,就加上「那個數量-1」。
這個合計,每倒一次最多只會減少 1,所以不會比最少步數大(用電腦來解)。
- 5 步的盤面:交界有 4 個,紅色在 2 個容器的底部所以加 1,下限是 5。剛好就是最少步數。
- 16 步的盤面:交界有 12 個,紅色和黃綠色各在 2 個容器的底部所以加 2,下限是 14。實際上要花 16 步。
89,675 種之中,下限和最少步數剛好一致的有 38,571 種(約 43%)。其餘的,都比下限多花步數。
更大的盤面呢
顏色變多之後,配法多到沒辦法全部檢查。用和 App 相同的方式各做 20 道題目,最少步數的平均,★1 是 11.8 步,★2(6 色)是 18.1 步。★3 以上,光是求 1 道題的最少步數就要花很多時間。
App 的「提示」告訴你的不是最少步數,而是很快就能找到的解法。如果想挑戰最少步數,請以下限為參考,自己思考步驟(提示的用法)。
