河内塔问题的初始状态有A、B、C三根柱子，在A柱上有中间带孔从大到小由下到上重叠像“塔”一样的n个圆盘。目标状态是将“塔”移到B柱上，C柱作为过渡。规则是每次只能移动最上面的一个圆盘， 大圆盘不能压在小圆盘上。

这个问题可通过下述三个步骤解决：

（1）将A柱上顶层的n-1个圆盘移到C柱；

（2）将A柱底部最大的圆盘移到B柱；

（3）将n-1个圆盘从C柱移到B柱。

借助于递归，直到n的值为1时，才做实际的移动工作。

假设n个圆盘按照从小到大的顺序编号，即n个圆盘的编号为从1至n。柱子上的圆盘用数字表表示；比如，若A为表(1 2 3)，则表示A柱上的圆盘从上到下是编号依次为1、2、3的圆盘。

三个柱子初始时的状态为：A,(1 2 3); B,(); C, ()。

实现程序代码如下（可打印出有关步骤的详细信息）。

函数的定义

;从from柱移动一个圆盘到to柱

(defun move_disk (from to)

(print (list 'move

(car (eval from)) ;打印出移动圆盘的编号

'from from ;移出柱

'to to ;移入柱

)

)

(cond

;移出柱为空

((null (eval from))

(print (list from 'empty)) ;打印移出柱为空

)

;移入柱为空或其顶端圆盘大于移出柱的顶端圆盘

((or (null (eval to)) (> (car (eval to)) (car (eval from))) )

(set to (cons (car (eval from)) (eval to) ) ) ;将圆盘添加到移入柱

(set from (cdr (eval from))) ;将圆盘从移出柱去除

)

;非法移动

(T

(print (list 'cannot 'move

(car (eval from))

'onto

(car (eval to))

)

)

)

) ;cond结束

(list (list

'move (car (eval to)) ;圆盘的编号

'from from ;从哪个柱子

'to to ;到哪个柱子

)

)

)

;借助spare柱, 将n个圆盘从from柱移动到to柱

(defun transfer ( from to spare n)

(cond

((equal n 1) (move_disk from to)) ;移动一个圆盘

(T

(append

(transfer from spare to (- n 1)) ;借助to柱, 将n-1个圆盘从from移到to

(move_disk from to) ; 移动最下面的圆盘

(transfer spare to from (- n 1)) ; 借助from柱, 将n-1个圆盘从spare移到to

)

)

)

)

;河内塔问题

(defun tower_of_hanoi ()

(transfer 'A 'B 'C (length A))

)

程序的运行：

程序的运行命令如下

(setq A '(1 2 3) B NIL C NIL) ;柱子初始状态

(tower_of_hanoi)

程序运行结果如下：