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

ActionScript

<lang actionscript>public function move(n:int, from:int, to:int, via:int):void {

   if (n > 0)
   {
       move(n - 1, from, via, to);
       trace("Move disk from pole " + from + " to pole " + to);
       move(n - 1, via, to, from);
   }

}</lang>

Ada

<lang 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; End_Peg : Pegs := Right; Via_Peg : Pegs := Center) 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;</lang>

Agena

<lang agena>move := proc(n::number, src::number, dst::number, via::number) is

  if n > 0 then
     move(n - 1, src, via, dst)
     print(src & ' to ' & dst)
     move(n - 1, via, dst, src)
  fi

end

move(4, 1, 2, 3)</lang>

ALGOL 68

<lang algol68>PROC move = (INT n, from, to, via) VOID:

 IF n > 0 THEN
   move(n - 1, from, via, to);
   printf(($"Move disk from pole "g" to pole "gl$, from, to));
   move(n - 1, via, to, from)
 FI

main: (

 move(4, 1,2,3)

)</lang>

AmigaE

<lang amigae>PROC move(n, from, to, via)

 IF n > 0
   move(n-1, from, via, to)
   WriteF('Move disk from pole \d to pole \d\n', from, to)
   move(n-1, via, to, from)
 ENDIF

ENDPROC

PROC main()

 move(4, 1,2,3)

ENDPROC</lang>

AppleScript

<lang 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</lang>

AutoHotkey

<lang AutoHotkey>move(n, from, to, via) ;n = # of disks, from = start pole, to = end pole, via = remaining pole {

 if (n = 1)
 {
   msgbox , 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)
 }

}</lang>

AWK

Translation of: Logo

<lang AWK>$ awk 'func hanoi(n,f,t,v){if(n>0){hanoi(n-1,f,v,t);print(f,"->",t);hanoi(n-1,v,t,f)}} BEGIN{hanoi(4,"left","middle","right")}' left -> right left -> middle right -> middle left -> right middle -> left middle -> right left -> right left -> middle right -> middle right -> left middle -> left right -> middle left -> right left -> middle right -> middle</lang>

BASIC

Works with: FreeBASIC

Works with: RapidQ

<lang freebasic> SUB move (n AS Integer, fromPeg AS Integer, toPeg AS Integer, viaPeg AS Integer)

   IF n>0 THEN
       move n-1, fromPeg, viaPeg, toPeg
       PRINT "Move disk from "; fromPeg; " to "; toPeg
       move n-1, viaPeg, toPeg, fromPeg
   END IF

END SUB

move 4,1,2,3 </lang>

C

<lang 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;

}</lang>

C#

<lang csharp>public void move(int n, int from, int to, int via) {

  if (n == 1) {
    System.Console.WriteLine("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);
  }
}</lang>

C++

Works with: g++

<lang cpp>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);
 }

}</lang>

Clojure

<lang lisp>(defn towers-of-hanoi [n from to via]

      (if (= n 1)
        (println (format "Move from %s to %s" from to))
        (do
          (towers-of-hanoi (dec n) from via to)
          (println (format "Move from %s to %s" from to))
          (recur (dec n) via to from))))</lang>

Common Lisp

<lang lisp>(defun move (n from to via)

 (cond ((= n 1)
        (format t "Move from ~A to ~A.~%" from to))
       (t
        (move (- n 1) from via to)
        (format t "Move from ~A to ~A.~%" from to)
        (move (- n 1) via to from))))</lang>

D

Recursive

<lang d>module hanoi; import std.stdio;

struct Hanoi { static Hanoi opCall(int n, string src, string dst, string via) { return (n > 0) ? Hanoi(n - 1, src, via, dst)(n, src, dst)(n - 1, via, dst, src) : Hanoi.init ; } static Hanoi opCall(int n, string src, string dst) { writefln("Move disk %s from %s to %s", n, src, dst) ; return Hanoi.init ; } }

