## Tower Of Hanoi

### October 11, 2011

We begin with the function to make a move. We will simply print the instructions for the move, but if you are so inclined you could write some graphical illustration of the move instead.

`(define (move ring from to)`

(display "Move ring ")

(display ring)

(display " from tower ")

(display from)

(display " to tower ")

(display to)

(newline))

The recursive program is given below. If there is only one ring to move, it is simply moved. Otherwise, the procedure is called recursively to move all but the last ring to the intermediate tower, then the last ring is moved to the final tower, and finally is called recursively to move all but the last ring to the final tower.

`(define (hanoi ring from to helper)`

(cond ((= ring 1) (move ring from to))

(else (hanoi (- ring 1) from helper to)

(move ring from to)

(hanoi (- ring 1) helper to from))))

The recursive procedure is called like this:

`> (hanoi 5 'A 'B 'C)`

Move disk 1 from stack A to stack B

Move disk 2 from stack A to stack C

Move disk 1 from stack B to stack C

Move disk 3 from stack A to stack B

Move disk 1 from stack C to stack A

Move disk 2 from stack C to stack B

Move disk 1 from stack A to stack B

Move disk 4 from stack A to stack C

Move disk 1 from stack B to stack C

Move disk 2 from stack B to stack A

Move disk 1 from stack C to stack A

Move disk 3 from stack B to stack C

Move disk 1 from stack A to stack B

Move disk 2 from stack A to stack C

Move disk 1 from stack B to stack C

Move disk 5 from stack A to stack B

Move disk 1 from stack C to stack A

Move disk 2 from stack C to stack B

Move disk 1 from stack A to stack B

Move disk 3 from stack C to stack A

Move disk 1 from stack B to stack C

Move disk 2 from stack B to stack A

Move disk 1 from stack C to stack A

Move disk 4 from stack C to stack B

Move disk 1 from stack A to stack B

Move disk 2 from stack A to stack C

Move disk 1 from stack B to stack C

Move disk 3 from stack A to stack B

Move disk 1 from stack C to stack A

Move disk 2 from stack C to stack B

Move disk 1 from stack A to stack B

You can run the program at http://programmingpraxis.codepad.org/F8eo5XvG.

Here is my scheme solution:

purely iterative version with ASCII art in C:

Here’s an iterative solution in Python 3.

The way I remember it is:

1. Consider pairs of towers according to a repeating pattern.

2. The pattern for an even number of disks is the same as for 2 disks;

the pattern for an odd number of disks is reversed.

3. For any pair of towers, make the legal move.

#lang racket

#|

Shortest path of moving a Hanoian tower from one needle to another one.

Non recursive algorithm.

n : exact non-negative integer number

h : number of disks.

m : number of the move to be made counting from 1.

d : disk, identified in increasing order by 0 up to but not including h.

f : Position of the full tower at the start of the path (0, 1 or 2)

t : Position of the full tower after completion of the path (0, 1 or 2)

f and t must be different.

mcnt : number of moves made with disk d after m moves.

onto : needle a disk is moved to during move m.

from : needle a disk is taken from during move m.

thrd : needle not involved in move m.

posi : needle disk d is positioned at after m moves.

disk : disk being moved during move m.

|#

(require (only-in (lib “60.ss” “srfi”) log2-binary-factors))

(define (exp2 n ) (expt 2 n))

(define (mod2 n ) (modulo n 2))

(define (mod3 n ) (modulo n 3))

(define (pari n ) (add1 (mod2 (add1 n))))

(define (rotd h d f t) (mod3 (* (- t f) (pari (- h d)))))

(define (rot3 h f t) (rotd h 0 f t))

(define (mcnt m d ) (quotient (+ m (exp2 d)) (exp2 (add1 d))))

(define (thrd m h f t) (mod3 (- f (* m (rot3 h f t)))))

(define (onto m h f t) (mod3 (- (thrd m h f t) (rotd h (disk m) f t))))

(define (from m h f t) (mod3 (+ (thrd m h f t) (rotd h (disk m) f t))))

(define (posi m h d f t) (mod3 (+ f (* (rotd h d f t) (mcnt m d)))))

(define disk log2-binary-factors)

#| compute the distribution of the disks of a tower of 100 disks after

(expt 10 30) moves starting from needle 0 and going to needle 1.

|#

(time

(let ((m (expt 10 30)) (h 100) (f 0) (t 1))

(for/list ((d (in-range 0 h))) (posi m h d f t))))

; cpu time: 0 real time: 0 gc time: 0

; (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 0 2 1 1 1 1 2 0 0 2 1 1 1 0 0 1 2 0 0 0 1 1 0 0 1 1 1 2 0 0 0 0 0 1 2 0 0 2 2 0 0 0 1 1 0 2 2 0 0 2 1 0 0 1 1 1 1 1 2 2 1 0 0 1 1)

Jos

[…] to the Tower of Hanoi puzzle, especially compared to the other languages: https://programmingpraxis.com/2011/10/11/tower-of-hanoi/ Tags: code, control, hacker, hacking, programming, […]