Towers of Hanoi

A classic example of a recursive algorithm implemented using ALGOL 68 to solve the Towers of Hanoi problem for one, two, three, four and five discs.


PROGRAM towers

{ Program to solve Towers of Hanoi - 20 Sep 12 - MEJT 

  This program is free software: you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the Free
  Software Foundation, either version 3 of the License, or (at your option)
  any later version.

  This program is distributed in the hope that it will be useful, but 
  WITHOUT ANY WARRANTY; without even the implied warranty of ERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  for more details. 

  You should have received a copy of the GNU General Public License along
  with this program.  If not, see <http://www.gnu.org/licenses/>
}

BEGIN

   HEAP INT counter;
   INT count;


   PROC move = (INT from, to) VOID:
   BEGIN
      IF counter MOD 7 = 0 THEN print (newline) FI;
      print ((fixed (from, 0, 0), " -> ", fixed(to, 0, 0), "   "));
      counter +:= 1
   END;


   PROC solve = (INT n, from, to, via) VOID:
   IF n > 0 THEN
      solve (n - 1, from, via, to);
      move (from, to);
      solve (n - 1, via, to, from)
   FI;


   FOR count FROM 1 TO 5 DO
      counter := 0;
      print (("Finding moves required for ", fixed(count, 0, 0)," disks:"));
      solve (count, 1, 3, 2);
      print ((newline, fixed(counter,0,0), " moves needed.", newline));
      print (newline)
   OD

END

FINISH

$ run towers
Finding moves required for 1 disks:
1 -> 3   
1 moves needed.

Finding moves required for 2 disks:
1 -> 2  1 -> 3  2 -> 3   
3 moves needed.

Finding moves required for 3 disks:
1 -> 3  1 -> 2  3 -> 2  1 -> 3  2 -> 1  2 -> 3  1 -> 3   
7 moves needed.

Finding moves required for 4 disks:
1 -> 2  1 -> 3  2 -> 3  1 -> 2  3 -> 1  3 -> 2  1 -> 2  1 -> 3   
2 -> 3  2 -> 1  3 -> 1  2 -> 3  1 -> 2  1 -> 3  2 -> 3   
15 moves needed.

Finding moves required for 5 disks:
1 -> 3  1 -> 2  3 -> 2  1 -> 3  2 -> 1  2 -> 3  1 -> 3  1 -> 2   
3 -> 2  3 -> 1  2 -> 1  3 -> 2  1 -> 3  1 -> 2  3 -> 2  1 -> 3   
2 -> 1  2 -> 3  1 -> 3  2 -> 1  3 -> 2  3 -> 1  2 -> 1  2 -> 3   
1 -> 3  1 -> 2  3 -> 2  1 -> 3  2 -> 1  2 -> 3  1 -> 3   
31 moves needed.

$

This entry was posted in Programming and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

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