void main() { Hanoi(3, "L","M","R") ; }</lang>

Iterative

ref : The shortest and "mysterious" TH algorithm <lang d>module hanoi; import std.stdio; import std.conv ;

void Hanoi(int n , string L /* from */, string M /* to */, string R /* via */) {

 string[3] Pegs = [L,R,M] ;
 int nn = (1 << n) ;
 int x, fr, to, i, j ;
 for(x = 1 ; x < nn ; x++){
   i =  x & x - 1       ; fr = (i + i/3) & 3 ;
   i = (x | x - 1) + 1  ; to = (i + i/3) & 3 ;
   for(i = x, j = 1; !(i&1) ; i >>=1, j++) 
       writefln("Move Disc %d from %s to %s", j, Pegs[fr], Pegs[to]) ;
 }

}

void main(string[] args) {

 int n = (args.length > 1) ? to!(int)(args[1]) : 3 ;
 Hanoi(n, "L","M","R") ;

}</lang>

Dc

From Here

 [ # move(from, to)
    n           # print from
    [ --> ]n    # print " --> "
    p           # print to\n
    sw          # p doesn't pop, so get rid of the value
 ]sm
 
 [ # init(n)
    sw          # tuck n away temporarily
    9           # sentinel as bottom of stack
    lw          # bring n back
    1           # "from" tower's label
    3           # "to" tower's label
    0           # processed marker
 ]si
 
 [ # Move()
    lt          # push to
    lf          # push from
    lmx         # call move(from, to)
 ]sM
 
 [ # code block<lang dc>
    ln          # push n
    lf          # push from
    lt          # push to
    1           # push processed marker 1
    ln          # push n
    1           # push 1
    -           # n - 1
    lf          # push from
    ll          # push left
    0           # push processed marker 0
 ]sd
 
 [ # code block <e>
    ln          # push n
    1           # push 1
    -           # n - 1
    ll          # push left
    lt          # push to
    0           # push processed marker 0
 ]se
 
 [ # code block <x>
    ln 1 =M
    ln 1 !=d
 ]sx
 
 [ # code block <y>
    lMx
    lex
 ]sy
 
 [ # quit()
    q           # exit the program
 ]sq
 
 [ # run()
    d 9 =q      # if stack empty, quit()
    sp          # processed
    st          # to
    sf          # from
    sn          # n
    6           #
    lf          #
    -           #
    lt          #
    -           # 6 - from - to
    sl          #
    lp 0 =x     #
    lp 0 !=y    #
    lrx         # loop
 ]sr
 
 5lix # init(n)
 lrx # run()

E

<lang 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 {})</lang>

Erlang

<lang erlang>move(1, F, T, _V) ->

 io:format("Move from ~p to ~p~n", [F, T]);

move(N, F, T, V) ->

 move(N-1, F, V, T), 
 move(1  , F, T, V),
 move(N-1, V, T, F).</lang>

FALSE

<lang false>["Move disk from "$!\" to "$!\" "]p: { to from } [n;0>[n;1-n: @\ h;! @\ p;! \@ h;! \@ n;1+n:]?]h: { via to from } 4n:["right"]["middle"]["left"]h;!%%%</lang>

Forth

With locals:

<lang forth>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 ;</lang>

Without locals, executable pegs:

<lang forth>: 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 ;</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>PROGRAM TOWER

 CALL Move(4, 1, 2, 3)
               

CONTAINS

 RECURSIVE SUBROUTINE Move(ndisks, from, to, via)
   INTEGER, INTENT (IN) :: ndisks, from, to, via
  
   IF (ndisks == 1) THEN
      WRITE(*, "(A,I1,A,I1)") "Move disk from pole ", from, " to pole ", to
   ELSE
      CALL Move(ndisks-1, from, via, to)
      CALL Move(1, from, to, via)
      CALL Move(ndisks-1, via, to, from)
   END IF
 END SUBROUTINE Move

