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.
Ada
<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;
</ada>
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
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++
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
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") ;
}
The following is iterative approach.
ref : The shortest and "mysterious" TH algorithm
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") ;
}
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
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
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])
OCaml
<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</ocaml>
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
<?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
<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)</scheme>
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
<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 </bash>
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 > 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>