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

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

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#

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

C++

Works with: g++

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

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

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

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

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

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:

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 = mapM_ f $ hanoi n 1 2 3 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

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

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

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

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>

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.

  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.

A little longer, but clearer for my taste

  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.

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

PHP

Translation of: Java

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

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

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

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;

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>

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>