The Tower of Hanoi:Wikipedia:en is classical problem in AI.

There are N disks of different sizes ant three pegs(or more, depends on the problem). Initially all disks are stacked on one peg with the smallest on the top and the largest at the bottom. The problem is to move entire stack from one peg to another that only one disk can be moved at a time and no disk may be placed on top of a smaller one.

Let the first peg called the “from”, the second peg used as a buffer to facilitate movement of disks - the “auxiliary” peg and the destination peg - the “to” peg.

Moving disks from peg “from” to peg “to” can be done using recursive scheme:

1. Move the top N-1 disks from peg “from” to peg “auxiliary” using “to” peg as a buffer
2. Move largest disk to the “to” peg
3. threat the remaining disks as a Tower of Hanoi problem with N-1 disks. Move the N-1 disks from the “auxiliary” peg to the “to” peg using the “form” peg as a buffer

We need to define some data structures:

• disk is simply represented by a number; the Disk 1 is represented by 1
• stack of disks is represented by a list of numbers; the first element represents the top disk
• constructors and selectors for the tower data type

;; The Tower represented by a list of numbers
 
;; Create empty tower
(defun make-empty-tower () nil)
 
;; Create tower by stacking DISK on top of TOWER
(defun tower-push (tower disk) (cons disk tower))
 
;; Get the top disk of TOWER
(defun tower-top (tower) (first tower))
 
;; Remove the top disk of TOWER
(defun tower-pop (tower) (rest tower))

The Hanoi configuration is a list of three towers:

;; Create a Hanoi Configuration
(defun make-hanoi (from-tower aux-tower to-tower)
  (list from-tower aux-tower to-tower))
 
;; Select I'th tower of HANOI
(defun hanoi-tower (hanoi i)
  (nth (1- i) hanoi))

Operations on towers:

;; replace the I'th tower in the HANOI configuration by tower TOWER
(defun hanoi-tower-update (hanoi i tower)
  (cond
    ((= i 1) (make-hanoi tower (second hanoi) (third hanoi)))
   ((= i 2) (make-hanoi (first hanoi) tower (third hanoi)))
   ((= i 3) (make-hanoi (first hanoi) (second hanoi) tower))))
 
;; return the top disk from I'th tower of HANOI
(defun hanoi-tower-top (hanoi i)
  (tower-top (hanoi-tower hanoi i)))
 
;; Pop the top disk of the I'th tower in the HANOI configuration
(defun hanoi-tower-pop (hanoi i)
  (hanoi-tower-update hanoi i (tower-pop (hanoi-tower hanoi i))))
 
;; Push DISK into I'th tower of HANOI
(defun hanoi-tower-push (hanoi i disk)
  (hanoi-tower-update hanoi i (tower-push (hanoi-tower hanoi i) disk)))

Basic operation is to move top disk from one peg to another:

(defun move-disk (from to hanoi)
  (let
    ((disk (hanoi-tower-top hanoi from))
      (intermediate-hanoi (hanoi-tower-pop hanoi from)))
  (hanoi-tower-push intermediate-hanoi to disk)))

Move a tower from one peg to another:

;; N disks from peg FROM to peg TO using AUX peg as in HANOI
(defun move-tower (N from aux to hanoi)
  (if (= N 1)
    (move-disk from to hanoi)
      (move-tower (- N 1) aux from to 
        (move-disk from to
          (move-tower (- N 1) from to aux hanoi)))))

At least, simply functions solving the Hanoi problem

(defun solve-hanoi (N)
  (move-tower N 1 2 3 (make-hanoi (make-complete-tower N) nil nil)))
 
;; Create tower of n disks
(defun make-complete-tower (N)
  (make-complete-tower-aux N (make-empty-tower)))
 
;; Push a complete tower of N disks on top of A tower
(defun make-complete-tower-aux (N A)
  (if (zerop N)
    A
    (make-complete-tower-aux (1- N) (tower-push A N))))

This simply program solves the Hanoi Tower problem. To run program type in (solve-hanoi N), where N is a number of disks:

(solve-hanoi 3)
(NIL NIL (1 2 3))

We get back final configuration of towers, but it is not interesting.

1. Trace the move-disk function to know the sequence of moves taken by the algorithm. Solve the problem for more than three disks.

Source code

Implementations of Tower of Hanoi problem in many other languages can be found on Hanoimania!