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.

About these ads

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);
      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;
    }
    
  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):
        print(format_header(ndisks))
        
        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 (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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: