A wooden version of the Tower of Hanoi

The Tower of Hanoi

The Tower of Hanoi is a math­e­mat­i­cal puz­zle, of­ten in­tro­duced to un­der­grad­u­ate col­lege stu­dents. At face value, the puz­zle seems point­less. You are sim­ply mov­ing discs around. Yet, some­thing is in­ter­est­ing about the puz­zle’s na­ture. After care­ful in­spec­tion, it turns out we can con­jure up a con­cise re­cur­sive al­go­rithm. If your not fa­mil­iar with re­cur­sion, con­sider check­ing out my pre­vi­ous post. In a nut­shell, re­cur­sion is use­ful when a prob­lem can be bro­ken down into smaller prob­lems of the same form as the orig­i­nal. With some imag­i­na­tion, the Tower of Hanoi meets this re­quire­ment.

Why?

And you may be won¬≠der¬≠ing why you should care. After all, there is an it¬≠er¬≠a¬≠tive so¬≠lu¬≠tion to the puz¬≠zle‚ÄĒjust do a Google search. Well, this toy prob¬≠lem shows that re¬≠cur¬≠sion can in¬≠spire sim¬≠pler code than it¬≠er¬≠a¬≠tion. Although I‚Äôm not go¬≠ing to cover the it¬≠er¬≠a¬≠tive so¬≠lu¬≠tion ex¬≠plic¬≠itly here, you should look it up. By com¬≠par¬≠ing the two so¬≠lu¬≠tions, it‚Äôs clear that the re¬≠cur¬≠sive one fea¬≠tures less code and eas¬≠ier to read.

Given the para¬≠graph above, I am go¬≠ing to em¬≠pha¬≠size that re¬≠cur¬≠sion is¬≠n‚Äôt a su¬≠per¬≠Ô¨āu¬≠ous, com¬≠pli¬≠cated tech¬≠nique. It has le¬≠git¬≠i¬≠mate uses in the real world. If it will make your code eas¬≠ier to write and un¬≠der¬≠stand, con¬≠sider us¬≠ing it. Now, it‚Äôs not al¬≠ways bet¬≠ter. You should also be aware of the per¬≠for¬≠mance trade¬≠offs‚ÄĒpar¬≠tic¬≠u¬≠larly in lan¬≠guages with¬≠out tail call op¬≠ti¬≠miza¬≠tion.

The Rules

For those un¬≠fa¬≠mil¬≠iar with the puz¬≠zle, I‚Äôll quickly ex¬≠plain the rules. There is a board with three poles and an arrange¬≠ment of disks. The disks are each of a dif¬≠fer¬≠ent size, and ini¬≠tially, they are arranged in a cone shape on a sin¬≠gle pole. The goal is to move all the disks‚Äďone at a time‚Äďto an¬≠other a pole, once again form¬≠ing the cone shape. Also, a larger disk can¬≠not be stacked on top of a smaller disk at any time.

Initial state for the Tower of Hanoi Puzzle

Recursive Solution

Once again, the Tower of Hanoi can be solved re¬≠cur¬≠sively. It works be¬≠cause we can split the game into sub¬≠puz¬≠zles. These sub¬≠puz¬≠zles are them¬≠selves a miniver¬≠sion of The Tower of Hanoi‚Äďwhich can then be solved in the same fash¬≠ion as the big¬≠ger ver¬≠sion. To note, the al¬≠go¬≠rithm will al¬≠ways pro¬≠duce a valid set of game-win¬≠ning moves. So you can win the game every time.

Before jump¬≠ing into the code, let‚Äôs imag¬≠ine what the so¬≠lu¬≠tion‚Äôs struc¬≠ture could look like. To start, we‚Äôll la¬≠bel the three poles A, B, and C. Then, let‚Äôs say there‚Äôs a stack of h disks on pole A. This arrange¬≠ment is the ini¬≠tial setup‚Äďno sur¬≠prises here. As a re¬≠minder, to win, the player needs to move all the disks to an¬≠other pole.

Yet, to move pole A‚Äôs largest disk, h-1 disks need to be shuf¬≠Ô¨āed to an aux¬≠il¬≠iary pole‚Äďlet‚Äôs say pole B. Of course, this is just solv¬≠ing a slightly smaller ver¬≠sion of the same puz¬≠zle. So, we need to move h-2 disks some¬≠where‚Ķ You should see where this is go¬≠ing.

