汉诺塔问题的两种解法(5)

第五节 条件限定法——限定条件

限定条件法不关注移动过程的整体规律，而着眼于具体的移动路径（规定每一步移动的出发点及落脚点），对每一种可能的移动路径设置限定条件，通过对限制条件的设置及调整，逐渐找到最优的完整的移动路径。如果说递归方法依赖于人类的智能，那么限定条件法则依赖于时下流行的机器的“智能”。

在由Roadlabs、陶陶和我组成的三人项目组中，Roadlabs负责给出限定条件，陶陶和我负责用具体的编程语言来实现。在Roadlab给出的若干个限定条件中，经过反复筛选验证，最终确定以下四个限定条件。

（1）取胜条件：当左、中为空，右不为空时，赢得游戏；

（2）单一原则：每次只能移动一个数字；

（3）大小原则：小的数字必须置于大的数字之上；

（4）不连续移动原则：不允许连续移动一个数字；

上述的4个条件中，条件1、条件2及条件3是依游戏规则而定，条件2是人为增加的限定，为了防止不必要的重复移动，或者出现死循环。

这些条件看起来都很简单，但是要将它们转化为程序语言，还需要进一步的演绎推理，转化成可操作的步骤。上述条件还可以进一步演化出以如4个结论。

（a）每次移动中，可用的出发点是唯一的（此条结论由陶陶同学给出）；

（b）针对（a）中所指的唯一出发点，当塔尖（列表首项——即将被移动的数字）不为1时，可用的落脚点是唯一的；

（c）当塔尖为1时，塔尖（数字1）的落脚点不唯一，但是作为整体的“塔”的落脚点是唯一的（关于塔的定义见结论d），它必须落在首项值比塔底大1的那一列上。如果塔高（数字的个数）为奇数，则1的落脚点=塔的落脚点；如果塔高是偶数，则1的落脚点=相对缓冲区（塔落脚点以外的另一个可落脚的点）；

（d）塔的定义：从1开始的、差值连续为1的数字，其中1被称为塔尖，最后一个数（最大的数）被称为塔底。

上述结论是否能够证明它们的正确性呢？这里我们对结论a给出证明，其余几项希望读者自行论证。

证明：每一次移动的出发点都是唯一的。

●当步数=0时，出发点只能是左侧的列，即起点，因此是唯一的；

●当步数>0时：

○ 如果最后移动项=1，那么出发点一定不是1（不连续移动原则），因此，下一个出发点必然是非1的两项中值较小的一列，因此出发点是唯一的；

○ 如果最后移动项≠1，那么下一个出发点一定是数字1所在的列，因为上一次移动的出发点所在的列，其首项的当前值一定大于最后移动项的值，因此该首项无处可移（大小原则）。

根据以上分析，可以证明结论a是正确的——每一次移动的出发点都是唯一的。有兴趣的读者不妨仿照此方法，对结论b、c给出证明，图29可供参考。结论d是对“塔”的定义，无须证明。

图29 猜猜看图中最后一次移动的是哪个盘子

有了上述结论，就可以着手用程序来实现它们了。

== 未完待续 ==