Tower Of Hanoi
October 11, 2011
According to legend, there is a temple in Hanoi where are located sixty-four golden rings of graduated sizes and three diamond towers. Each day, the monks of the temple move a ring from one tower to another according to the rule that only one ring may be moved each day, that a single move consists of taking the highest ring from one tower and placing it on another tower, and that no ring may be placed on top of a smaller ring. The rings and towers were placed at the beginning of the world, and the monks have toiled through the ages to move all the rings from the designated starting tower to the designated finishing tower, at each day making the move that minimizes the total number of moves required. The world will end when the monks complete their work.
Actually, there is no legend; the story was concocted as a mathematical puzzle by Edouard Lucas, whom we have met in our work on primality testing. The program that determines the sequence of moves is often used as a demonstration of recursion: to move five rings from the first tower to the second, first move four rings from the first tower to the third, then move the fifth ring from the first tower to the second, then move four rings from the third tower to the second. To move four rings from the first tower to the third, first move three rings from … There is also an iterative solution, but I can never remember it, and the recursive solution is so simple that it’s the one I always use.
Your task is to write the program that calculates the sequence of moves that solved the Tower of Hanoi using the fewest number of moves. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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))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); return tower[t][n - !(n - NUM_RNG)]; } 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; }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): print(format_header(ndisks)) for disk, fm, to in hanoi(ndisks): print(format_step(disk, 'ABC'[fm], 'ABC'[to])) print()#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, […]