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>

ALGOL 68

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

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>

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

(defn towers-of-hanoi [n from to via]
       (if (= n 1)
         (println (format "Move from %s to %s" from to))
         (do
           (towers-of-hanoi (- n 1) from via to)
           (println (format "Move from %s to %s" from to))
           (recur (- n 1) via to from))))

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 d>
    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

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

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;!%%%

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 ;

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

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

J

H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. *
H1=: 3 : 'if. *y do. ({&0 2 1 , 0 2 , {&1 0 2) H1 y-1 else. i.0 2 end.'

H employs anonymous recursion; H1 is an "explicit" statement of the same computation. For example:

   H 3
0 2
0 1
2 1
0 2
1 2
1 0
2 0

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

DEFINE hanoi == 
               [[rolldown] infra] dip 
               [ [ [null] [pop pop] ] 
                 [ [dup2 [[rotate] infra] dip pred] 
                   [ [dup rest put] dip 
                     [[swap] infra] dip pred ] 
                   [] ] ] 
               condnestrec.

Using it (5 is the number of disks.)

[source destination temp] 5  hanoi.

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

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])

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>

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>

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 move {

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

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

PHP

Translation of: Java

<lang php><?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>

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");

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 )
   print(sprintf("move disk from %d to %d", from, to))
 else {
   hanoimove(ndisks-1, from, via, to)
   hanoimove(1, from, to, via)
   hanoimove(ndisks-1, via, to, from)
 }

}

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

Ruby

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

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;

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

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

UNIX Shell

Works with: bash

<lang bash>

1. !/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>

Vedit macro language

This implementation outputs the results in current edit buffer. <lang vedit>

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

XSLT

<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 &gt; 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>

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