解开排序拼图,至少要多少步呢?如果是应用“排序拼图”的★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步)
每个容器里,都是同一种颜色重叠着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%)。剩下的,都比下限花得多。
更大的棋盘
颜色一多,发牌太多,就没法全部查了。用和应用相同的方法生成的题,各20道的最少步数平均,★1是11.8步,★2(6色)是18.1步。★3以上,光求一道题的最少步数也要花时间。
应用的“提示”告诉你的,不是最少步数,而是能很快找到的解法。想挑战最少步数的话,请以下限为参考,自己去想步骤(提示的用法)。
