## 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.

Pages: 1 2

### 5 Responses to “Tower Of Hanoi”

1. Dmitriy Borodiy said

Here is my scheme solution:

```(define (hanoi n)
(define (move-disks from to quantity)
(if (eq? quantity 1)
(printf "Move disk from ~a to ~a~%" from to)
(let ((aux (- 6 (+ from to))))
(move-disks from aux (sub1 quantity))
(move-disks from to 1)
(move-disks aux to (sub1 quantity)))))
(move-disks 1 3 n))
```
2. ardnew said

purely iterative version with ASCII art in C:

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_TOW 3
#define NUM_RNG 5

#define TOWER_1 0
#define TOWER_2 1
#define TOWER_3 2

#define RING '='
#define POST '|'

int tower[NUM_TOW][NUM_RNG];

void print_towers(int k)
{
int i, j, n, u, v;
char *s;

printf("\n\nStep (%d):\n\n", k);

for (j = 0; j < NUM_RNG; ++j)
{
for (i = 0; i < NUM_TOW; ++i)
{
s = malloc(NUM_RNG * sizeof(*s));
memset(s, 0, NUM_RNG);

n  = NUM_RNG / 2;

u = tower[i][j];
v = !u;

memset(s, ' ', n);
memset(s + n, RING + v * (POST - RING), u + v - u * v);
memset(s + n + u + v, ' ', n);

printf("%*s", NUM_TOW + NUM_RNG + 1, s);
}
printf("\n");
}
printf("\n");
}

void init_towers()
{
int i, j;

for (i = 0; i < NUM_TOW; ++i)
for (j = 0; j < NUM_RNG; ++j)
tower[i][j] = (j + 1) * !i;
}

int top(int t)
{
int i = NUM_RNG;
while (tower[t][i - 1] && --i);
return i;
}

int top_ring(int t)
{
int n = top(t);
}

void swap(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

void move(int a, int b)
{
int ar = top_ring(a);
int br = top_ring(b);

if (ar && (!br || (br > ar))) swap(&a, &b);

tower[a][top(a) - 1] = top_ring(b);
tower[b][top(b)]     = 0;
}

void hanoi()
{
int x, n = 0;
while (top(TOWER_3))
{
x = ++n % NUM_TOW;
move(!x, 1 + !(x >> 1));
print_towers(n);
}
}

int main(void)
{
init_towers();
print_towers(0);
hanoi();
return 0;
}
```
3. Mike said

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.

```from collections import deque
from itertools import cycle

def hanoi(ndisks):
'''Generate moves to solve the Tower of Hanoi.

input  - number of disks
output - sequence of tuples of the form (disk, from, to)
'''

tower = [deque(range(ndisks)), deque(), deque()]

pattern = ((0,1),(0,2),(1,2)) if ndisks&1 != 1 else ((0,2),(0,1),(1,2))

for fm, to in cycle(pattern):
if not tower[fm] or tower[to] and tower[to] < tower[fm]:
fm, to = to, fm

yield tower[fm][0], fm, to

tower[to].appendleft(tower[fm].popleft())

if len(tower[2]) == ndisks:
break

# test
format_header = "Solution for {}-disk Towers of Hanoi:".format
format_step = "Move disk {} from tower {} to tower {}.".format

for ndisks in range(1,5):

for disk, fm, to in hanoi(ndisks):
print(format_step(disk, 'ABC'[fm], 'ABC'[to]))

print()

```
4. Jos Koot said

#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 (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

5. […] 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, […]