应用“排序拼图”在出题之前,会用计算机确认能解开。“提示”给出的下一步,也是同一个求解器找到的步骤的第一步。这里介绍这个求解器的原理。

沿着局面和走法往下找

排序拼图棋盘的状态(哪个容器里装着什么颜色),称为局面。移1步,就变成另一个局面。从最初的局面出发沿着走法往下找,到达排好的局面,走过的路就是答案。

最直接的找法,是把走1步能到的局面全部、接着走2步能到的局面全部……一层层展开的广度优先搜索。一定能找到最少步数的答案,但颜色一多,要查的局面就会多得惊人。

离排好还有多“远”的参考值

所以应用会对每个局面数出离排好还有多远的参考值,先查看看起来近的局面。参考值是下面两项的合计。

  1. 容器里颜色分界处的个数:从下往上看,颜色变化的地方的个数。
  2. 底部的重叠:如果同一种颜色在好几个容器的底部,就是那个数减去1。
123456

这个棋盘里,颜色分界处第1个有2处,第2个有2处,第3个有3处,第4个有3处,合计10。天蓝色在第3个和第4个的底部,所以底部的重叠是1。参考值是11。在排好的局面里,分界处和重叠都没有了,所以参考值是0。

参考值不会比最少步数大

这个参考值有个好性质。走1步,参考值最多只减少1。

  • 倒一次,移出的容器里的分界处,最多只减少1处。移入的容器,是同色的上面或者空容器,所以分界处既不增也不减。
  • 容器变空、底部的重叠减少1,只发生在把这个容器最后一段连着的颜色移走的时候,这时分界处不会减少。

也就是说,参考值是11的棋盘,至少要走11步。在各种棋盘上检查了12万多种走法,没有一步能让参考值一下子减少2以上。上面这个棋盘的最少步数,正好是11步。

加权A*搜索

应用给局面打上“到目前为止的步数 + 3 × 参考值”的分数,先查分数小的局面。这叫加权A*(A星)搜索。

  • 权重取1(普通的A*搜索)的话,因为参考值是最少步数的下限,所以一定能找到最少步数的答案。
  • 权重取3的话,会一个接一个地先查参考值小的局面,所以答案会快得多地找到。代价是,有时答案会比最少步数稍长一点。

用和应用相同的方法生成的题,各20道,比较了到排好为止查看的局面数,和找到的答案的步数(★3的广度优先搜索,因为局面太多,没有去数)。

★1(4色、空2)查看的局面答案的步数
广度优先搜索53711.8
A*(权重1)20311.8
A*(权重3)3911.9
★2(6色、空2)查看的局面答案的步数
广度优先搜索293418.1
A*(权重1)62218.1
A*(权重3)6418.8

两个表都是20道题的平均。权重3只查了广度优先搜索几十分之一的局面就找到了答案,步数只增加了一点点。

减少要查的走法的办法

应用的求解器,还用下面这些办法减少要查的局面。

  • 不区分容器的排列顺序:容器里的内容一样的话,排列顺序不同也当作同一个局面。
  • 不查没意义的走法:把只有一种颜色的容器移到空容器里的走法(形状不变),和移到第2个以后的空容器里的走法(和第1个的局面相同),都去掉。
  • 只用“倒”的走法来查:“叠”的题,也是查用倒的走法能不能解开(“倒”和“叠”的区别)。
  • 定上限:查了6万个局面还找不到,就当作“不知道”,不用这个发牌。

用这个求解器,同时负担了出题时的“确认能否解开”(怎么出必定有解的题)和“提示”(提示的用法)。关于底部颜色的思路,在先集中哪种颜色里也有介绍。