I saw a link today on John Cook's blog mentioning the Tower of Hanoi with four pegs. This was an extra credit problem in the algorithms class I took in school, so I looked at the article. The problem of finding the optimimum number of steps is still open. Well, there is a possible solution, but no proof that it is correct.
That extra credit problem was one of the more interesting things I worked on at school. I forgot some of the details of the solution, but went to the basement and found the copy I handed in. The solution was ugly 13 year old C code.
Wikipedia has the algorithm that is believed to be the best, so I decided to use it to check my solution. The solution uses dynamic programming, and I am re-learning lisp at the moment, so I solved the problem in lisp.
Here is the code. The result is a two by n array, where the last element in the second row is the final answer.
;; From Graham's "ANSI Common Lisp"
(defun map-int (fn n)
"Map fn over integers from 0 to n - 1"
(let ((acc nil))
(dotimes (i n)
(push (funcall fn i) acc))
(nreverse acc)))
(defun hanoi-4 (n)
"Return the number of moves needed to solve the tower of hanoi
with four poles"
(let ((memo (make-array (list 2 (1+ n))
:initial-element 0)))
;; Set up the "three pole" numbers
(dotimes (i (1+ n))
(setf (aref memo 0 i) (- (expt 2 i) 1)))
;; Do the dynamic programming.
;; For each i less than n, find the best solution to using
;; four poles. The best solution is the min of
;; 2 * T(k, 4) + T(i-k, 3) for 0 <= k < i.
;; T(u, v) is the number of moves needed to move u disks
;; using v poles.
(do ((i 1 (1+ i)))
((= i (1+ n)) memo)
(setf (aref memo 1 i)
(apply #'min
(map-int
(lambda (j)
(+ (* 2 (aref memo 1 j))
(aref memo 0 (- i j))))
i))))))
Running the test I get:
CL-USER> (hanoi-4 36)
#2A((0 1 3 7 15 31 63 127 255 511 1023 2047
4095 8191 16383 32767 65535 131071
262143 524287 1048575 2097151 4194303
8388607 16777215 33554431 67108863
134217727 268435455 536870911 1073741823
2147483647 4294967295 8589934591
17179869183 34359738367 68719476735)
(0 1 3 5 9 13 17 25 33 41 49 65 81 97
113 129 161 193 225 257 289 321 385
449 513 577 641 705 769 897 1025
1153 1281 1409 1537 1665 1793))
Here, 1793 is the solution for four pegs and 36 discs.
With dynamic programming, this solution is pretty straight forward. My memory is hazy about what I did, but basically, I did the dynamic programming part the hard way by figuring out the recursive steps ahead of time, for each value up to 36. I had a sense of what worked, but no real proof that it would work beyond the value I tried. People talk about reading their own code after a few months... I am not sure if I want to look at this close enough to figure out what exactly I was thinking.
In college, I never understood dynamic programming. We didn't spend much time on it, and it was a short chapter in our textbook. After doing a few TopCoder competitions, I finally got it.
The lisp solution took a little while, because I was trying to remember all sorts of stuff. I am sure that there are much better ways to do this... Recursion with memoization would probably be easier, but I haven't tried it yet.
