Turm von Hanoi in Lisp

save [hanoi.lisp]

__________________________________________________________________

; Die Tuerme von Hanoi
; --------------------
; Ute Schmid Maerz 1995

; 3 Staebe: A B C
; n Scheiben
; Start: alle Scheiben auf A; Ziel: alle Scheiben auf B
; Constraints:
; (1) Es darf immer nur die oberste Scheibe versetzt werden
; (2) Es darf immer nur eine kleinere Scheibe auf eine groessere gesetzt werden

; Produktionsregel:
; WENN nur eine Scheibe
; DANN bewege die Scheibe von "von_stab" nach "nach_stab"
; SONST versetze von "von_stab" nach "hilfs_stab" und
;       verwende "nach_stab" als neuen "hilfs_stab" fuer n-1 Scheiben
;       versetze von "hilfs_stab" nach "nach_stab" und
;       verwende "von_stab" als "hilfs_stab" fuer n-1 Scheiben
;
; Fuer 3 Scheiben:         (1 2 3) (     ) (     )
; Scheibe 1 von A nach B   (  2 3) (    1) (     )
; Scheibe 2 von A nach C   (    3) (    1) (    2)
; Scheibe 1 von B nach C   (    3) (     ) (  1 2)
; Scheibe 3 von A nach B   (     ) (    3) (  1 2)
; Scheibe 1 von C nach A   (    1) (    3) (    2)
; Scheibe 2 von C nach B   (    1) (  2 3) (     )
; Scheibe 1 von A nach B   (     ) (1 2 3) (     )

; -----------------------------------------------------

; Erste Version nach Winston & Horn S. 125

; Programmstart: (tuerme-von-hanoi n), n=Scheibenzahl

; (DEFUN tuerme-von-hanoi (n)
;    (versetze 'A 'B 'C n)                              ; A B C sind Staebe
; )

; (DEFUN bewege-scheibe (von nach)
;    (LIST(LIST 'BEWEGE 'SCHEIBE 'VON von 'NACH nach))
; )

; (DEFUN versetze (von nach hilfsplatz zahl)
;   (COND ( (= zahl 1) (bewege-scheibe von nach) )
;         ( T       (APPEND
;                     (versetze von hilfsplatz nach (- zahl 1))
;                     (bewege-scheibe von nach)
;                     (versetze hilfsplatz nach von (- zahl 1))
;                    )
;   )     )
; )

; =============================================================
; Zweite Version: mit Angabe der Scheibennummern

; (1) Laden
; (2) (SETQ A '(1 2 3) B NIL C NIL)
;             oder '(1 2 3 4 5) etc.
; (3) (hanoi)

(DEFUN bewege (von nach)
    (PRINT
       (LIST 'BEWEGE 'SCHEIBE (CAR (EVAL von))
             'VON    von
             'NACH   nach
    )  )

    (COND ( (NULL (EVAL von)) (PRINT (LIST 'STAB von 'LEER)) )
          ( (OR (NULL (EVAL nach))
                (> (CAR(EVAL nach)) (CAR(EVAL von)) )
            )
            (SET nach (CONS (CAR(EVAL von)) (EVAL nach)) )
            (SET von  (CDR (EVAL von))                   )
          )
          ( T  (PRINT (LIST 'VERSETZEN 'VON (CAR(EVAL von))
                                       'AUF (CAR(EVAL nach)) 'GEHT 'NICHT)))
    )

  (LIST(LIST 'BEWEGE 'SCHEIBE (CAR(EVAL nach))
                      'VON     von
                      'NACH    nach
   )    )
)

(DEFUN zugwahl (von nach hilfsplatz zahl)
   (COND ( (= zahl 1) (bewege von nach) )
         ( T  ( APPEND
                  (zugwahl von hilfsplatz nach (- zahl 1))
                  (bewege von nach)
                  (zugwahl hilfsplatz nach von (- zahl 1))
               )
   )     )
)

(DEFUN hanoi ()
   (zugwahl  'A 'B 'C (LENGTH A))
)