Towers of Hanoi: Difference between revisions
Nimrod -> Nim |
|||
Line 1,882:
hanoimove(4, 1, 2, 3);</lang>
=={{header|Oforth}}==
<lang Oforth>func: move(n, from, to, via)
{
n 0 > ifTrue: [
move(n 1 -, from, via, to)
System.Out "Move disk from " << from << " to " << to << cr
move(n 1 -, via, to, from)
]
}
move(7, 1, 2, 3)</lang>
=={{header|Oz}}==
|
Revision as of 21:44, 18 January 2015
You are encouraged to solve this task according to the task description, using any language you may know.
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) }
} move(64, 1, 3, 2)</lang>
AutoIt
<lang 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)</lang>
AWK
<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")}'</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
BASIC
Using a Subroutine
<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>
Using GOSUB
s
Here's an example of implementing recursion in an old BASIC that only has global variables:
<lang gwbasic>10 DIM N(1024), F(1024), T(1024), V(1024): REM STACK PER PARAMETER 20 SP = 0: REM STACK POINTER 30 N(SP) = 4: REM START WITH 4 DISCS 40 F(SP) = 1: REM ON PEG 1 50 T(SP) = 2: REM MOVE TO PEG 2 60 V(SP) = 3: REM VIA PEG 3 70 GOSUB 100 80 END 90 REM MOVE SUBROUTINE 100 IF N(SP) = 0 THEN RETURN 110 OS = SP: REMEMBER STACK POINTER 120 SP = SP + 1: REM INCREMENT STACK POINTER 130 N(SP) = N(OS) - 1: REM MOVE N-1 DISCS 140 F(SP) = F(OS) : REM FROM START PEG 150 T(SP) = V(OS) : REM TO VIA PEG 160 V(SP) = T(OS) : REM VIA TO PEG 170 GOSUB 100 180 OS = SP - 1: REM OS WILL HAVE CHANGED 190 PRINT "MOVE DISC FROM"; F(OS); "TO"; T(OS) 200 N(SP) = N(OS) - 1: REM MOVE N-1 DISCS 210 F(SP) = V(OS) : REM FROM VIA PEG 220 T(SP) = T(OS) : REM TO DEST PEG 230 V(SP) = F(OS) : REM VIA FROM PEG 240 GOSUB 100 250 SP = SP - 1 : REM RESTORE STACK POINTER FOR CALLER 260 RETURN</lang>
BASIC256
<lang BASIC256>call move(4,1,2,3) print "Towers of Hanoi puzzle completed!" end
subroutine move (n, fromPeg, toPeg, viaPeg)
if n>0 then call move(n-1, fromPeg, viaPeg, toPeg) print "Move disk from "+fromPeg+" to "+toPeg call move(n-1, viaPeg, toPeg, fromPeg) end if
end subroutine</lang>
- Output:
Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2 Move disk from 1 to 3 Move disk from 2 to 1 Move disk from 2 to 3 Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2 Move disk from 3 to 1 Move disk from 2 to 1 Move disk from 3 to 2 Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2 Towers of Hanoi puzzle completed!
BBC BASIC
<lang bbcbasic> DIM Disc$(13),Size%(3)
FOR disc% = 1 TO 13 Disc$(disc%) = STRING$(disc%," ")+STR$disc%+STRING$(disc%," ") IF disc%>=10 Disc$(disc%) = MID$(Disc$(disc%),2) Disc$(disc%) = CHR$17+CHR$(128+disc%-(disc%>7))+Disc$(disc%)+CHR$17+CHR$128 NEXT disc% MODE 3 OFF ndiscs% = 13 FOR n% = ndiscs% TO 1 STEP -1 PROCput(n%,1) NEXT INPUT TAB(0,0) "Press Enter to start" dummy$ PRINT TAB(0,0) SPC(20); PROChanoi(ndiscs%,1,2,3) VDU 30 END DEF PROChanoi(a%,b%,c%,d%) IF a%=0 ENDPROC PROChanoi(a%-1,b%,d%,c%) PROCtake(a%,b%) PROCput(a%,c%) PROChanoi(a%-1,d%,c%,b%) ENDPROC DEF PROCput(disc%,peg%) PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))Disc$(disc%); Size%(peg%) = Size%(peg%)+1 ENDPROC DEF PROCtake(disc%,peg%) Size%(peg%) = Size%(peg%)-1 PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))STRING$(2*disc%+1," "); ENDPROC</lang>
Bracmat
<lang bracmat>( ( move
= n from to via . !arg:(?n,?from,?to,?via) & ( !n:>0 & move$(!n+-1,!from,!via,!to) & out$("Move disk from pole " !from " to pole " !to) & move$(!n+-1,!via,!to,!from) | ) )
& move$(4,1,2,3) );</lang>
- Output:
Move disk from pole 1 to pole 3 Move disk from pole 1 to pole 2 Move disk from pole 3 to pole 2 Move disk from pole 1 to pole 3 Move disk from pole 2 to pole 1 Move disk from pole 2 to pole 3 Move disk from pole 1 to pole 3 Move disk from pole 1 to pole 2 Move disk from pole 3 to pole 2 Move disk from pole 3 to pole 1 Move disk from pole 2 to pole 1 Move disk from pole 3 to pole 2 Move disk from pole 1 to pole 3 Move disk from pole 1 to pole 2 Move disk from pole 3 to pole 2
Brainfuck
<lang brainfuck>[ This implementation is recursive and uses a stack, consisting of frames that are 8 bytes long. The layout is as follows:
Byte Description
0 recursion flag (the program stops if the flag is zero) 1 the step which is currently executed 4 means a call to move(a, c, b, n - 1) 3 means a call to move(a, b, c, 1) 2 means a call to move(b, a, c, n - 1) 1 prints the source and dest pile 2 flag to check whether the current step has already been done or if it still must be executed 3 the step which will be executed in the next loop 4 the source pile 5 the helper pile 6 the destination pile 7 the number of disks to move
The first stack frame (0 0 0 0 0 0 0 0) is used to abort the recursion. ]
>>>>>>>>
These are the parameters for the program (1 4 1 0 'a 'b 'c 5) +>++++>+>> >>>>++++++++[<++++++++++++>-]< [<<<+>+>+>-]<<<+>++>+++>+++++> <<<<<<<<
[> while (recurse)
[- if (step gt 0) >[-]+< todo = 1 [- if (step gt 1) [- if (step gt 2) [- if (step gt 3) >>+++<< next = 3 >-< todo = 0 >>>>>>[>+>+<<-]>[<+>-]> n dup - [[-] if (sub(n 1) gt 0) <+>>>++++> push (1 0 0 4)
copy and push a <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< >
copy and push c <<<<<<<[>>>>>>>+>+ <<<<<<<<-]>>>>>>> >[<<<<<<<<+>>>>>>>>-]< >
copy and push b <<<<<<<<<[>>>>>>>>>+>+ <<<<<<<<<<-]>>>>>>>>> >[<<<<<<<<<<+>>>>>>>>>>-]< >
copy n and push sub(n 1) <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< - >> ] <<<<<<<< ] >[-< if ((step gt 2) and todo) >>++<< next = 2 >>>>>>> +>>>+> push 1 0 0 1 a b c 1 <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< > a <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< > b <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< > c + >> >]< ] >[-< if ((step gt 1) and todo) >>>>>>[>+>+<<-]>[<+>-]> n dup - [[-] if (n sub 1 gt 0) <+>>>++++> push (1 0 0 4)
copy and push b <<<<<<<[>>>>>>>+ <<<<<<<-]>>>>>>> >[<<<<<<<<+>>>>>>>>-]< >
copy and push a <<<<<<<<<[>>>>>>>>>+ <<<<<<<<<-]>>>>>>>>> >[<<<<<<<<<<+>>>>>>>>>>-]< >
copy and push c <<<<<<<<[>>>>>>>>+ <<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< >
copy n and push sub(n 1) <<<<<<<<[>>>>>>>>+>+ <<<<<<<<<-]>>>>>>>> >[<<<<<<<<<+>>>>>>>>>-]< - >> ] <<<<<<<< >]< ] >[-< if ((step gt 0) and todo) >>>>>>> >++++[<++++++++>-]< >>++++++++[<+++++++++>-]<++++ >>++++++++[<++++++++++++>-]<+++++ >>+++++++++[<++++++++++++>-]<+++ <<< >.+++++++>.++.--.<<. >>-.+++++.----.<<. >>>.<---.+++.>+++.+.+.<.<<. >.>--.+++++.---.++++. -------.+++.<<. >>>++.-------.-.<<<. >+.>>+++++++.---.-----.<<<. <<<<.>>>>. >>----.>++++++++.<+++++.<<. >.>>.---.-----.<<<. <<.>>++++++++++++++. >>>[-]<[-]<[-]<[-] +++++++++++++.---.[-] <<<<<<< >]< >>[<<+>>-]<< step = next ] return with clear stack frame <[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<< <<<<<<<< >>[<<+>>-]<< step = next <
]</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>
Animate it for fun:<lang c>#include <stdio.h>
- include <stdlib.h>
- include <unistd.h>
typedef struct { int *x, n; } tower; tower *new_tower(int cap) { tower *t = calloc(1, sizeof(tower) + sizeof(int) * cap); t->x = (int*)(t + 1); return t; }
tower *t[3]; int height;
void text(int y, int i, int d, const char *s) { printf("\033[%d;%dH", height - y + 1, (height + 1) * (2 * i + 1) - d); while (d--) printf("%s", s); }
void add_disk(int i, int d) { t[i]->x[t[i]->n++] = d; text(t[i]->n, i, d, "==");
usleep(100000); fflush(stdout); }
int remove_disk(int i) { int d = t[i]->x[--t[i]->n]; text(t[i]->n + 1, i, d, " "); return d; }
void move(int n, int from, int to, int via) { if (!n) return;
move(n - 1, from, via, to); add_disk(to, remove_disk(from)); move(n - 1, via, to, from); }
int main(int c, char *v[]) { puts("\033[H\033[J");
if (c <= 1 || (height = atoi(v[1])) <= 0) height = 8; for (c = 0; c < 3; c++) t[c] = new_tower(height); for (c = height; c; c--) add_disk(0, c);
move(height, 0, 2, 1);
text(1, 0, 1, "\n"); 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++
<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>
COBOL
<lang cobol> >>SOURCE FREE IDENTIFICATION DIVISION. PROGRAM-ID. towers-of-hanoi.
PROCEDURE DIVISION.
CALL "move-disk" USING 4, 1, 2, 3 .
END PROGRAM towers-of-hanoi.
IDENTIFICATION DIVISION. PROGRAM-ID. move-disk RECURSIVE.
DATA DIVISION. LINKAGE SECTION. 01 n PIC 9 USAGE COMP. 01 from-pole PIC 9 USAGE COMP. 01 to-pole PIC 9 USAGE COMP. 01 via-pole PIC 9 USAGE COMP.
PROCEDURE DIVISION USING n, from-pole, to-pole, via-pole.
IF n > 0 SUBTRACT 1 FROM n CALL "move-disk" USING CONTENT n, from-pole, via-pole, to-pole DISPLAY "Move disk from pole " from-pole " to pole " to-pole CALL "move-disk" USING CONTENT n, via-pole, to-pole, from-pole END-IF .
END PROGRAM move-disk.</lang>
CoffeeScript
<lang coffeescript>hanoi = (ndisks, start_peg=1, end_peg=3) ->
if ndisks staging_peg = 1 + 2 + 3 - start_peg - end_peg hanoi(ndisks-1, start_peg, staging_peg) console.log "Move disk #{ndisks} from peg #{start_peg} to #{end_peg}" hanoi(ndisks-1, staging_peg, end_peg)
hanoi(4)</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 Version
<lang d>import std.stdio;
void hanoi(in int n, in char from, in char to, in char via) {
if (n > 0) { hanoi(n - 1, from, via, to); writefln("Move disk %d from %s to %s", n, from, to); hanoi(n - 1, via, to, from); }
}
void main() {
hanoi(3, 'L', 'M', 'R');
}</lang>
- Output:
Move disk 1 from L to M Move disk 2 from L to R Move disk 1 from M to R Move disk 3 from L to M Move disk 1 from R to L Move disk 2 from R to M Move disk 1 from L to M
Fast Iterative Version
See: The shortest and "mysterious" TH algorithm <lang d>// Code found and then improved by Glenn C. Rhoads, // then some more by M. Kolar (2000). void main(in string[] args) {
import core.stdc.stdio, std.conv, std.typetuple;
immutable size_t n = (args.length > 1) ? args[1].to!size_t : 3; size_t[3] p = [(1 << n) - 1, 0, 0];
// Show the start configuration of the pegs. '|'.putchar; foreach_reverse (immutable i; 1 .. n + 1) printf(" %d", i); "\n|\n|".puts;
foreach (immutable size_t x; 1 .. (1 << n)) { { immutable size_t i1 = x & (x - 1); immutable size_t fr = (i1 + i1 / 3) & 3; immutable size_t i2 = (x | (x - 1)) + 1; immutable size_t to = (i2 + i2 / 3) & 3;
size_t j = 1; for (size_t w = x; !(w & 1); w >>= 1, j <<= 1) {}
// Now j is not the number of the disk to move, // it contains the single bit to be moved: p[fr] &= ~j; p[to] |= j; }
// Show the current configuration of pegs. foreach (immutable size_t k; TypeTuple!(0, 1, 2)) { "\n|".printf; size_t j = 1 << n; foreach_reverse (immutable size_t w; 1 .. n + 1) { j >>= 1; if (j & p[k]) printf(" %zd", w); } } '\n'.putchar; }
}</lang>
- Output:
| 3 2 1 | | | 3 2 | | 1 | 3 | 2 | 1 | 3 | 2 1 | | | 2 1 | 3 | 1 | 2 | 3 | 1 | | 3 2 | | | 3 2 1
Dart
<lang dart>main() {
moveit(from,to) { print("move ${from} ---> ${to}"); }
hanoi(height,toPole,fromPole,usePole) { if (height>0) { hanoi(height-1,usePole,fromPole,toPole); moveit(fromPole,toPole); hanoi(height-1,toPole,usePole,fromPole); } }
hanoi(3,3,1,2);
}</lang>
The same as above, with optional static type annotations and styled according to http://www.dartlang.org/articles/style-guide/ <lang dart>main() {
String say(String from, String to) => "$from ---> $to";
hanoi(int height, int toPole, int fromPole, int usePole) { if (height > 0) { hanoi(height - 1, usePole, fromPole, toPole); print(say(fromPole.toString(), toPole.toString())); hanoi(height - 1, toPole, usePole, fromPole); } }
hanoi(3, 3, 1, 2);
}</lang>
- Output:
move 1 ---> 3 move 1 ---> 2 move 3 ---> 2 move 1 ---> 3 move 2 ---> 1 move 2 ---> 3 move 1 ---> 3
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()
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>
Eiffel
<lang Eiffel>class APPLICATION
create make
feature {NONE} -- Initialization
make do move (4, "A", "B", "C") end
feature -- Towers of Hanoi
move (n: INTEGER; frm, to, via: STRING) require n > 0 do if n = 1 then
print ("Move disk from pole " + frm + " to pole " + to + "%N") else move (n - 1, frm, via, to) move (1, frm, to, via) move (n - 1, via, to, frm)
end end end</lang>
Emacs Lisp
<lang lisp> (defun move (n from to via)
(cond ((= n 1) (print (format "Move from %S to %S" from to))) (t
(progn (move (- n 1) from via to) (print (format "Move from %S to %S" from to)) (move (- n 1) via to from))))) </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>
ERRE
<lang erre> !----------------------------------------------------------- ! HANOI.R : solve tower of Hanoi puzzle using a recursive ! modified algorithm. !-----------------------------------------------------------
PROGRAM HANOI
!$INTEGER
!VAR I,J,MOSSE,NUMBER
PROCEDURE PRINTMOVE
LOCAL SOURCE$,DEST$ MOSSE=MOSSE+1 CASE I OF 1-> SOURCE$="Left" END -> 2-> SOURCE$="Center" END -> 3-> SOURCE$="Right" END -> END CASE CASE J OF 1-> DEST$="Left" END -> 2-> DEST$="Center" END -> 3-> DEST$="Right" END -> END CASE PRINT("I move a disk from ";SOURCE$;" to ";DEST$)
END PROCEDURE
PROCEDURE MOVE
IF NUMBER<>0 THEN NUMBER=NUMBER-1 J=6-I-J MOVE J=6-I-J PRINTMOVE I=6-I-J MOVE I=6-I-J NUMBER=NUMBER+1 END IF
END PROCEDURE
BEGIN
MAXNUM=12 MOSSE=0 PRINT(CHR$(12);TAB(25);"--- TOWERS OF HANOI ---") REPEAT PRINT("Number of disks ";) INPUT(NUMBER) UNTIL NUMBER>1 AND NUMBER<=MAXNUM PRINT PRINT("For ";NUMBER;"disks the total number of moves is";2^NUMBER-1) I=1 ! number of source pole J=3 ! number of destination pole MOVE
END PROGRAM </lang>
- Output:
--- TOWER OF HANOI --- Number of disks ? 3 For 3 disks the total number of moves is 7 I move a disk from Left to Right I move a disk from Left to Center I move a disk from Right to Center I move a disk from Left to Right I move a disk from Center to Left I move a disk from Center to Right I move a disk from Left to Right
Ezhil
<lang Python>
- (C) 2013 Ezhil Language Project
- Tower of Hanoi – recursive solution
நிரல்பாகம் ஹோனாய்(வட்டுகள், முதல்அச்சு, இறுதிஅச்சு,வட்டு)
@(வட்டுகள் == 1 ) ஆனால் பதிப்பி “வட்டு ” + str(வட்டு) + “ஐ \t (” + str(முதல்அச்சு) + “ —> ” + str(இறுதிஅச்சு)+ “) அச்சிற்கு நகர்த்துக.” இல்லை
@( ["இ", "அ", "ஆ"] இல் அச்சு ) ஒவ்வொன்றாக @( (முதல்அச்சு != அச்சு) && (இறுதிஅச்சு != அச்சு) ) ஆனால் நடு = அச்சு முடி முடி
# solve problem for n-1 again between src and temp pegs ஹோனாய்(வட்டுகள்-1, முதல்அச்சு,நடு,வட்டுகள்-1)
# move largest disk from src to destination ஹோனாய்(1, முதல்அச்சு, இறுதிஅச்சு,வட்டுகள்)
# solve problem for n-1 again between different pegs ஹோனாய்(வட்டுகள்-1, நடு, இறுதிஅச்சு,வட்டுகள்-1) முடி
முடி
ஹோனாய்(4,”அ”,”ஆ”,0) </lang>
F#
<lang fsharp>#light let rec hanoi num start finish =
match num with | 0 -> [ ] | _ -> let temp = (6 - start - finish) (hanoi (num-1) start temp) @ [ start, finish ] @ (hanoi (num-1) temp finish)
[<EntryPoint>] let main args =
(hanoi 4 1 2) |> List.iter (fun pair -> match pair with | a, b -> printf "Move disc from %A to %A\n" a b) 0</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>
Factor
<lang factor>USING: formatting kernel locals math ; IN: rosettacode.hanoi
- move ( from to -- )
"%d->%d\n" printf ;
- hanoi ( n from to other -- )
n 0 > [ n 1 - from other to hanoi from to move n 1 - other to from hanoi ] when ;</lang>
In the REPL:
( scratchpad ) 3 1 3 2 hanoi 1->3 1->2 3->2 1->3 2->1 2->3 1->3
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
<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>
GAP
<lang gap>Hanoi := function(n) local move; move := function(n, a, b, c) # from, through, to if n = 1 then Print(a, " -> ", c, "\n"); else move(n - 1, a, c, b); move(1, a, b, c); move(n - 1, b, a, c); fi; end; move(n, "A", "B", "C"); end;
Hanoi(1);
- A -> C
Hanoi(2);
- A -> B
- A -> C
- B -> C
Hanoi(3);
- A -> C
- A -> B
- C -> B
- A -> C
- B -> A
- B -> C
- A -> C</lang>
Go
<lang go>package main
import "fmt"
// a towers of hanoi solver just has one method, play type solver interface {
play(int)
}
func main() {
var t solver // declare variable of solver type t = new(towers) // type towers must satisfy solver interface t.play(4)
}
// towers is example of type satisfying solver interface type towers struct {
// an empty struct. some other solver might fill this with some // data representation, maybe for algorithm validation, or maybe for // visualization.
}
// play is sole method required to implement solver type func (t *towers) play(n int) {
// drive recursive solution, per task description t.moveN(n, 1, 2, 3)
}
// recursive algorithm func (t *towers) moveN(n, from, to, via int) {
if n > 0 { t.moveN(n-1, from, via, to) t.move1(from, to) t.moveN(n-1, via, to, from) }
}
// example function prints actions to screen. // enhance with validation or visualization as needed. func (t *towers) move1(from, to int) {
fmt.Println("move disk from rod", from, "to rod", to)
}</lang>
In other words:
<lang go>package main
import "fmt"
func main() { move(3, "A", "B", "C") }
func move(n uint64, a, b, c string) { if n > 0 { move(n-1, a, c, b) fmt.Println("Move disk from " + a + " to " + c) move(n-1, b, a, c) } }</lang>
Groovy
Unlike most solutions here this solution manipulates more-or-less actual stacks of more-or-less actual rings. <lang groovy>def tail = { list, n -> def m = list.size(); list[([m - n, 0].max())..<m] }
final STACK = [A:[],B:[],C:[]].asImmutable()
def report = { it -> } def check = { it -> }
def moveRing = { from, to -> to << from.pop(); report(); check(to) }
def moveStack moveStack = { from, to, using = STACK.values().find { !(it.is(from) || it.is(to)) } ->
if (!from) return def n = from.size() moveStack(tail(from, n-1), using, to) moveRing(from, to) moveStack(tail(using, n-1), to, from)
}</lang> Test program: <lang groovy>enum Ring {
S('°'), M('o'), L('O'), XL('( )'); private sym private Ring(sym) { this.sym=sym } String toString() { sym }
}
report = { STACK.each { k, v -> println "${k}: ${v}" }; println() } check = { to -> assert to == ([] + to).sort().reverse() }
Ring.values().reverseEach { STACK.A << it } report() check(STACK.A) moveStack(STACK.A, STACK.C)</lang>
- Output:
A: [( ), O, o, °] B: [] C: [] A: [( ), O, o] B: [°] C: [] A: [( ), O] B: [°] C: [o] A: [( ), O] B: [] C: [o, °] A: [( )] B: [O] C: [o, °] A: [( ), °] B: [O] C: [o] A: [( ), °] B: [O, o] C: [] A: [( )] B: [O, o, °] C: [] A: [] B: [O, o, °] C: [( )] A: [] B: [O, o] C: [( ), °] A: [o] B: [O] C: [( ), °] A: [o, °] B: [O] C: [( )] A: [o, °] B: [] C: [( ), O] A: [o] B: [°] C: [( ), O] A: [] B: [°] C: [( ), O, o] A: [] B: [] C: [( ), O, o, °]
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>
Icon and Unicon
The following is based on a solution in the Unicon book. <lang 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</lang>
Inform 7
<lang inform7>Hanoi is a room.
A disk is a kind of supporter.
A post is a kind of supporter. A post is always fixed in place.
The left post, the middle post, and the right post are posts in Hanoi.
A disk is a kind of supporter. The red disk is a disk on the left post. The orange disk is a disk on the red disk. The yellow disk is a disk on the orange disk. The green disk is a disk on the yellow disk.
Definition: a disk is topmost if nothing is on it.
When play begins: move 4 disks from the left post to the right post via the middle post.
To move (N - number) disk/disks from (FP - post) to (TP - post) via (VP - post): if N > 0: move N - 1 disks from FP to VP via TP; say "Moving a disk from [FP] to [TP]..."; let D be a random topmost disk enclosed by FP; if a topmost disk (called TD) is enclosed by TP, now D is on TD; otherwise now D is on TP; move N - 1 disks from VP to TP via FP.</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
Solutions <lang j>H =: i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * NB. tacit using anonymous recursion</lang>
- Example use:
<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 . Or, using explicit rather than implicit code: <lang j>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.
)</lang> The usage here is the same:
H1 2 0 1 0 2 1 2
- Alternative solution
If a textual display is desired, similar to some of the other solutions here (counting from 1 instead of 0, tracking which disk is on the top of the stack, and of course formatting the result for a human reader instead of providing a numeric result): <lang J>hanoi=: monad define
moves=. H y disks=. $~` ((],[,]) $:@<:) @.* y ('move disk ';' from peg ';' to peg ');@,."1 ":&.>disks,.1+moves
)</lang>
- Demonstration:
<lang J> 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</lang>
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, a, b, c) { if (n > 0) { move(n-1, a, c, b); console.log("Move disk from " + a + " to " + c); move(n-1, b, a, c); } } move(4, "A", "B", "C");</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>
jq
The algorithm used here is used elsewhere on this page but it is worthwhile pointing out that it can also be read as a proof that:
(a) move(n;"A";"B";"C") will logically succeed for n>=0; and
(b) move(n;"A";"B";"C") will generate the sequence of moves, assuming sufficient computing resources.
The proof of (a) is by induction:
- As explained in the comments, the algorithm establishes that move(n;x;y;z) is possible for all n>=0 and distinct x,y,z if move(n-1;x;y;z)) is possible;
- Since move(0;x;y;z) evidently succeeds, (a) is established by induction.
The truth of (b) follows from the fact that the algorithm emits an instruction of what to do when moving a single disk.
<lang jq># n is the number of disks to move from From to To
def move(n; From; To; Via):
if n > 0 then # move all but the largest at From to Via (according to the rules): move(n-1; From; Via; To), # ... so the largest disk at From is now free to move to its final destination: "Move disk from \(From) to \(To)", # Move the remaining disks at Via to To: move(n-1; Via; To; From) else empty end;</lang>
Example:
move(5; "A"; "B"; "C")
K
<lang K> h:{[n;a;b;c]if[n>0;_f[n-1;a;c;b];`0:,//$($n,":",$a,"->",$b,"\n");_f[n-1;c;b;a]]}
h[4;1;2;3]
1:1->3 2:1->2 1:3->2 3:1->3 1:2->1 2:2->3 1:1->3 4:1->2 1:3->2 2:3->1 1:2->1 3:3->2 1:1->3 2:1->2 1:3->2</lang> The disk to move in the i'th step is the same as the position of the leftmost 1 in the binary representation of 1..2^n. <lang K> s:();{[n;a;b;c]if[n>0;_f[n-1;a;c;b];s,:n;_f[n-1;c;b;a]]}[4;1;2;3];s 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1_{*1+&|x}'a:(2_vs!_2^4)
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1</lang>
Lasso
<lang Lasso>#!/usr/bin/lasso9
define towermove( disks::integer, a,b,c ) => { if(#disks > 0) => { towermove(#disks - 1, #a, #c, #b ) stdoutnl("Move disk from " + #a + " to " + #c) towermove(#disks - 1, #b, #a, #c ) } }
towermove((integer($argv -> second || 3)), "A", "B", "C")</lang> Called from command line: <lang Lasso>./towers</lang>
- Output:
Move disk from A to C Move disk from A to B Move disk from C to B Move disk from A to C Move disk from B to A Move disk from B to C Move disk from A to C
Called from command line: <lang Lasso>./towers 4</lang>
- Output:
Move disk from A to B Move disk from A to C Move disk from B to C Move disk from A to B Move disk from C to A Move disk from C to B Move disk from A to B Move disk from A to C Move disk from B to C Move disk from B to A Move disk from C to A Move disk from B to C Move disk from A to B Move disk from A to C Move disk from B to C
Liberty BASIC
This looks much better with a GUI interface. <lang lb> source$ ="A"
via$ ="B" target$ ="C"
call hanoi 4, source$, target$, via$ ' ie call procedure to move legally 4 disks from peg A to peg C via peg B
wait
sub hanoi numDisks, source$, target$, via$ if numDisks =0 then exit sub else call hanoi numDisks -1, source$, via$, target$ print " Move disk "; numDisks; " from peg "; source$; " to peg "; target$ call hanoi numDisks -1, via$, target$, source$ end if end sub
end</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>
Logtalk
<lang logtalk>:- object(hanoi).
:- public(run/1). :- mode(run(+integer), one). :- info(run/1, [ comment is 'Solves the towers of Hanoi problem for the specified number of disks.', argnames is ['Disks']]).
run(Disks) :- move(Disks, left, middle, right).
move(1, Left, _, Right):- !, report(Left, Right). move(Disks, Left, Aux, Right):- Disks2 is Disks - 1, move(Disks2, Left, Right, Aux), report(Left, Right), move(Disks2, Aux, Left, Right).
report(Pole1, Pole2):- write('Move a disk from '), writeq(Pole1), write(' to '), writeq(Pole2), write('.'), nl.
- - end_object.</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 disk from pole ", from, " to ", to, "."]; Hanoi[n-1, via, from, to])</lang>
MATLAB
This is a direct translation from the Python example given in the Wikipedia entry for the Tower of Hanoi puzzle. <lang MATLAB>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</lang>
- 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
МК-61/52
<lang>^ 2 x^y П0 <-> 2 / {x} x#0 16 3 П3 2 П2 БП 20 3 П2 2 П3 1 П1 ПП 25 КППB ПП 28 КППA ПП 31 КППB ПП 34 КППA ИП1 ИП3 КППC ИП1 ИП2 КППC ИП3 ИП2 КППC ИП1 ИП3 КППC ИП2 ИП1 КППC ИП2 ИП3 КППC ИП1 ИП3 КППC В/О ИП1 ИП2 БП 62 ИП2 ИП1 КППC ИП1 ИП2 ИП3 П1 -> П3 -> П2 В/О 1 0 / + С/П КИП0 ИП0 x=0 89 3 3 1 ИНВ ^ ВП 2 С/П В/О</lang>
Instruction: РA = 56; РB = 60; РC = 72; N В/О С/П, where 2 <= N <= 7.
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>
Monte
<lang monte>def move(n, fromPeg, toPeg, viaPeg):
if (n > 0): move(n.previous(), fromPeg, viaPeg, toPeg) traceln(`Move disk $n from $fromPeg to $toPeg`) move(n.previous(), viaPeg, toPeg, fromPeg)
move(3, "left", "right", "middle")</lang>
Nemerle
<lang Nemerle>using System; using System.Console;
module Towers {
Hanoi(n : int, from = 1, to = 3, via = 2) : void { when (n > 0) { Hanoi(n - 1, from, via, to); WriteLine("Move disk from peg {0} to peg {1}", from, to); Hanoi(n - 1, via, to, from); } } Main() : void { Hanoi(4) }
}</lang>
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols binary
runSample(arg) return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) private static
parse arg discs . if discs = , discs < 1 then discs = 4 say 'Minimum moves to solution:' 2 ** discs - 1 moves = move(discs) say 'Solved in' moves 'moves.' return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method move(discs = int 4, towerFrom = int 1, towerTo = int 2, towerVia = int 3, moves = int 0) public static
if discs == 1 then do moves = moves + 1 say 'Move disc from peg' towerFrom 'to peg' towerTo '- Move No:' Rexx(moves).right(5) end else do moves = move(discs - 1, towerFrom, towerVia, towerTo, moves) moves = move(1, towerFrom, towerTo, towerVia, moves) moves = move(discs - 1, towerVia, towerTo, towerFrom, moves) end return moves
</lang>
- Output:
Minimum moves to solution: 15 Move disc from peg 1 to peg 3 - Move No: 1 Move disc from peg 1 to peg 2 - Move No: 2 Move disc from peg 3 to peg 2 - Move No: 3 Move disc from peg 1 to peg 3 - Move No: 4 Move disc from peg 2 to peg 1 - Move No: 5 Move disc from peg 2 to peg 3 - Move No: 6 Move disc from peg 1 to peg 3 - Move No: 7 Move disc from peg 1 to peg 2 - Move No: 8 Move disc from peg 3 to peg 2 - Move No: 9 Move disc from peg 3 to peg 1 - Move No: 10 Move disc from peg 2 to peg 1 - Move No: 11 Move disc from peg 3 to peg 2 - Move No: 12 Move disc from peg 1 to peg 3 - Move No: 13 Move disc from peg 1 to peg 2 - Move No: 14 Move disc from peg 3 to peg 2 - Move No: 15 Solved in 15 moves.
NewLISP
<lang lisp>(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)</lang>
Nim
<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:
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
Objective-C
From here
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>
- import "TowersOfHanoi.h"
int main( int argc, const char *argv[] ) { @autoreleasepool {
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];
} 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>
Oforth
<lang Oforth>func: move(n, from, to, via) {
n 0 > ifTrue: [ move(n 1 -, from, via, to) System.Out "Move disk from " << from << " to " << to << cr move(n 1 -, via, to, from) ]
}
move(7, 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
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
<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>
PHL
<lang phl>module hanoi;
extern printf;
@Void move(@Integer n, @Integer from, @Integer to, @Integer 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); } ]
@Integer main [ move(4, 1,2,3); return 0; ]</lang>
PHP
<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 pli>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>
Plain TeX
<lang TeX>\newcount\hanoidepth \def\hanoi#1{%
\hanoidepth = #1 \move abc
}% \def\move#1#2#3{%
\advance \hanoidepth by -1 \ifnum \hanoidepth > 0 \move #1#3#2 \fi Move the upper disk from pole #1 to pole #3.\par \ifnum \hanoidepth > 0 \move#2#1#3 \fi \advance \hanoidepth by 1
}
\hanoi{5} \end</lang>
PostScript
A million-page document, each page showing one move. <lang PostScript>%!PS-Adobe-3.0 %%BoundingBox: 0 0 300 300
/plate {
exch 100 mul 50 add exch th mul 10 add moveto dup s mul neg 2 div 0 rmoveto dup s mul 0 rlineto 0 th rlineto s neg mul 0 rlineto closepath gsave .5 setgray fill grestore 0 setgray stroke
} def
/drawtower {
0 1 2 { /x exch def /y 0 def tower x get { dup 0 gt { x y plate /y y 1 add def } {pop} ifelse } forall } for showpage
} def
/apop { [ exch aload pop /last exch def ] last } def /apush{ [ 3 1 roll aload pop counttomark -1 roll ] } def
/hanoi {
0 dict begin /from /mid /to /h 5 -1 2 { -1 roll def } for h 1 eq { tower from get apop tower to get apush tower to 3 -1 roll put tower from 3 -1 roll put drawtower } { /h h 1 sub def from to mid h hanoi from mid to 1 hanoi mid from to h hanoi } ifelse end
} def
/n 12 def
/s 90 n div def
/th 180 n div def
/tower [ [n 1 add -1 2 { } for ] [] [] ] def
drawtower 0 1 2 n hanoi
%%EOF</lang>
Prolog
From Programming in Prolog by W.F. Clocksin & C.S. Mellish <lang prolog>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.</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>
- Output:
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
recursive
<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>
- Output:
for ndisks=2
Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3
There is a 3D hanoi-game in the examples that come with VPython, and at github.
R
<lang rsplus>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>
Racket
<lang racket>
- lang racket
(define (hanoi n a b c)
(when (> n 0) (hanoi (- n 1) a c b) (printf "Move ~a to ~a\n" a b) (hanoi (- n 1) c b a)))
(hanoi 4 'left 'middle 'right) </lang>
Rascal
<lang rascal>public void hanoi(ndisks, startPeg, endPeg){ if(ndisks>0){ hanoi(ndisks-1, startPeg, 6 - startPeg - endPeg); println("Move disk <ndisks> from peg <startPeg> to peg <endPeg>"); hanoi(ndisks-1, 6 - startPeg - endPeg, endPeg); } }</lang>
- Output:
<lang rascal>rascal>hanoi(4,1,3) Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 3 from peg 1 to peg 2 Move disk 1 from peg 3 to peg 1 Move disk 2 from peg 3 to peg 2 Move disk 1 from peg 1 to peg 2 Move disk 4 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 2 from peg 2 to peg 1 Move disk 1 from peg 3 to peg 1 Move disk 3 from peg 2 to peg 3 Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 ok</lang>
Raven
<lang raven>define hanoi use ndisks, startpeg, endpeg
ndisks 0 > if 6 startpeg - endpeg - startpeg ndisks 1 - hanoi endpeg startpeg ndisks "Move disk %d from peg %d to peg %d\n" print endpeg 6 startpeg - endpeg - ndisks 1 - hanoi
define dohanoi use ndisks
# startpeg=1, endpeg=3 3 1 ndisks hanoi
- 4 disks
4 dohanoi </lang>
- Output:
raven hanoi.rv Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 3 from peg 1 to peg 2 Move disk 1 from peg 3 to peg 1 Move disk 2 from peg 3 to peg 2 Move disk 1 from peg 1 to peg 2 Move disk 4 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 2 from peg 2 to peg 1 Move disk 1 from peg 3 to peg 1 Move disk 3 from peg 2 to peg 3 Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3
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
Retro
<lang Retro>4 elements a b c n
- vars !c !b !a !n ;
- hanoi ( num from to via -- )
vars @n 0 <> [ @n @a @b @c @n 1- @a @c @b hanoi vars @b @a "\nMove a ring from %d to %d" puts @n 1- @c @b @a hanoi ] ifTrue ;
4 1 3 2 hanoi</lang>
REXX
simple text moves
<lang rexx>/*REXX pgm shows the moves to solve the Tower of Hanoi (with 3 disks). */ parse arg N . /*get optional # towers from C.L.*/ if N== then N=3 /*Not given? Use default 3 towers*/
- =0; z=2**N - 1 /*number of ring moves so far. */
call mov 1, 3, N /*move top ring, then recurse··· */ say say 'The minimum number of moves to solve a ' N " Tower of Hanoi is " z exit /*stick a fork in it, we're done.*/ /*─────────────────────────────DSK subroutine───────────────────────────*/ dsk: #=#+1 /*bump the move counter by one. */ say 'step' right(#,length(z))": move disk on tower" arg(1) '───►' arg(2) return /*─────────────────────────────MOV subroutine───────────────────────────*/ mov: procedure expose # z; parse arg @1, @2, @3 if @3==1 then call dsk @1, @2
else do call mov @1, 6-@1-@2, @3-1 call mov @1, @2, 1 call mov 6-@1-@2, @2, @3-1 end
return</lang>
- Output:
when the default input was used
step 1: move disk on tower 1 ───► 3 step 2: move disk on tower 1 ───► 2 step 3: move disk on tower 3 ───► 2 step 4: move disk on tower 1 ───► 3 step 5: move disk on tower 2 ───► 1 step 6: move disk on tower 2 ───► 3 step 7: move disk on tower 1 ───► 3 The minimum number of moves to solve a 3 Tower of Hanoi is 7
- Output:
when the following was entered (to solve with four towers)
step 1: move disk on tower 1 ───► 2 step 2: move disk on tower 1 ───► 3 step 3: move disk on tower 2 ───► 3 step 4: move disk on tower 1 ───► 2 step 5: move disk on tower 3 ───► 1 step 6: move disk on tower 3 ───► 2 step 7: move disk on tower 1 ───► 2 step 8: move disk on tower 1 ───► 3 step 9: move disk on tower 2 ───► 3 step 10: move disk on tower 2 ───► 1 step 11: move disk on tower 3 ───► 1 step 12: move disk on tower 2 ───► 3 step 13: move disk on tower 1 ───► 2 step 14: move disk on tower 1 ───► 3 step 15: move disk on tower 2 ───► 3 The minimum number of moves to solve a 4 Tower of Hanoi is 15
pictorial moves
This version pictorially shows the moves for solving the Town of Hanoi.
Quite a bit of code has been dedicated to showing a picture of the towers with the disks, and the movement of the disk (the move). Coloring of the rings is attempted with dithering.
In addition, it shows each move in a countdown manner (the last move is marked as #1).
No attempt is made to explain this version of the REXX program 'cause of the complexity and somewhat obtuse features of the REXX language, the smallest of which is support for ASCII and EBCDIC "graphic" characters (glyphs). It may not be obvious from the pictorial display of the moves, but whenever a ring is moved from one tower to another, it is always the top ring that is moved (to the target tower). <lang rexx>/*REXX pgm shows pictorial moves to solve Tower of Hanoi (with N disks).*/ parse arg N .; if N== then N=3 /*Not given? Use default 3 disks.*/ sw=80; wp=sw%3-1; blanks=center(,wp) /*define some default variables. */ c.1=sw%3%2 c.2=sw%2-1 c.3=sw-1-c.1-1
- =0; z=2**N-1; movek=z
@abc='abcdefghijklmnopqrstuvwxyN' /*dithering chars when many disks*/ ebcdic= 'f0'x==0 /*determine if EBCDIC or ASCII*/ if ebcdic then do
bar='bf'x;ar='df'x;boxen='db9f9caf'x;tl='ac'x;tr='bf'x;bl='ab'x;br='bb'x;vert='fa'x;down='9a'x end else do bar='c4'x;ar='10'x;boxen='b0b1b2db'x;tl='da'x;tr='bf'x;bl='c0'x;br='d9'x;vert='b3'x;down='19'x end
verts=vert || vert downs=down || down Tcorners=tl || tr Bcorners=bl || br box=left(boxen,1); boxchars=boxen || @abc bararrow=bar || bar || ar $.=0; $.1=N; k=N; kk=k+k
do j=1 for N @.3.j=blanks; @.2.j=blanks @.1.j=center(copies(box,kk),wp) if N<=length(boxchars) then @.1.j=translate(@.1.j, , substr(boxchars,kk%2,1),box) kk=kk-2 end /*j*/
call showtowers; call mov 1,3,N say say "The minimum number of moves to solve a " N ' Tower of Hanoi is ' z exit /*─────────────────────────────MOV subroutine───────────────────────────*/ mov: if arg(3)==1 then call rng arg(1) arg(2)
else do call mov arg(1), 6-arg(1)-arg(2), arg(3)-1 call mov arg(1), arg(2), 1 call mov 6-arg(1)-arg(2),arg(2), arg(3)-1 end
return /*─────────────────────────────RNG subroutine───────────────────────────*/ rng: parse arg from dest; #=#+1; pp= if from==1 then do
pp=overlay(bl,pp,c.1) pp=overlay(bar,pp,c.1+1,c.dest-c.1-1,bar) pp=pp || tr end
if from==3 then do
pp=overlay(br,pp,c.3) pp=overlay(bar,pp,c.dest+1,c.3-c.dest-1,bar) pp=overlay(tl,pp,c.dest) end
if from==2 then do
lpost=min(2,dest) hpost=max(2,dest) if dest==1 then do pp=overlay(tl,pp,c.1) pp=overlay(bar,pp,c.1+1,c.2-c.1-1,bar) pp=pp || br end if dest==3 then do pp=overlay(bl,pp,c.2) pp=overlay(bar,pp,c.2+1,c.3-c.2-1,bar) pp=pp || tr end end
say translate(pp,downs,Bcorners||Tcorners||bar); say overlay(movek,pp,1) say translate(pp,verts,Tcorners||Bcorners||bar) say translate(pp,downs,Tcorners||Bcorners||bar) movek=movek-1 $.from=$.from-1; $.dest=$.dest+1; _f=$.from+1; _t=$.dest @.dest._t=@.from._f; @.from._f=blanks call showtowers return /*─────────────────────────────SHOWTOWERS subroutine────────────────────*/ showtowers: do j=N by -1 for N
_=@.1.j @.2.j @.3.j; if _\= then say _ end /*j*/
return</lang>
- Output:
when the default input was used
░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓ 7 └───────────────────────────────────────────────────┐ │ ↓ ▒▒▒▒ ▓▓▓▓▓▓ ░░ ↓ 6 └─────────────────────────┐ │ ↓ ▓▓▓▓▓▓ ▒▒▒▒ ░░ ↓ 5 ┌─────────────────────────┘ │ ↓ ░░ ▓▓▓▓▓▓ ▒▒▒▒ ↓ 4 └───────────────────────────────────────────────────┐ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓ 3 ┌─────────────────────────┘ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓ 2 └─────────────────────────┐ │ ↓ ▒▒▒▒ ░░ ▓▓▓▓▓▓ ↓ 1 └───────────────────────────────────────────────────┐ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓ The minimum number of moves to solve a 3 Tower of Hanoi is 7
Ruby
<lang ruby>def move(num_disks, start=0, target=1, using=2)
if num_disks == 1 @towers[target] << @towers[start].pop puts "Move disk from #{start} to #{target} : #{@towers}" else move(num_disks-1, start, using, target) move(1, start, target, using) move(num_disks-1, using, target, start) end
end
n = 5 @towers = [[*1..n].reverse, [], []] move(n)</lang>
- Output:
Move disk from 0 to 1 : [[5, 4, 3, 2], [1], []] Move disk from 0 to 2 : [[5, 4, 3], [1], [2]] Move disk from 1 to 2 : [[5, 4, 3], [], [2, 1]] Move disk from 0 to 1 : [[5, 4], [3], [2, 1]] Move disk from 2 to 0 : [[5, 4, 1], [3], [2]] Move disk from 2 to 1 : [[5, 4, 1], [3, 2], []] Move disk from 0 to 1 : [[5, 4], [3, 2, 1], []] Move disk from 0 to 2 : [[5], [3, 2, 1], [4]] Move disk from 1 to 2 : [[5], [3, 2], [4, 1]] Move disk from 1 to 0 : [[5, 2], [3], [4, 1]] Move disk from 2 to 0 : [[5, 2, 1], [3], [4]] Move disk from 1 to 2 : [[5, 2, 1], [], [4, 3]] Move disk from 0 to 1 : [[5, 2], [1], [4, 3]] Move disk from 0 to 2 : [[5], [1], [4, 3, 2]] Move disk from 1 to 2 : [[5], [], [4, 3, 2, 1]] Move disk from 0 to 1 : [[], [5], [4, 3, 2, 1]] Move disk from 2 to 0 : [[1], [5], [4, 3, 2]] Move disk from 2 to 1 : [[1], [5, 2], [4, 3]] Move disk from 0 to 1 : [[], [5, 2, 1], [4, 3]] Move disk from 2 to 0 : [[3], [5, 2, 1], [4]] Move disk from 1 to 2 : [[3], [5, 2], [4, 1]] Move disk from 1 to 0 : [[3, 2], [5], [4, 1]] Move disk from 2 to 0 : [[3, 2, 1], [5], [4]] Move disk from 2 to 1 : [[3, 2, 1], [5, 4], []] Move disk from 0 to 1 : [[3, 2], [5, 4, 1], []] Move disk from 0 to 2 : [[3], [5, 4, 1], [2]] Move disk from 1 to 2 : [[3], [5, 4], [2, 1]] Move disk from 0 to 1 : [[], [5, 4, 3], [2, 1]] Move disk from 2 to 0 : [[1], [5, 4, 3], [2]] Move disk from 2 to 1 : [[1], [5, 4, 3, 2], []] Move disk from 0 to 1 : [[], [5, 4, 3, 2, 1], []]
or <lang ruby># solve(source, via, target)
- Example:
- solve([5, 4, 3, 2, 1], [], [])
- Note this will also solve randomly placed disks,
- "place all disk in target with legal moves only".
def solve(*towers)
# total number of disks disks = towers.inject(0){|sum, tower| sum+tower.length} x=0 # sequence number p towers # initial trace # have we solved the puzzle yet? while towers.last.length < disks do x+=1 # assume the next step from = (x&x-1)%3 to = ((x|(x-1))+1)%3 # can we actually take from tower? if top = towers[from].last bottom = towers[to].last # is the move legal? if !bottom || bottom > top # ok, do it! towers[to].push(towers[from].pop) p towers # trace end end end
end
solve([5, 4, 3, 2, 1], [], [])</lang>
- Output:
[[5, 4, 3, 2, 1], [], []] [[5, 4, 3, 2], [], [1]] [[5, 4, 3], [2], [1]] [[5, 4, 3], [2, 1], []] [[5, 4], [2, 1], [3]] [[5, 4, 1], [2], [3]] [[5, 4, 1], [], [3, 2]] [[5, 4], [], [3, 2, 1]] [[5], [4], [3, 2, 1]] [[5], [4, 1], [3, 2]] [[5, 2], [4, 1], [3]] [[5, 2, 1], [4], [3]] [[5, 2, 1], [4, 3], []] [[5, 2], [4, 3], [1]] [[5], [4, 3, 2], [1]] [[5], [4, 3, 2, 1], []] [[], [4, 3, 2, 1], [5]] [[1], [4, 3, 2], [5]] [[1], [4, 3], [5, 2]] [[], [4, 3], [5, 2, 1]] [[3], [4], [5, 2, 1]] [[3], [4, 1], [5, 2]] [[3, 2], [4, 1], [5]] [[3, 2, 1], [4], [5]] [[3, 2, 1], [], [5, 4]] [[3, 2], [], [5, 4, 1]] [[3], [2], [5, 4, 1]] [[3], [2, 1], [5, 4]] [[], [2, 1], [5, 4, 3]] [[1], [2], [5, 4, 3]] [[1], [], [5, 4, 3, 2]] [[], [], [5, 4, 3, 2, 1]]
Run BASIC
<lang runbasic>a = move(4, "1", "2", "3") function move(n, a$, b$, c$) if n > 0 then a = move(n-1, a$, c$, b$) print "Move disk from " ; a$ ; " to " ; c$ a = move(n-1, b$, a$, c$) end if end function</lang>
Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2 Move disk from 1 to 3 Move disk from 2 to 1 Move disk from 2 to 3 Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2 Move disk from 3 to 1 Move disk from 2 to 1 Move disk from 3 to 2 Move disk from 1 to 3 Move disk from 1 to 2 Move disk from 3 to 2
Rust
<lang rust> fn move(n: int, from: int, to: int, via: int) {
if n > 0 { move(n - 1, from, via, to); println!("Move disk from pole {:d} to pole {:d}", from, to); move(n - 1, via, to, from); }
}
fn main() {
move(4, 1,2,3);
} </lang>
Sather
<lang sather>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;</lang>
Scala
<lang scala>def move(n: Int, from: Int, to: Int, via: Int) : Unit = {
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>
SNOBOL4
<lang 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</lang>
- 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
Swift
<lang Swift>func hanoi(n:Int, a:String, b:String, c:String) {
if (n > 0) { hanoi(n - 1, a, c, b) println("Move disk from \(a) to \(c)") hanoi(n - 1, b, a, c) }
}
hanoi(4, "A", "B", "C")</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>
- Output:
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
TI-83 BASIC
TI-83 BASIC lacks recursion, so technically this task is impossible, however here is a version that uses an iterative method. <lang ti-83b>PROGRAM:TOHSOLVE 0→A 1→B 0→C 0→D 0→M 1→R While A<1 or A>7 Input "No. of rings=?",A End randM(A+1,3)→[C] [[1,2][1,3][2,3]]→[E]
Fill(0,[C]) For(I,1,A,1) I?[C](I,1) End ClrHome While [C](1,3)≠1 and [C](1,2)≠1
For(J,1,3) For(I,1,A) If [C](I,J)≠0:Then Output(I+1,3J,[C](I,J)) End End End While C=0 Output(1,3B," ") 1→I [E](R,2)→J While [C](I,J)=0 and I≤A I+1→I End [C](I,J)→D 1→I [E](R,1)→J While [C](I,J)=0 and I≤A I+1→I End If (D<[C](I,J) and D≠0) or [C](I,J)=0:Then [E](R,2)→B Else [E](R,1)→B End
1→I While [C](I,B)=0 and I≤A I+1→I End If I≤A:Then [C](I,B)→C 0→[C](I,B) Output(I+1,3B," ") End Output(1,3B,"V") End
While C≠0 Output(1,3B," ") If B=[E](R,2):Then [E](R,1)→B Else [E](R,2)→B End
1→I While [C](I,B)=0 and I≤A I+1→I End If [C](I,B)=0 or [C](I,B)>C:Then C→[C](I-1,B) 0→C M+1→M End End Output(1,3B,"V") R+1→R If R=4:Then:1→R:End
End </lang>
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>
TSE SAL
<lang TSESAL>// library: program: run: towersofhanoi: recursive: sub <description></description> <version>1.0.0.0.0</version> <version control></version control> (filenamemacro=runprrsu.s) [kn, ri, tu, 07-02-2012 19:54:23] PROC PROCProgramRunTowersofhanoiRecursiveSub( INTEGER totalDiskI, STRING fromS, STRING toS, STRING viaS, INTEGER bufferI )
IF ( totalDiskI == 0 ) RETURN() ENDIF PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI - 1, fromS, viaS, toS, bufferI ) AddLine( Format( "Move disk", " ", totalDiskI, " ", "from peg", " ", "'", fromS, "'", " ", "to peg", " ", "'", toS, "'" ), bufferI ) PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI - 1, viaS, toS, fromS, bufferI )
END
// library: program: run: towersofhanoi: recursive <description></description> <version>1.0.0.0.6</version> <version control></version control> (filenamemacro=runprtre.s) [kn, ri, tu, 07-02-2012 19:40:45] PROC PROCProgramRunTowersofhanoiRecursive( INTEGER totalDiskI, STRING fromS, STRING toS, STRING viaS )
INTEGER bufferI = 0 PushPosition() bufferI = CreateTempBuffer() PopPosition() PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI, fromS, toS, viaS, bufferI ) GotoBufferId( bufferI )
END
PROC Main() STRING s1[255] = "4" IF ( NOT ( Ask( "program: run: towersofhanoi: recursive: totalDiskI = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF
PROCProgramRunTowersofhanoiRecursive( Val( s1 ), "source", "target", "via" )
END</lang>
UNIX Shell
<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
- 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>
XPL0
<lang XPL0>code Text=12;
proc MoveTower(Discs, From, To, Using); int Discs, From, To, Using; [if Discs > 0 then
[MoveTower(Discs-1, From, Using, To); Text(0, "Move from "); Text(0, From); Text(0, " peg to "); Text(0, To); Text(0, " peg.^M^J"); MoveTower(Discs-1, Using, To, From); ];
];
MoveTower(3, "left", "right", "center")</lang>
- Output:
Move from left peg to right peg. Move from left peg to center peg. Move from right peg to center peg. Move from left peg to right peg. Move from center peg to left peg. Move from center peg to right peg. Move from left peg to right peg.
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>
XQuery
<lang 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></lang>
- Output:
<lang xml><?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></lang>
zkl
<lang zkl>fcn move(n, from,to,via){
if (n>0){ move(n-1, from,via,to); println("Move disk from pole %d to pole %d".fmt(from, to)); move(n-1, via,to,from); }
} move(3, 1,2,3);</lang>
- Output:
Move disk from pole 1 to pole 2 Move disk from pole 1 to pole 3 Move disk from pole 2 to pole 3 Move disk from pole 1 to pole 2 Move disk from pole 3 to pole 1 Move disk from pole 3 to pole 2 Move disk from pole 1 to pole 2
- Programming Tasks
- Classic CS problems and programs
- Recursion
- Games
- ActionScript
- Ada
- Agena
- ALGOL 68
- AmigaE
- AppleScript
- AutoHotkey
- AutoIt
- AWK
- BASIC
- BASIC256
- BBC BASIC
- Bracmat
- Brainfuck
- C
- C sharp
- C++
- Clojure
- COBOL
- CoffeeScript
- Common Lisp
- D
- Dart
- Dc
- E
- Eiffel
- Emacs Lisp
- Erlang
- ERRE
- Ezhil
- F Sharp
- FALSE
- Factor
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Inform 7
- Io
- Ioke
- J
- Java
- JavaScript
- Joy
- Jq
- K
- Lasso
- Liberty BASIC
- Logo
- Logtalk
- Lua
- Mathematica
- MATLAB
- МК-61/52
- Modula-3
- Monte
- Nemerle
- NetRexx
- NewLISP
- Nim
- Objective-C
- OCaml
- Octave
- Oforth
- Oz
- Pascal
- Perl
- Perl 6
- PHL
- PHP
- PicoLisp
- Pop11
- PL/I
- PlainTeX
- PostScript
- Prolog
- PureBasic
- Python
- VPython
- R
- Racket
- Rascal
- Raven
- REBOL
- Retro
- REXX
- Ruby
- Run BASIC
- Rust
- Sather
- Scala
- Scheme
- Seed7
- SNOBOL4
- Swift
- Tcl
- TI-83 BASIC
- Toka
- TSE SAL
- UNIX Shell
- Ursala
- Vedit macro language
- Visual Basic .NET
- XPL0
- XSLT
- XQuery
- Zkl
- Puzzles