rA{ .J^W %pQuz !sˍQuz cOqgc; -*-LISP-*- ; Impossible without the inspiration that ; came from seeing TEACH;KMP HANOI ; Hope it works. (defun hanoi (tower-list) (hanoi-1 tower-list nil nil)) (defun hanoi-1 (start stack result) (cond ((null start) result) (t (hanoi-1 (cdr start) result stack) (hanoi-1 (cdr start) nil (ncons (car start))))));;; -*- LISP -*- ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; ;;; KMP's Solution to the "Tower of Hanoi" problem. ;;; ;;; ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Representation being used for towers is ;;; ( ... ) ;;;;;;;;;;;;;;; Define Basic Operations to do on a Towers ;;;;;;;;;;;;;;;;;;;;; ;;; Data-structure dependent functions (DEFUN CREATE-TOWER (NAME ELEMENTS) (CONS NAME ELEMENTS)) (DEFUN NAME-OF (TOWER) (CAR TOWER)) (DEFUN ELEMENTS-OF (TOWER) (CDR TOWER)) ;;; Data-structure independent functions (these functions depend only ;;; on the fact that ELEMENTS-OF returns a list of the elements of a ;;; tower.) (DEFUN HEIGHT (TOWER) (LENGTH (ELEMENTS-OF TOWER))) (DEFUN EMPTY? (TOWER) (ZEROP (HEIGHT TOWER))) (DEFUN ALL-BUT-BOTTOM (TOWER) (CDR (ELEMENTS-OF TOWER))) (DEFUN TOP (TOWER) (CAR (LAST (ELEMENTS-OF TOWER)))) (DEFUN BOTTOM (TOWER) (CAR (ELEMENTS-OF TOWER))) ;;;;;;;;;;;;;;;;;;;;;;;;; User Interface Function ;;;;;;;;;;;;;;;;;;;;;;;;; (DEFUN HANOI () (PROG (N) (TERPRI TYO) (PRINC '|How many blocks? | TYO) ; Ask initial question (SETQ N (DO ((FORM (READ) (READ))) ; Loop reading reply ((FIXP FORM) FORM) ; Exit on fixed point # (TERPRI TYO) ; Re-ask otherwise (PRINC '|Try again: | TYO))) (SOLVE (CREATE-TOWER '|Tower #1| (MAKE-A-STACK N)) ; Solve (CREATE-TOWER '|Tower #2| NIL) (CREATE-TOWER '|Tower #3| NIL)) (RETURN 'DONE))) ; Return ;;;;;;;;;;;;;;;;;;;;;;;;; Auxiliary Functions ;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Returns a list of numbers (N N-1 N-2 ... 1) (DEFUN MAKE-A-STACK (N) (DO ((COUNT 1. (1+ COUNT)) ; COUNT counts from 1 by 1's (L NIL)) ; L will accumulate a list ((> COUNT N) L) ; Stop when COUNT > N, Return L (SETQ L (CONS COUNT L)))) ; L <- [CONS N onto front of L] ;;; Just printing the solution is enough for our purposes. (DEFUN PUT-BLOCK (BLOCK-NAME LOCATION) (TERPRI TYO) (PRINC (LIST '|Put Block #| BLOCK-NAME '| on | LOCATION) TYO)) ;;;;;;;;;;;;;;;;;;;;;;;;; Main Problem Solver ;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Method of solution: ;;; ;;; If there are no blocks in the ORIGIN tower, there is nothing to do ;;; else ;;; [1] Solve for N-1 blocks, thereby clearing the top off of biggest ;;; block ;;; [2] Move the biggest block ;;; [3] With the biggest block on right pile, resolve the N-1 case, ;;; remembering that some blocks have moved from their original ;;; locations by now. ;;; (DEFUN SOLVE (ORIGIN-TOWER SCRAP-TOWER GOAL-TOWER) (COND ((EMPTY? ORIGIN-TOWER) NIL) ; Nothing to do! (T (SOLVE ; Clear biggest (bottom) block (CREATE-TOWER (NAME-OF ORIGIN-TOWER) (ALL-BUT-BOTTOM ORIGIN-TOWER)) GOAL-TOWER SCRAP-TOWER) (PUT-BLOCK ; Move biggest block (BOTTOM ORIGIN-TOWER) (NAME-OF GOAL-TOWER)) (SOLVE ; Put things back on biggest block (CREATE-TOWER (NAME-OF SCRAP-TOWER) (ALL-BUT-BOTTOM ORIGIN-TOWER)) (CREATE-TOWER (NAME-OF ORIGIN-TOWER) NIL) (CREATE-TOWER (NAME-OF GOAL-TOWER) (NCONS (BOTTOM ORIGIN-TOWER))))))) fThe Tower of Hanoi. There exist 3 poles, with an arbitrary number of blocks on them, each block a different size, with any given block stackable only on a block larger than itself. You wish to move all the blocks from one pole to another, within these restrictions. _ _ - | | | | | | ------- | | | | | 1 | | | | | --------- | | | | | 2 | | | | | ----------- | | | | | 3 | | | | | --------------------------------------------- To help you get started, a few of the solutions are provided here: Three block problem. (Remember that larger numbers specify larger blocks) 1 2 2 1 1 3 3 1 3 2 1 3 2 2 3 1 2 3 -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- (1) (2) (3) (4) (5) (6) 1 2 2 1 3 3 -|-|-|- -|-|-|- Solved (7) (8) --------------------------------------------------------------- Four block problem. 1 2 2 3 3 3 3 1 1 1 1 2 4 4 1 4 1 2 4 2 4 3 2 4 3 2 4 3 -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- (1) (2) (3) (4) (5) (6) (7) 1 1 2 2 2 2 1 1 1 3 3 4 3 3 4 1 3 4 3 4 2 3 4 2 4 2 1 4 -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- -|-|-|- (8) (9) (10) (11) (12) (13) (14) 1 2 2 3 3 1 4 4 -|-|-|- -|-|-|- Solved (15) (16) --------------------------------------------------------------- Hint: The general solution to this problem is of the following nature... |------------| | N-1 Blocks | ---------------- | Nth Block | No blocks No Blocks --------------------------------------------------------------- | | \ / V ---------------- |------------| | Nth Block | | N-1 Blocks | No Blocks --------------------------------------------------------------- | | \ / V |------------| ---------------- No blocks | N-1 Blocks | | Nth Block | --------------------------------------------------------------- | | \ / V -------------- | N-1 Blocks | ---------------- No blocks No blocks | Nth Block | --------------------------------------------------------------- * * * How, you ask do you move the N-1 blocks from one pole to another? (That could still be a lot of blocks?) Well, just treat that as a separate problem! You now have one less block and still three poles because all the blocks can still fit on any pole (since the only block you're ignoring is the biggest one), and call your program recursively, having it pretend that's all the blocks you have! Eventually (after enough recursive calls) it will have to reduce it to one block... and that's an easy enuf problem to solve! [1] You should then create a solution to the problem that works recursively (ie, does not depend on the number of blocks that are used). Think this out carefully on paper before you try implementing anything. That way you will not be confusing the process of debugging your thinking with the process of debugging your lisp code. We have attempted to shield you from getting lost in the real problem by providing you with a head start on that problem, leaving the real programming problem to you. [2] Things to consider in your implementation. [a] Representation You should first create an appropriate representation for this problem. For instance, using 3 lists named something like STACK-1, STACK-2, and STACK-3 might be one way of doing it. Another way might be to use a single list, with three sub-lists of elements. You may use whatever you want for the blocks themselves. You are advised to pick a representation which will allow you to compare whether a given block is bigger than another, so you can determine if you can stack one on another. Numbers are one way, as we have used here. [b] Generality Your solution should be able to solve an arbitrarily large number of blocks. If the solution works for cases of 1-50 blocks because you have listed out the solutions for these, then you lose. A correctly defined, recursive solution will not be bothered by this restriction (and will probably be MUCH simpler besides). [3] Think clearly! If your solution is long and complicated, it is probably wrong. The emphasis in lisp is on clarity of thought. You have the primitives available to represent this problem very cleanly. If you start getting buried in code, STOP! Look carefully at what you have done and say to yourself 'How can I generalize, where am I doing more work than I think I should be,...?' Good luck!