Towers of Hanoi - 3

Let's look at the steps for (move 3 1 2 3):

step disk from  to  spare
  1    1    1    2    3
  2    2    1    3    2
  3    1    2    3    1
  4    3    1    2    3
  5    1    3    1    2
  6    2    3    2    1
  7    1    1    2    3

Now reorder the lines on the disk row, in reverse order:

step disk from  to  spare
  4    3    1    2    3
  2    2    1    3    2
  6    2    3    2    1
  1    1    1    2    3
  3    1    2    3    1
  5    1    3    1    2
  7    1    1    2    3

This means disk 3 is moved once, disk 2 is moved twice, and disk 1 is moved four times. What causes this?

See what happens for each disk:

1. move pile on top of disk 3 on to spare
2. move disk to destination
3. move pile back on top of disk (at destination)

So, for each move of a disk, the pile on top of it is moved twice as often:

• disk 3 is moved once
• pile on top of disk 3 (disks 1 and 2) are moved twice

• disk 2 is moved twice
• for each move of disk 2, disk 1 on top of disk 2 is moved twice

• disk 1 is moved four times

More general for a pile of n disks, for p between 1 and n:

1. move pile on top of disk p (consisting of disks 1 tru p-1) to spare
2. move disk p to destination
3. move pile at spare to destination

• disk 1 tru p-1 is moved twice as often as disk p

Therefore, the total number of moves is:

Sum(p=1 tru n) { 2^n-p }

or

2ⁿ - 1

Another observation is that:

• disk 1 is always moved in odd steps (1, 3, 5, etc.)
• disk 2 is always moved in steps 2, 6, 10, etc.
• disk 3 is always moved in steps 4, 12, 20, etc.
• disk p is always moved in step

  2^p-1 mod 2^p

Look at the following moves, depending on the number of disks, n:

n = 1
disk 1: from → to

n = 2
disk 2: from → to
disk 1: from → spare → to

n = 3
disk 3: from → to
disk 2: from → spare → to
disk 1: from → to → spare → from → to

n = k
disk k-0: from → to
disk k-1: from → spare → to
disk k-2: from → to → spare → from → to
disk k-3: from → spare → to → from → spare → to → from → spare → to
...

To find the disk of a n disk Towers of Hanoi puzzle, depending on the current value of step, use this program:

;; find-disk-for-step: number number -> number
;; find the disk that is moved in a step
;; in a n high Tower of Hanoi
;; if step is out of range, then return a -1
(define (find-disk-for-step step n)
  (if (> step (- (expt 2 n) 1))
      -1
      (find-disk-for-step-loop step n 1)))
;; find-disk-loop number number number -> number
;; check which disk is moved in a certain step
;; of the Towers of Hanoi puzzle
;; seed this recursion with disk = 1
(define (find-disk-for-step-loop step n disk)
  (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk-for-step-loop step n (+ disk 1))))

The program consists of two definitions.

There is a the definition called find-disk-for-step, which consumes step (which stands for the step, or move number, in the puzzle) and n (which stands for the total number of disks in the puzzle), and produces either the disk that is moved in that step, or a value of -1 if the value of step is out of range (too high).

Then there is the definition that is called from the first definition, as a helper definition. This second definition is called find-disk-for-step-loop, which consumes step and n, and a disk parameter, which should be seeded with the value 1. The definition tests if a disk is moved for the given values of step and n. It checks if the following condition is true:

step mod 2^disk == 2^disk-1

if it is true, disk has been found and is returned as a result, otherwise a higher value of disk is tested, by recursing the find-disk-for-step-loop with disk + 1 as an argument for the disk parameter, and the same values as before for the other parameters.

Now we now which disk is moved in a particular step, we can use what we have observed before to formulate a definition that finds the move of a disk in a certain step, expressed in the values of from, to and spare, as used as arguments in (move n from to spare). Of course, we already know what disk moves.

What we observed was, that the bottom disk in the starting position, moves as follows:

disk n: from → to

The disk on top of the bottom disk, moves as follows:

disk n-1: from → spare → to

The disk on top of that disk, moves as follows:

disk n-2: from → to → spare → from → to

In general:

disk n - (even number):
from → to → spare → from → to → spare → ...

disk n - (odd number):
from → spare → to → from → spare → to → ...

Restated as follows:

if (modulo n 2) is equal to (modulo disk 2) then:
from → to → spare → from → to → spare → ...
else:
from → spare → to → from → spare → to → ...

If we want to find how many times a disk has moved in the puzzle, based on the value of step, we can use this formula:

        step - 2^disk-1
moved = —————————————
            2^disk

If moved is equal to zero, this particular disk hasn't moved. If it's equal to one, it has moved once, etc. We can use this to determine a move, once we have established which disk moves, which is based on the value of step. Now about the details:

if (modulo n 2) is equal to (modulo disk 2) then:

in case

(= (modulo moved 3) 0)
  (print-move disk from to)

(= (modulo moved 3) 1)
  (print-move disk to spare)

(= (modulo moved 3) 2)
  (print-move disk spare from)

else:

in case

(= (modulo moved 3) 0)
  (print-move disk from spare)

(= (modulo moved 3) 1)
  (print-move disk spare to)

(= (modulo moved 3) 2)
  (print-move disk to from)

So, now we can run the value of step from 1 to 2ⁿ-1, inclusive, determine which disk is moved, what the move is, and print that to the screen.

This all is enough to write the definitions:

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (move-loop n from to spare 1))

;; calculate each move through iteration
;; using step as a counter
;; seed step with 1
(define (move-loop n from to spare step)
  (define disk (find-disk step n 1))
  (if (< step (expt 2 n))
      (begin
        (print-step-move step n disk from to spare)
        (move-loop n from to spare (+ step 1)))
      "done"))

;; print a move of a disk
(define (print-step-move step n disk from to spare)
  (define moved (/ (- step (expt 2 (- disk 1))) (expt 2 disk)))
  (cond
    [(= (modulo n 2) (modulo disk 2))
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from to)]
        [(= (modulo moved 3) 1)
         (print-move disk to spare)]
        [else
         (print-move disk spare from)])]
    [else
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from spare)]
        [(= (modulo moved 3) 1)
         (print-move disk spare to)]
        [else
         (print-move disk to from)])]))

;; print a move
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))

;; find which disk is moved in the current step
(define (find-disk step n disk)
   (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk step n (+ disk 1))))

The iterative process is not necessarily faster than the recursive process, because, in contrast to the recursive process in the Fibonacci numbers, there are no steps that could be calculated from earlier steps, or something.

Remember, that in the Fibonacci number problem,

Fib(n) = Fib(n-1) - Fib(n-2)

uses Fib(n-2) when trying to calculate Fib(n-1) (which is equal to Fib(n-2) + Fib(n-3)). This lead to inefficiency when using the formulas straight in a code definition.

In the Towers of Hanoi, on the other hand, there is no such inefficiency. A recursive or iterative process is just another way to express a solution to the problem.