Towers of Hanoi
From Rosetta Code
Towers of Hanoi 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.
[edit] 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);
}
}
[edit] 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;
[edit] 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)
[edit] 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)
)
[edit] 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
[edit] 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
[edit] 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)
}
}
[edit] AutoIt
Func move($n, $from, $to, $via)
If ($n = 1) Then
ConsoleWrite(StringFormat("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)
EndIf
EndFunc
move(4, 1,2,3)
[edit] AWK
Translation of: Logo
$ 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
[edit] BASIC
Works with: FreeBASIC Works with: RapidQ
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
[edit] 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;
}
[edit] 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);
}
}
[edit] 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);
}
}
[edit] 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 (dec n) from via to)
(println (format "Move from %s to %s" from to))
(recur (dec n) via to from))))
[edit] 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))))
[edit] D
[edit] Recursive
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") ;
}
[edit] Iterative
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") ;
}
[edit] 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 <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()
[edit] 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 {})
[edit] 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).
[edit] 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;!%%%
[edit] 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 ;
[edit] Fortran
Works with: Fortran version 90 and later
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
[edit] 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 0 _ _ _ = []
hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a
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 _ _ _ = 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
[edit] Icon and Unicon
The following is based on a solution in the Unicon book.
[edit] Icon
procedure main(arglist)
hanoi(arglist[1]) | stop("Usage: hanoi n\n\rWhere n is the number of disks to move.")
end
#procedure hanoi(n:integer, needle1:1, needle2:2) # unicon shorthand for icon code 1,2,3 below
procedure hanoi(n, needle1, needle2) #: solve towers of hanoi by moving n disks from needle 1 to needle2 via other
local other
n := integer(0 < n) | runerr(n,101) # 1 ensure integer (this also ensures it's positive too)
/needle1 := 1 # 2 default
/needle2 := 2 # 3 default
if n = 1 then
write("Move disk from ", needle1, " to ", needle2)
else {
other := 6 - needle1 - needle2 # clever but somewhat un-iconish way to find other
hanoi(n-1, needle1, other)
write("Move disk from ", needle1, " to ", needle2)
hanoi(n-1, other, needle2)
}
return
end
[edit] Unicon
This Icon solution works in Unicon.
[edit] 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)
)
)
[edit] 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)
)
[edit] J
Solutions
H =: i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * NB. tacit using anonymous recursion
H1=: monad define NB. explicit equivalent of H
if. y do.
({&0 2 1 , 0 2 , {&1 0 2) H1 y-1
else.
i.0 2
end.
)
Example use
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 .
Alternative solution
If a textual display is desired, similar to some of the other solutions here:
hanoi=: monad define
moves=. i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * y
disks=. $~` ((],[,]) $:@<:) @.* y
('move disk ';' from peg ';' to peg ');@,."1 ":&.>disks,.1+moves
)
For example:
hanoi 3
move disk 1 from peg 1 to peg 3
move disk 2 from peg 1 to peg 2
move disk 1 from peg 3 to peg 2
move disk 3 from peg 1 to peg 3
move disk 1 from peg 2 to peg 1
move disk 2 from peg 2 to peg 3
move disk 1 from peg 1 to peg 3
[edit] 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);
}
}
[edit] 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")
[edit] 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.
[edit] 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
[edit] 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)
[edit] Mathematica
Hanoi[0, from_, to_, via_] := Null
Hanoi[n_Integer, from_, to_, via_] :=
(Hanoi[n-1, from, via, to];
Print["Move disk from pole ", from, " to ", to, "."];
Hanoi[n-1, via, from, to])
[edit] MATLAB
This is a direct translation from the Python example given in the Wikipedia entry for the Tower of Hanoi puzzle.
function towerOfHanoi(n,A,C,B)
if (n~=0)
towerOfHanoi(n-1,A,B,C);
disp(sprintf('Move plate %d from tower %d to tower %d',[n A C]));
towerOfHanoi(n-1,B,C,A);
end
end
Sample output:
towerOfHanoi(3,1,3,2)
Move plate 1 from tower 1 to tower 3
Move plate 2 from tower 1 to tower 2
Move plate 1 from tower 3 to tower 2
Move plate 3 from tower 1 to tower 3
Move plate 1 from tower 2 to tower 1
Move plate 2 from tower 2 to tower 3
Move plate 1 from tower 1 to tower 3
[edit] Modula-3
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.
[edit] Nimrod
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")
Output:
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
[edit] NewLISP
(define (move n from to via)
(if (> n 0)
(move (- n 1) from via to
(print "move disk from pole " from " to pole " to "\n")
(move (- n 1) via to from))))
(move 4 1 2 3)
[edit] 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:
#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
The Implementation - TowersOfHanoi.m:
#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
Test code: TowersTest.m:
#import <stdio.h>
#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;
}
[edit] 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
[edit] 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);
[edit] 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}
[edit] 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.
[edit] 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);
};
};
[edit] Perl 6
Works with: Rakudo version #22 "Thousand Oaks"
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;
}
[edit] PHP
Translation of: Java
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);
}
}
[edit] 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) ) )
[edit] 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");
[edit] 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;
[edit] Prolog
From Programming in Prolog by W.F. Clocksin & C.S. Mellish
hanoi(N) :- move(N,left,center,right).
move(0,_,_,_) :- !.
move(N,A,B,C) :-
M is N-1,
move(M,A,C,B),
inform(A,B),
move(M,C,B,A).
inform(X,Y) :- write([move,a,disk,from,the,X,pole,to,Y,pole]), nl.
[edit] PureBasic
Algorithm according to http://en.wikipedia.org/wiki/Towers_of_Hanoi
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
Full program
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
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.
[edit] 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)
[edit] R
Translation of: Octave
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)
[edit] 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
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
[edit] 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
[edit] Sather
Translation of: Fortran
class MAIN is
move(ndisks, from, to, via:INT) is
if ndisks = 1 then
#OUT + "Move disk from pole " + from + " to pole " + to + "\n";
else
move(ndisks-1, from, via, to);
move(1, from, to, via);
move(ndisks-1, via, to, from);
end;
end;
main is
move(4, 1, 2, 3);
end;
end;
[edit] 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)
}
}
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
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]
}
}
[edit] 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)
[edit] 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;
[edit] SNOBOL4
* # Note: count is global
define('hanoi(n,src,trg,tmp)') :(hanoi_end)
hanoi hanoi = eq(n,0) 1 :s(return)
hanoi(n - 1, src, tmp, trg)
count = count + 1
output = count ': Move disc from ' src ' to ' trg
hanoi(n - 1, tmp, trg, src) :(return)
hanoi_end
* # Test with 4 discs
hanoi(4,'A','C','B')
end
Output:
1: Move disc from A to B 2: Move disc from A to C 3: Move disc from B to C 4: Move disc from A to B 5: Move disc from C to A 6: Move disc from C to B 7: Move disc from A to B 8: Move disc from A to C 9: Move disc from B to C 10: Move disc from B to A 11: Move disc from C to A 12: Move disc from B to C 13: Move disc from A to B 14: Move disc from A to C 15: Move disc from B to C
[edit] Tcl
The use of interp alias shown is a sort of closure: keep track of the number of moves required
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
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
[edit] 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
[edit] UNIX Shell
Works with: 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
[edit] Ursala
#import nat
move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC
#show+
main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'>
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
[edit] Vedit macro language
This implementation outputs the results in current edit buffer.
#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
[edit] Visual Basic .NET
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
[edit] 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>
[edit] XQuery
declare function local:hanoi($disk as xs:integer, $from as xs:integer,
$to as xs:integer, $via as xs:integer) as element()*
{
if($disk > 0)
then (
local:hanoi($disk - 1, $from, $via, $to),
<move disk='{$disk}'><from>{$from}</from><to>{$to}</to></move>,
local:hanoi($disk - 1, $via, $to, $from)
)
else ()
};
<hanoi>
{
local:hanoi(4, 1, 2, 3)
}
</hanoi>
Result is:
<?xml version="1.0" encoding="UTF-8"?>
<hanoi>
<move disk="1">
<from>1</from>
<to>3</to>
</move>
<move disk="2">
<from>1</from>
<to>2</to>
</move>
<move disk="1">
<from>3</from>
<to>2</to>
</move>
<move disk="3">
<from>1</from>
<to>3</to>
</move>
<move disk="1">
<from>2</from>
<to>1</to>
</move>
<move disk="2">
<from>2</from>
<to>3</to>
</move>
<move disk="1">
<from>1</from>
<to>3</to>
</move>
<move disk="4">
<from>1</from>
<to>2</to>
</move>
<move disk="1">
<from>3</from>
<to>2</to>
</move>
<move disk="2">
<from>3</from>
<to>1</to>
</move>
<move disk="1">
<from>2</from>
<to>1</to>
</move>
<move disk="3">
<from>3</from>
<to>2</to>
</move>
<move disk="1">
<from>1</from>
<to>3</to>
</move>
<move disk="2">
<from>1</from>
<to>2</to>
</move>
<move disk="1">
<from>3</from>
<to>2</to>
</move>
</hanoi>
Categories: Programming Tasks | Puzzles | Recursion | Games | Classic CS problems and programs | ActionScript | Ada | Agena | ALGOL 68 | AmigaE | AppleScript | AutoHotkey | AutoIt | AWK | BASIC | C | C sharp | C++ | Clojure | Common Lisp | D | Dc | E | Erlang | FALSE | Forth | Fortran | Haskell | Icon | Unicon | Io | Ioke | J | Java | JavaScript | Joy | Logo | Lua | Mathematica | MATLAB | Modula-3 | Nimrod | NewLISP | Objective-C | OCaml | Octave | Oz | Pascal | Perl | Perl 6 | PHP | PicoLisp | Pop11 | PL/I | Prolog | PureBasic | Python | R | REBOL | Ruby | Sather | Scala | Scheme | Seed7 | SNOBOL4 | Tcl | Toka | UNIX Shell | Ursala | Vedit macro language | Visual Basic .NET | XSLT | XQuery
