河内塔序言

tower of hanoi prolog

你好,我对汉诺塔的实现有疑问。 我需要打印包含必要动作的列表列表,但我的算法只在光盘数为 N=1 时有效。 这是我的代码

move(1,X,Y,_,L) :-  
    append([X],[Y],L).
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).

这是N=1时的结果

?- move(1,left,right,_,L).

L = [left,right]

(16 ms) yes

我需要这样的东西

    L = [[left,center],[left,right],[center,right],[left,center],[right,left],
      [right,center],[left,center],[left,right],[center,right],[center,left],
[right,left],[center,right],[left,center],[left,right],[center,right]]

当N=4时

如果有人能帮助我,我将不胜感激。

通过一些小的改动你可以这样写:

move(1,X,Y,_,[[X,Y]]).

move(N,X,Y,Z,L) :- 
    N>1, 
    M is N-1, 
    move(M,X,Z,Y,L1),
    move(1,X,Y,_,L2), 
    move(M,Z,Y,X,L3),
    append(L1,L2,L4),
    append(L4,L3,L).

示例:

?- move(4,left,right,center,L).
L = [[left, center], [left, right], [center, right], [left, center], [right, left], [right, center], [left, center], [left, right], [center, right], [center, left], [right, left], [center, right], [left, center], [left, right], [center, right]] ;
false.

在 Prolog 中描述 lists 时,请始终考虑使用 表示法!

例如,考虑:

moves(1, X, Y, _) --> [X-Y].
moves(N, X, Y, Z) -->
    { N #> 1,
      M #= N-1 },
    moves(M, X, Z, Y),
    moves(1, X, Y, _),
    moves(M, Z, Y, X).

注意这...

  • 使用更少 个参数
  • 避免使用append/3.

我也冒昧使用了...

  • 名称 moves//4 以明确我们描述的是 动作 ,而不是 单个 搬家。
  • CLP(FD) 声明式算法的约束(更容易理解)
  • (-)/2 用于表示 ,这是 Prolog 中的惯例。

示例查询,使用 DCG 的 phrase/2 接口谓词:

?- phrase(moves(4,left,right,center), Ls).
Ls = [left-center, left-right, center-right, left-center, right-left, ... ].