END PROGRAM TOWER</lang>

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:

<lang haskell>hanoi :: Integer -> a -> a -> a -> [(a, a)] hanoi 0 _ _ _ = [] hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a</lang>

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

<lang haskell>hanoiIO n = mapM_ f $ hanoi n 1 2 3 where

 f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y</lang>

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

<lang haskell>hanoiM :: Integer -> IO () hanoiM n = hanoiM' n 1 2 3 where

 hanoiM' 0 _ _ _ = 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</lang>

Io

<lang io>hanoi := method(n, from, to, via,

 if (n == 1) then (
   writeln("Move from ", from, " to ", to)
 ) else (
   hanoi(n - 1, from, via, to  )
   hanoi(1    , from, to , via )
   hanoi(n - 1, via , to , from)
 )

)</lang>

Ioke

<lang ioke> = method(n, f, u, t,

 if(n < 2,
   "#{f} --> #{t}" println,

   H(n - 1, f, t, u)
   "#{f} --> #{t}" println
   H(n - 1, u, f, t)
 )

)

hanoi = method(n,

 H(n, 1, 2, 3)

)</lang>

J

<lang j>H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. *

H1=: monad define

 if. *y do.
   ({&0 2 1 , 0 2 , {&1 0 2) H1 y-1
 else.
   i.0 2
 end.

)</lang> H employs anonymous recursion; H1 is an "explicit" statement of the same computation. For example: <lang j> H 3 0 2 0 1 2 1 0 2 1 2 1 0 2 0</lang> The result is a 2-column table; a row i,j is interpreted as: move a disk (the top disk) from peg i to peg j .

Java

<lang 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);
 }

}</lang>

JavaScript

<lang javascript>function move(n, from, to, via) {

 if (n > 0) {
   move(n-1, from, via, to)
   print("Move disk from " + from + " to " + to)
   move(n-1, via, to, from)
 }

} move(4, "left", "middle", "right")</lang>

Joy

From here <lang joy>DEFINE hanoi == [[rolldown] infra] dip

               [ [ [null] [pop pop] ] 
                 [ [dup2 [[rotate] infra] dip pred] 
                   [ [dup rest put] dip 
                     [[swap] infra] dip pred ] 
                   [] ] ] 
               condnestrec.</lang>

Using it (5 is the number of disks.) <lang joy>[source destination temp] 5 hanoi.</lang>

Logo

<lang logo>to move :n :from :to :via

 if :n = 0 [stop]
 move :n-1 :from :via :to
 (print [Move disk from] :from [to] :to)
 move :n-1 :via :to :from

end move 4 "left "middle "right</lang>

Lua

<lang Lua> function move(n, src, dst, via)

   if n > 0 then
       move(n - 1, src, via, dst)
       print(src, 'to', dst)
       move(n - 1, via, dst, src)
   end

end

move(4, 1, 2, 3) </lang>

Mathematica

<lang mathematica>Hanoi[0, from_, to_, via_] := Null Hanoi[n_Integer, from_, to_, via_] :=

 (Hanoi[n-1, from, via, to];
  Print["Move dist from pole ", from, " to ", to, "."];
  Hanoi[n-1, via, from, to])</lang>

Modula-3

<lang modula3>MODULE Hanoi EXPORTS Main;

FROM IO IMPORT Put; FROM Fmt IMPORT Int;

PROCEDURE doHanoi(n, from, to, using: INTEGER) =

 BEGIN
   IF n > 0 THEN
     doHanoi(n - 1, from, using, to);
     Put("move " & Int(from) & " --> " & Int(to) & "\n");
     doHanoi(n - 1, using, to, from);
   END;
 END doHanoi;

BEGIN

 doHanoi(4, 1, 2, 3);

END Hanoi.</lang>

Nimrod

