解开排序拼图,至少要多少步呢?如果是应用“排序拼图”的★1(4色、空2)的大小,就能把发牌全部查一遍。我们用“倒”的走法,数出了所有发牌的最少步数。

调查方法

  • 只查没有容器里连着3个以上同色的“公平的发牌”(应用拿出来的只有这种发牌)。
  • 只是容器排列顺序换了的发牌,和只是颜色换了的发牌,视为同一种。这样就是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步占了全体的八成以上。5步能解开的发牌只有3种,要16步的发牌只有4种。

(这里的数是“种类”。在应用里实际发到的概率,每种略有不同。)

最短的棋盘(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%)。剩下的,都比下限花得多。

更大的棋盘

颜色一多,发牌太多,就没法全部查了。用和应用相同的方法生成的题,各20道的最少步数平均,★1是11.8步,★2(6色)是18.1步。★3以上,光求一道题的最少步数也要花时间。

应用的“提示”告诉你的,不是最少步数,而是能很快找到的解法。想挑战最少步数的话,请以下限为参考,自己去想步骤(提示的用法)。