Towers of Hanoi

Towers of Hanoi is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed. For other Puzzles, see Category:Puzzles.

In this task, the goal is to solve the Towers of Hanoi problem with recursivity.

Ada

with Ada.Text_Io; use Ada.Text_Io;

procedure Towers is
   type Pegs is (Left, Center, Right);
   procedure Hanoi (Ndisks : Natural; Start_Peg : Pegs := Left; Via_Peg : Pegs := Center; End_Peg : Pegs := Right) is
   begin
      if Ndisks > 0 then
         Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg);
         Put_Line("Move disk" & Natural'Image(Ndisks) & " from " & Pegs'Image(Start_Peg) & " to " &
            Pegs'Image(End_Peg));
         Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg);
      end if;
   end Hanoi;
begin
   Hanoi(4);
end Towers;

AppleScript

global moves --this is so the handler 'hanoi' can see the 'moves' variable
set moves to ""
hanoi(4, "peg A", "peg C", "peg B")

on hanoi(ndisks, fromPeg, toPeg, withPeg)
    if ndisks is greater than 0 then
        hanoi(ndisks - 1, fromPeg, withPeg, toPeg)
        set moves to moves & "Move disk " & ndisks & " from " & fromPeg & " to " & toPeg & return
        hanoi(ndisks - 1, withPeg, toPeg, fromPeg)
    end if
    return moves
end hanoi

C

#include <stdio.h>

void move(int n, int from, int to, int via)
{
  if (n > 0) {
    move(n - 1, from, via, to);
    printf("Move disk from pole %d to pole %d\n", from, to);
    move(n - 1, via, to, from);
  }
}
int main()
{
  move(4, 1,2,3);
  return 0;
}

C++

Compiler: GCC

void move(int n, int from, int to, int via) {
  if (n == 1) {
    std::cout << "Move disk from pole " << from << " to pole " << to << std::endl;
  } else {
    move(n - 1, from, via, to);
    move(1, from, to, via);
    move(n - 1, via, to, from);
  }
}

E

def move(out, n, fromPeg, toPeg, viaPeg) {
    if (n.aboveZero()) {
        move(out, n.previous(), fromPeg, viaPeg, toPeg)
        out.println(`Move disk $n from $fromPeg to $toPeg.`)
        move(out, n.previous(), viaPeg, toPeg, fromPeg)
    }
}

move(stdout, 4, def left {}, def right {}, def middle {})

Forth

With locals:

CREATE peg1 ," left "   
CREATE peg2 ," middle " 
CREATE peg3 ," right " 

: .$   COUNT TYPE ;
: MOVE-DISK 
  LOCALS| via to from n | 
  n 1 =
  IF   CR ." Move disk from " from .$ ." to " to .$ 
  ELSE n 1- from via to RECURSE 
       1    from to via RECURSE 
       n 1- via to from RECURSE 
  THEN ;

Without locals, executable pegs:

: left   ." left" ;
: right  ." right" ;
: middle ." middle" ;

: move-disk ( v t f n -- v t f )
  dup 0= if drop exit then
  1-       >R
  rot swap R@ ( t v f n-1 ) recurse
  rot swap
  2dup cr ." Move disk from " execute ."  to " execute
  swap rot R> ( f t v n-1 ) recurse
  swap rot ;
: hanoi ( n -- )
  1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ;

Haskell

Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c:

hanoi :: Integer -> a -> a -> a -> [(a, a)]
hanoi = hanoi' [] where
  hanoi' k 0 _ _ _  = k
  hanoi' k n a b c = hanoi' ((a,b):(hanoi' k (n-1) c b a)) (n-1) a c b

Here hanoi' uses an accumulator argument for the "following" moves.

One can use this function to produce output, just like the other programs:

hanoiIO n a b c = foldl (>>) (return ()) $ map f $ hanoi n a b c where
  f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y

Or, instead one can of course also program imperatively, using the IO monad directly:

hanoiM :: Integer -> IO ()
hanoiM n = hanoiM' n 1 2 3 where
  hanoiM' 0 a b c = return ()
  hanoiM' n a b c = do
    hanoiM' (n-1) a c b
    putStrLn $ "Move " ++ show a ++ " to " ++ show b
    hanoiM' (n-1) c b a

Java

 public void move(int n, int from, int to, int via) {
   if (n == 1) {
     System.out.println("Move disk from pole " + from + " to pole " + to);
   } else {
     move(n - 1, from, via, to);
     move(1, from, to, via);
     move(n - 1, via, to, from);
   }
 }

Perl

sub move {
    my $n    = shift;
    my $from = shift;
    my $to   = shift;
    my $via  = shift;

    if ($n == 1) {
        print "Move disk from pole $from to pole $to.\n";
    } else {
        move($n - 1, $from, $via, $to);
        move(1, $from, $to, $via);
        move($n - 1, $via, $to, $from);
    };
};

Pop11

define hanoi(n, src, dst, via);
if n > 0 then
    hanoi(n - 1, src, via, dst);
    printf('Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.\n');
    hanoi(n - 1, via, dst, src);
endif;
enddefine;

hanoi(4, "left", "middle", "right");

Python

def hanoi(ndisks, startPeg=1, endPeg=3):
    if ndisks:
        hanoi(ndisks-1, startPeg, 6-startPeg-endPeg)
        print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg)
        hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)

hanoi(ndisks=4)

Ruby

def hanoi n,a='left',b='middle',c='right'
    return if n==0
    hanoi (n-1),a,c,b
    puts "Move from #{a} to #{b}"
    hanoi (n-1),c,b,a
end

Seed7

const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func
  begin
    if disk > 0 then
      hanoi(pred(disk), source, via, dest);
      writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest);
      hanoi(pred(disk), via, dest, source);
    end if;
  end func;

Toka

value| sa sb sc n |
[ to sc to sb to sa to n ] is vars!
[ ( num from to via -- )
  vars!
  n 0 <>
  [
    n sa sb sc 
    n 1- sa sc sb recurse
    vars!
    ." Move a ring from " sa . ." to " sb . cr
    n 1- sc sb sa recurse
  ] ifTrue
] is hanoi