<lang Python>proc hanoi(disks: int, fromTower: string, toTower: string, viaTower: string) =

 if disks != 0:
   hanoi(disks - 1, fromTower, viaTower, toTower)
   echo("Move disk ", disks, " from ", fromTower, " to ", toTower)
   hanoi(disks - 1, viaTower, toTower, fromTower)
   

hanoi(4, "1", "2", "3")</lang> Output: <lang>Move disk 1 from 1 to 3 Move disk 2 from 1 to 2 Move disk 1 from 3 to 2 Move disk 3 from 1 to 3 Move disk 1 from 2 to 1 Move disk 2 from 2 to 3 Move disk 1 from 1 to 3 Move disk 4 from 1 to 2 Move disk 1 from 3 to 2 Move disk 2 from 3 to 1 Move disk 1 from 2 to 1 Move disk 3 from 3 to 2 Move disk 1 from 1 to 3 Move disk 2 from 1 to 2 Move disk 1 from 3 to 2</lang>

Objective-C

From here

This has been tested on GNUstep compiler. But it should be compatible with XCode/Cocoa on MacOS too.

The Interface - TowersOfHanoi.h: <lang objc>#import <Foundation/NSObject.h>

@interface TowersOfHanoi: NSObject { int pegFrom; int pegTo; int pegVia; int numDisks; }

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks; -(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks; @end</lang>

The Implementation - TowersOfHanoi.m:

<lang objc>#import "TowersOfHanoi.h" @implementation TowersOfHanoi

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks { pegFrom = from; pegTo = to; pegVia = via; numDisks = disks; }

-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks { if (disks == 1) {

           printf("Move disk from pole %i to pole %i\n", from, to);
       } else {
			[self movePegFrom: from andMovePegTo: via andMovePegVia: to andWithNumDisks: disks-1];

[self movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: 1]; [self movePegFrom: via andMovePegTo: to andMovePegVia: from andWithNumDisks: disks-1];

       }

}

@end</lang>

Test code: TowersTest.m:

<lang objc>#import <stdio.h>

1. import "TowersOfHanoi.h"

int main( int argc, const char *argv[] ) { TowersOfHanoi *tower = [[TowersOfHanoi alloc] init];

int from = 1; int to = 3; int via = 2; int disks = 3;

[tower setPegFrom: from andSetPegTo: to andSetPegVia: via andSetNumDisks: disks];

[tower movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: disks];

[tower release];

return 0; }</lang>

OCaml

<lang ocaml>let rec hanoi n a b c =

 if n <> 0 then begin
   hanoi (pred n) a c b;
   Printf.printf "Move disk from pole %d to pole %d\n" a b;
   hanoi (pred n) c b a
 end

let () =

 hanoi 4 1 2 3</lang>

Octave

<lang octave>function hanoimove(ndisks, from, to, via)

 if ( ndisks == 1 )
   printf("Move disk from pole %d to pole %d\n", from, to);
 else
   hanoimove(ndisks-1, from, via, to);
   hanoimove(1, from, to, via);
   hanoimove(ndisks-1, via, to, from);
 endif

endfunction

hanoimove(4, 1, 2, 3);</lang>

Oz

<lang oz>declare

 proc {TowersOfHanoi N From To Via}
    if N > 0 then
       {TowersOfHanoi N-1 From Via To}
       {System.showInfo "Move from "#From#" to "#To}
       {TowersOfHanoi N-1 Via To From}
    end
 end

in

 {TowersOfHanoi 4 left middle right}</lang>

Pascal

Compiler: Free Pascal (2.0.4)

I think it is standard pascal, except for the constant array "strPole". I am not sure if constant arrays are part of the standard. However, as far as I know, they are a "de facto" standard in every compiler.

<lang pascal>program Hanoi; type

 TPole = (tpLeft, tpCenter, tpRight);

const

 strPole:array[TPole] of string[6]=('left','center','right');

procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole);
begin
 if Ndisks >0 then begin
    MoveStack(Ndisks - 1, Origin,Auxiliary, Destination );
    Writeln('Move disk ',Ndisks ,' from ',strPole[Origin],' to ',strPole[Destination]);
    MoveStack(Ndisks - 1, Auxiliary, Destination, origin);
 end;
end;

begin

MoveStack(4,tpLeft,tpCenter,tpRight);

end.</lang>

A little longer, but clearer for my taste <lang pascal>program Hanoi; type

 TPole = (tpLeft, tpCenter, tpRight);

const

 strPole:array[TPole] of string[6]=('left','center','right');

procedure MoveOneDisk(const DiskNum:integer; const Origin,Destination:TPole);
begin
 Writeln('Move disk ',DiskNum,' from ',strPole[Origin],' to ',strPole[Destination]);
end;

procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole);
begin
 if Ndisks =1 then
      MoveOneDisk(1,origin,Destination)
 else begin
      MoveStack(Ndisks - 1, Origin,Auxiliary, Destination );
      MoveOneDisk(Ndisks,origin,Destination);
      MoveStack(Ndisks - 1, Auxiliary, Destination, origin);
 end;
