Prolog - 汉诺塔问题

---

河内塔问题是一个著名的难题，使用中间桩作为辅助固定桩，将 N 个圆盘从源桩/塔移动到目标桩/塔。解决这个问题时需要遵循两个条件 -

• 较大的磁盘不能放置在较小的磁盘上。

• 一次只能移动一个磁盘。

下图描述了 N=3 磁盘的启动设置。

为了解决这个问题，我们必须编写一个过程 move(N, Source, Target,auxiliary)。这里，N 个磁盘必须从源桩转移到目标桩，并将辅助桩保持在中间。

例如 – 移动（3，源，目标，辅助）。

• 将顶部磁盘从源移动到目标

• 将顶部磁盘从源移动到辅助

• 将顶部磁盘从目标移动到辅助

• 将顶部磁盘从源移动到目标

• 将顶部磁盘从辅助磁盘移至源磁盘

• 将顶部磁盘从辅助磁盘移至目标磁盘

• 将顶部磁盘从源移动到目标

程序

move(1,X,Y,_) :-
   write('Move top disk from '), write(X), write(' to '), write(Y), nl.
move(N,X,Y,Z) :-
   N>1,
   M is N-1,
   move(M,X,Z,Y),
   move(1,X,Y,_),
   move(M,Z,Y,X).

输出

| ?- [towersofhanoi].
compiling D:/TP Prolog/Sample_Codes/towersofhanoi.pl for byte code...
D:/TP Prolog/Sample_Codes/towersofhanoi.pl compiled, 8 lines read - 1409 bytes written, 15 ms

yes
| ?- move(4,source,target,auxiliary).
Move top disk from source to auxiliary
Move top disk from source to target
Move top disk from auxiliary to target
Move top disk from source to auxiliary
Move top disk from target to source
Move top disk from target to auxiliary
Move top disk from source to auxiliary
Move top disk from source to target
Move top disk from auxiliary to target
Move top disk from auxiliary to source
Move top disk from target to source
Move top disk from auxiliary to target
Move top disk from source to auxiliary
Move top disk from source to target
Move top disk from auxiliary to target

true ?

(31 ms) yes