Prolog解决汉诺塔问题

起源

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象为数学问题

如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

问题分析

当n == 1时，

1. A---->C sum = 1 次

当n == 2时，

1. A---->B

2. A---->C

3. B---->C sum = 3 次

当n == 3时，

1. A---->C

2. A---->B

3. C---->B

4. A---->C

5. B---->A

6. B---->C

7. A---->C sum = 7 次

不难发现规律：移动次数为：2^n - 1

递归算法

实现这个算法可以简单分为三个步骤：

把n-1个盘子由A 移到 B；

把第n个盘子由 A移到 C；

把n-1个盘子由B 移到 C；

Prolog实现

执行prolog得到：

总结

prolog非常适合解决类似于逻辑推理的问题，例如数独问题、八皇后问题，使用prolog实现非常漂亮。接下来小编会边学习边实现相关代码，希望大家多多支持。