end;

begin

MoveStack(4,tpLeft,tpCenter,tpRight);

end.</lang>

Perl

<lang perl>sub hanoi {

   my ($n, $from, $to, $via) = (@_, 1, 2, 3);

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

};</lang>

Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>subset Peg of Int where * == 1|2|3;

multi hanoi (0, Peg $a, Peg $b, Peg $c) { } multi hanoi (Int $n, Peg $a = 1, Peg $b = 2, Peg $c = 3) {

   hanoi $n - 1, $a, $c, $b;
   say "Move $a to $b.";
   hanoi $n - 1, $c, $b, $a;

}</lang>

PHP

Translation of: Java

<lang php>function move($n,$from,$to,$via) {

   if ($n === 1) {
       print("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);
   }

}</lang>

PicoLisp

<lang PicoLisp>(de move (N A B C) # Use: (move 3 'left 'center 'right)

  (unless (=0 N)
     (move (dec N) A C B)
     (println 'Move 'disk 'from A 'to B)
     (move (dec N) C B A) ) )</lang>

Pop11

<lang pop11>define hanoi(n, src, dst, via); if n > 0 then

   hanoi(n - 1, src, via, dst);
   'Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.' =>
   hanoi(n - 1, via, dst, src);

endif; enddefine;

hanoi(4, "left", "middle", "right");</lang>

PL/I

<lang PL/I> /* From Rosetta Fortran */ tower: proc options (main);

  call Move (4,1,2,3);

Move: procedure (ndiscs, from, to, via) recursive;

  declare (ndiscs, from, to, via) fixed binary;

  if ndiscs = 1 then
     put skip edit ('Move disc from pole ', trim(from), ' to pole ',
        trim(to) ) (a);
  else
     do;
        call Move (ndiscs-1, from, via, to);
        call Move (1, from, to, via);
        call Move (ndiscs-1, via, to, from);
     end;

end Move;

end tower; </lang>

PureBasic

Algorithm according to http://en.wikipedia.org/wiki/Towers_of_Hanoi <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

 If n
   Hanoi(n-1, A, B, C)
   PrintN("Move the plate from "+A+" to "+C)
   Hanoi(n-1, B, C, A)
 EndIf

EndProcedure</lang>

Full program <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

 If n
   Hanoi(n-1, A, B, C)
   PrintN("Move the plate from "+A+" to "+C)
   Hanoi(n-1, B, C, A)
 EndIf

EndProcedure

If OpenConsole()

 Define n=3
 PrintN("Moving "+Str(n)+" pegs."+#CRLF$)
 Hanoi(n,"Left Peg","Middle Peg","Right Peg")
 PrintN(#CRLF$+"Press ENTER to exit."): Input()

EndIf</lang>

Outputs

Moving 3 pegs.

Move the plate from Left Peg to Middle Peg
Move the plate from Left Peg to Right Peg
Move the plate from Middle Peg to Right Peg
Move the plate from Left Peg to Middle Peg
Move the plate from Right Peg to Left Peg
Move the plate from Right Peg to Middle Peg
Move the plate from Left Peg to Middle Peg

Press ENTER to exit.

Python

<lang 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)</lang>

R

Translation of: Octave

<lang R>hanoimove <- function(ndisks, from, to, via) {

 if ( ndisks == 1 )
   cat("move disk from", from, "to", to, "\n")
 else {
   hanoimove(ndisks-1, from, via, to)
   hanoimove(1, from, to, via)
   hanoimove(ndisks-1, via, to, from)
 }

}

hanoimove(4,1,2,3)</lang>

REBOL

<lang REBOL>REBOL [ Title: "Towers of Hanoi" Author: oofoe Date: 2009-12-08 URL: http://rosettacode.org/wiki/Towers_of_Hanoi ]

hanoi: func [ {Begin moving the golden disks from one pole to the next. Note: when last disk moved, the world will end.} disks [integer!] "Number of discs on starting pole." /poles "Name poles." from to via ][

   if disks = 0 [return]

if not poles [from: 'left to: 'middle via: 'right]

   hanoi/poles disks - 1 from via to

print [from "->" to]

   hanoi/poles disks - 1 via to from

]

hanoi 4</lang>

Output:

left -> right
left -> middle
right -> middle
left -> right
middle -> left
middle -> right
left -> right
left -> middle
right -> middle
right -> left
middle -> left
right -> middle
left -> right
left -> middle
right -> middle

Ruby

<lang ruby>def hanoi n,from='left',to='middle',via='right'

   return if n==0
   hanoi (n-1), from, via, to
   puts "Move from #{from} to #{to}"
   hanoi (n-1), via, to, from

end</lang>

Scala

<lang scala>def move(n: int, from: int, to: int, via: int) = {

   if (n == 1) {
     Console.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)
   }
 }</lang>

This next example is from http://gist.github.com/66925 it is a translation to Scala of a Prolog solution and solves the problem at compile time <lang scala>object TowersOfHanoi {

 import scala.reflect.Manifest
 
 def simpleName(m:Manifest[_]):String = {
   val name = m.toString
   name.substring(name.lastIndexOf('$')+1)
 }
 
 trait Nat
 final class _0 extends Nat
 final class Succ[Pre<:Nat] extends Nat

 type _1 = Succ[_0]
 type _2 = Succ[_1]
 type _3 = Succ[_2]
 type _4 = Succ[_3]

 case class Move[N<:Nat,A,B,C]()

 implicit def move0[A,B,C](implicit a:Manifest[A],b:Manifest[B]):Move[_0,A,B,C] = {
       System.out.println("Move from "+simpleName(a)+" to "+simpleName(b));null
 }

 implicit def moveN[P<:Nat,A,B,C](implicit m1:Move[P,A,C,B],m2:Move[_0,A,B,C],m3:Move[P,C,B,A])
  :Move[Succ[P],A,B,C] = null
 
 def run[N<:Nat,A,B,C](implicit m:Move[N,A,B,C]) = null
 
 case class Left()
 case class Center()
 case class Right()
 
 def main(args:Array[String]){
   run[_2,Left,Right,Center]
 }

}</lang>

Scheme

<lang scheme>(define (hanoi n a b c)

 (if (> n 0)
   (begin
     (hanoi (- n 1) a c b)
     (display "Move disk from pole ")
     (display a)
     (display " to pole ")
     (display b)
     (newline)
     (hanoi (- n 1) c b a))))

(hanoi 4 1 2 3)</lang>

Seed7

<lang 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;</lang>

Tcl

The use of interp alias shown is a sort of closure: keep track of the number of moves required <lang tcl>interp alias {} hanoi {} do_hanoi 0

proc do_hanoi {count n {from A} {to C} {via B}} {

   if {$n == 1} {
       interp alias {} hanoi {} do_hanoi [incr count]
       puts "$count: move from $from to $to"
   } else {
       incr n -1
       hanoi $n $from $via $to
       hanoi 1  $from $to $via
       hanoi $n $via $to $from
   }

}

hanoi 4</lang> produces

1: move from A to B
2: move from A to C
3: move from B to C
4: move from A to B
5: move from C to A
6: move from C to B
7: move from A to B
8: move from A to C
9: move from B to C
10: move from B to A
11: move from C to A
12: move from B to C
13: move from A to B
14: move from A to C
15: move from B to C

Toka

<lang 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</lang>

UNIX Shell

Works with: bash

<lang bash>#!/bin/bash

move() {

 local n="$1"
 local from="$2"
 local to="$3"
 local via="$4"

 if "$n" == "1" 
 then
   echo "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
 fi

}

move $1 $2 $3 $4</lang>

Ursala

<lang Ursala>#import nat

move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC

1. show+

main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'></lang> output:

start -> middle
start -> end
middle -> end
start -> middle
end -> start
end -> middle
start -> middle
start -> end
middle -> end
middle -> start
end -> start
middle -> end
start -> middle
start -> end
middle -> end

Vedit macro language

This implementation outputs the results in current edit buffer. <lang vedit>#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2 Call("MOVE_DISKS") Return

// Move disks // #1 = from, #2 = to, #3 = via, #4 = number of disks //

MOVE_DISKS:

if (#4 > 0) {

   Num_Push(1,4)
       #9=#2; #2=#3; #3=#9; #4--       // #1 to #3 via #2
       Call("MOVE_DISKS")
   Num_Pop(1,4)

   Ins_Text("Move a disk from ")       // move one disk
   Num_Ins(#1, LEFT+NOCR)
   Ins_Text(" to ")
   Num_Ins(#2, LEFT)

   Num_Push(1,4)
       #9=#1; #1=#3; #3 = #9; #4--     // #3 to #2 via #1
       Call("MOVE_DISKS")
   Num_Pop(1,4)

} Return</lang>

Visual Basic .NET

<lang vbnet>Module TowersOfHanoi

   Sub MoveTowerDisks(ByVal disks As Integer, ByVal fromTower As Integer, ByVal toTower As Integer, ByVal viaTower As Integer)
       If disks > 0 Then
           MoveTowerDisks(disks - 1, fromTower, viaTower, toTower)
           System.Console.WriteLine("Move disk {0} from {1} to {2}", disks, fromTower, toTower)
           MoveTowerDisks(disks - 1, viaTower, toTower, fromTower)
       End If
   End Sub

   Sub Main()
       MoveTowerDisks(4, 1, 2, 3)
   End Sub

End Module</lang>

XSLT

<lang xml><xsl:template name="hanoi"> <xsl:param name="n"/> <xsl:param name="from">left</xsl:param> <xsl:param name="to">middle</xsl:param> <xsl:param name="via">right</xsl:param>

 <xsl:if test="$n > 0">
   <xsl:call-template name="hanoi">
     <xsl:with-param name="n"    select="$n - 1"/>
     <xsl:with-param name="from" select="$from"/>
     <xsl:with-param name="to"   select="$via"/>
     <xsl:with-param name="via"  select="$to"/>
   </xsl:call-template>
   <fo:block>
     <xsl:text>Move disk from </xsl:text>
     <xsl:value-of select="$from"/>
     <xsl:text> to </xsl:text>
     <xsl:value-of select="$to"/>
   </fo:block>
   <xsl:call-template name="hanoi">
     <xsl:with-param name="n"    select="$n - 1"/>
     <xsl:with-param name="from" select="$via"/>
     <xsl:with-param name="to"   select="$to"/>
     <xsl:with-param name="via"  select="$from"/>
   </xsl:call-template>
 </xsl:if>

</xsl:template></lang>

<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template>