解開排序拼圖,至少需要幾步呢?以 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 步)

123456
第1步 3→5(2個)
123456
第2步 1→3(2個)
123456
第3步 4→5(2個)
123456
第4步 2→4(2個)
123456
第5步 1→2(2個)
123456
完成

每個容器都是同色疊了 2 個。用 2 個空容器,5 步就能排好。

最花步數的盤面(16 步)

123456

第 1 個和第 2 個、第 3 個和第 4 個,排列完全一樣。每個容器裡相鄰的顏色都不同,紅色和黃綠色各自在 2 個容器的底部。

查看 16 步的走法
123456
第1步 1→5
123456
第2步 1→6
123456
第3步 2→5
123456
第4步 2→6
123456
第5步 1→2
123456
第6步 1→5
123456
第7步 2→1(2個)
123456
第8步 2→5
123456
第9步 3→2
123456
第10步 3→6
123456
第11步 3→1
123456
第12步 2→3
123456
第13步 4→3
123456
第14步 4→6
123456
第15步 4→1
123456
第16步 3→4(3個)
123456
完成

找出步數的下限

最少步數不用全部檢查,光看盤面就能知道下限(不會比這個數字更少)。

  1. 數容器裡顏色的交界數量。
  2. 如果同一種顏色在好幾個容器的底部,就加上「那個數量-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 的「提示」告訴你的不是最少步數,而是很快就能找到的解法。如果想挑戰最少步數,請以下限為參考,自己思考步驟(提示的用法)。