再帰を使うと美しく簡潔に解けることで有名な『ハノイの塔』を Common Lisp で塔の状態を表示しながら解いてみます。
;; 三つある塔それぞれを表現します。 ;; 三つの塔を作ります。 ;; 塔"A"の重ねてあるリングを塔"B"に移動したい。 (setq tower-a '("A" (1 2 3 4))) (setq tower-b '("B" ())) (setq tower-c '("C" ())) ;; 塔の状態を表示する関数 (defun show-tw (tower) (format t "~A:~A~%" (car tower) (reverse (cadr tower)))) ;; 三つの塔を持つハノイ。 (setq hanoi-tw (list tower-a tower-b tower-c)) ;; 三つの塔を表示する関数。 (defun show-hanoi (tw) (progn (show-tw (first hanoi-tw)) (show-tw (second hanoi-tw)) (show-tw (third hanoi-tw)))) ;; 塔の状態を表示しながらリングを移動する関数。 (defun hanoi (n from to via) (if (= n 1) ;; マイナス１しながら再帰するのでｎが１の状態にたどり着く。 ;; 一番上のリングは直接目的の棒へ移動します。 (progn (format t "--- ~A から ~A へ移動 ---~%" (car from) (car to)) (push (pop (cadr from)) (cadr to)) (show-hanoi hanoi-tw)) ;; そうでない場合は自分より上のリングを仮の場所に移動してから ;; 目的の棒へ移動します。 (progn (hanoi (- n 1) from via to) (format t "--- ~A から ~A へ移動 ---~%" (car from) (car to)) (push (pop (cadr from)) (cadr to)) (show-hanoi hanoi-tw) ;; 上のリングをその後で仮の場所から ;; 今移動した自分の上に一つ上のリングを移動します。 (hanoi (- n 1) via to from)))) (show-hanoi hanoi-tw) (hanoi 4 tower-a tower-b tower-c) ;; => 以下は移動する様子。 ;; 最初は移動する前の状態。 A:(4 3 2 1) B:NIL C:NIL --- A から C へ移動 --- A:(4 3 2) B:NIL C:(1) --- A から B へ移動 --- A:(4 3) B:(2) C:(1) --- C から B へ移動 --- A:(4 3) B:(2 1) C:NIL --- A から C へ移動 --- A:(4) B:(2 1) C:(3) --- B から A へ移動 --- A:(4 1) B:(2) C:(3) --- B から C へ移動 --- A:(4 1) B:NIL C:(3 2) --- A から C へ移動 --- A:(4) B:NIL C:(3 2 1) --- A から B へ移動 --- A:NIL B:(4) C:(3 2 1) --- C から B へ移動 --- A:NIL B:(4 1) C:(3 2) --- C から A へ移動 --- A:(2) B:(4 1) C:(3) --- B から A へ移動 --- A:(2 1) B:(4) C:(3) --- C から B へ移動 --- A:(2 1) B:(4 3) C:NIL --- A から C へ移動 --- A:(2) B:(4 3) C:(1) --- A から B へ移動 --- A:NIL B:(4 3 2) C:(1) --- C から B へ移動 --- A:NIL B:(4 3 2 1) C:NIL
4 のリングを移動しようとするが自分の上にリングがあるので3を移動しようとし、さらに再帰して2、1と・・・1を移動する。再帰が深くなって行く様子をtraceを使って表示してみる。
(defun hanoi (n from to via) (if (= n 1) (push (pop (cadr from)) (cadr to)) (progn (hanoi (- n 1) from via to) (push (pop (cadr from)) (cadr to)) (hanoi (- n 1) via to from)))) (trace hanoi) (hanoi 4 tower-a tower-b tower-c) ;; 再帰のネストが深くなる様子。 ;; 4 を B へ移動しようとする 0: (HANOI 4 ("A" (1 2 3 4)) ("B" NIL) ("C" NIL)) ;; 3 を C へ移動しようとする 1: (HANOI 3 ("A" (1 2 3 4)) ("C" NIL) ("B" NIL)) ;; 2 を B へ移動しようとする 2: (HANOI 2 ("A" (1 2 3 4)) ("B" NIL) ("C" NIL)) ;; 1 を C へ移動しようとする 3: (HANOI 1 ("A" (1 2 3 4)) ("C" NIL) ("B" NIL)) 3: HANOI returned (1) ;; 1 を C へ移動出来た ;; 2 を B へ移動出来た ;; 2 を B へ移動出来たので1 を その上へ 3: (HANOI 1 ("C" (1)) ("B" (2)) ("A" (3 4))) 3: HANOI returned (1 2) 2: HANOI returned (1 2) ;; 2 がどかれたので 3 を C へ移動出来た 2: (HANOI 2 ("B" (1 2)) ("C" (3)) ("A" (4))) 3: (HANOI 1 ("B" (1 2)) ("A" (4)) ("C" (3))) 3: HANOI returned (1 4) 3: (HANOI 1 ("A" (1 4)) ("C" (2 3)) ("B" NIL)) 3: HANOI returned (1 2 3) 2: HANOI returned (1 2 3) 1: HANOI returned (1 2 3) 1: (HANOI 3 ("C" (1 2 3)) ("B" (4)) ("A" NIL)) 2: (HANOI 2 ("C" (1 2 3)) ("A" NIL) ("B" (4))) 3: (HANOI 1 ("C" (1 2 3)) ("B" (4)) ("A" NIL)) 3: HANOI returned (1 4) 3: (HANOI 1 ("B" (1 4)) ("A" (2)) ("C" (3))) 3: HANOI returned (1 2) 2: HANOI returned (1 2) 2: (HANOI 2 ("A" (1 2)) ("B" (3 4)) ("C" NIL)) 3: (HANOI 1 ("A" (1 2)) ("C" NIL) ("B" (3 4))) 3: HANOI returned (1) 3: (HANOI 1 ("C" (1)) ("B" (2 3 4)) ("A" NIL)) 3: HANOI returned (1 2 3 4) 2: HANOI returned (1 2 3 4) 1: HANOI returned (1 2 3 4) 0: HANOI returned (1 2 3 4)