What hap¬≠pens when we have re¬≠duced our way to sub¬≠puz¬≠zle con¬≠sist¬≠ing of one disk? This sit¬≠u¬≠a¬≠tion is the eas¬≠i¬≠est to han¬≠dle‚Äďjust move di¬≠rectly move the disk to the tar¬≠get pole‚Äďin this case pole C.

Now, in gen¬≠eral, once the largest disk of a sub¬≠puz¬≠zle has moved been moved the tar¬≠get pole, we can then move all the disks placed on the aux¬≠il¬≠iary pole over to the tar¬≠get pole as well. To do this, we are again just solv¬≠ing a smaller ver¬≠sion of the puz¬≠zle‚Äďwe are just chang¬≠ing which poles are la¬≠beled as the aux¬≠il¬≠iary and the tar¬≠get.

In sum­mary, we are re­peat­edly mov­ing the large disk of a sub­puz­zle af­ter the smaller disks above have been moved to the aux­il­iary pole. The key is to cor­rectly track which poles should be the tar­get and the aux­il­iary as the al­go­rithm twists through the self calls. Assuming we do this cor­rectly, the puz­zle will be solved by solv­ing all the sub­puz­zles in turn.

An animation showing a solution to the three disk version of the Tower of Hanoi puzzle

Some Code

Let‚Äôs stop talk¬≠ing the¬≠ory and look at some code. Below, I wrote a so¬≠lu¬≠tion in Racket that al¬≠lows you to change the num¬≠ber of disks. Since im¬≠mutable data struc¬≠tures are used, the code is a lit¬≠tle dif¬≠fer¬≠ent than what you typ¬≠i¬≠cally Ô¨Ānd on the Internet; how¬≠ever, the core con¬≠cepts are still the same. You should be able to map my nat¬≠ural lan¬≠guage de¬≠scrip¬≠tion to the code. At the very least, note what the base case is and how the prob¬≠lem space is re¬≠duced every self call.

#lang racket

(struct board (A B C) #:transparent)

(define (new-board size)
  (board (range 1 (add1 size)) '() '()))

(define (pop stack)
  (cond
    [(empty? stack) '()]
    [else (cdr stack)]))

(define (peak stack)
  (cond
    [(empty? stack) '()]
    [else (list (car stack))]))

(define (move brd pole1 pole2)
  (define table
    (hash 'A (board-A brd)
          'B (board-B brd)
          'C (board-C brd)))
  (define (check stack pole)
    (cond
      [(eq? pole pole1) (pop stack)]
      [(eq? pole pole2) (append (peak (hash-ref table pole1)) stack)]
      [else stack]))
  (board (check (board-A brd) 'A) (check (board-B brd) 'B) (check (board-C brd) 'C)))

(define (solve size)
  (cond
    [(<= size 2) (raise-user-error "Size must be greater than two")]
    [else
     (define board (new-board size))
     (helper size board 'A 'C 'B)]))

(define (helper n brd source target auxiliary)
  (cond
    [(n . > . 0)
     (define new-brd-1 (helper (sub1 n) brd source auxiliary target))
     (define new-brd-2 (move new-brd-1 source target))
     (displayln new-brd-2)
     (helper (sub1 n) new-brd-2 auxiliary target source)]
    [else brd]))
    
(module+ main
  (solve 3))

Here‚Äôs the out¬≠put from the code‚Äďwith the size pa¬≠ra¬≠me¬≠ter set to three. The left-hand side is the top of each stack. With a lit¬≠tle squint¬≠ing, you should be able to trace out the cor¬≠rect se¬≠ries of moves to solve the puz¬≠zle.

Console Output
$ #(struct:board (2 3) () (1))
$ #(struct:board (3) (2) (1))
$ #(struct:board (3) (1 2) ())
$ #(struct:board () (1 2) (3))
$ #(struct:board (1) (2) (3))
$ #(struct:board (1) () (2 3))
$ #(struct:board () () (1 2 3))
$ (board '() '() '(1 2 3))