Solve the Towers of Hanoi problem with recursion.
F hanoi(ndisks, startPeg = 1, endPeg = 3) -> Void I ndisks hanoi(ndisks - 1, startPeg, 6 - startPeg - endPeg) print(‘Move disk #. from peg #. to peg #.’.format(ndisks, startPeg, endPeg)) hanoi(ndisks - 1, 6 - startPeg - endPeg, endPeg)hanoi(ndisks' 3)
Move disk 1 from peg 1 to peg 3Move disk 2 from peg 1 to peg 2Move disk 1 from peg 3 to peg 2Move disk 3 from peg 1 to peg 3Move disk 1 from peg 2 to peg 1Move disk 2 from peg 2 to peg 3Move disk 1 from peg 1 to peg 3
* Towers of Hanoi 08/09/2015HANOITOW CSECT USING HANOITOW,R12 r12 : base register LR R12,R15 establish base register ST R14,SAVE14 save r14BEGIN LH R2,=H'4' n <=== L R3,=C'123 ' stating position BAL R14,MOVE r1=move(m,n)RETURN L R14,SAVE14 restore r14 BR R14 return to callerSAVE14 DS F static save r14PG DC CL44'xxxxxxxxxxxx Move disc from pole X to pole Y' NN DC F'0'POLEX DS F current polesPOLEN DS F new poles* .... recursive subroutine move(n, poles) [r2,r3]MOVE LR R10,R11 save stackptr (r11) in r10 temp LA R1,STACKLEN amount of storage required GETMAIN RU,LV=(R1) allocate storage for stack USING STACKDS,R11 make storage addressable LR R11,R1 establish stack addressability ST R14,SAVE14M save previous r14 ST R10,SAVE11M save previous r11 LR R1,R5 restore saved argument r5BEGINM STM R2,R3,STACK push arguments to stack ST R3,POLEX CH R2,=H'1' if n<>1 BNE RECURSE then goto recurse L R1,NN LA R1,1(R1) nn=nn+1 ST R1,NN XDECO R1,PG nn MVC PG+33(1),POLEX+0 from MVC PG+43(1),POLEX+1 to XPRNT PG,44 print "move disk from to" B RETURNMRECURSE L R2,N n BCTR R2,0 n=n-1 MVC POLEN+0(1),POLES+0 from MVC POLEN+1(1),POLES+2 via MVC POLEN+2(1),POLES+1 to L R3,POLEN new poles BAL R14,MOVE call move(n-1,from,via,to) LA R2,1 n=1 MVC POLEN,POLES L R3,POLEN new poles BAL R14,MOVE call move(1,from,to,via) L R2,N n BCTR R2,0 n=n-1 MVC POLEN+0(1),POLES+2 via MVC POLEN+1(1),POLES+1 to MVC POLEN+2(1),POLES+0 from L R3,POLEN new poles BAL R14,MOVE call move(n-1,via,to,from)RETURNM LM R2,R3,STACK pull arguments from stack LR R1,R11 current stack L R14,SAVE14M restore r14 L R11,SAVE11M restore r11 LA R0,STACKLEN amount of storage to free FREEMAIN A=(R1),LV=(R0) free allocated storage BR R14 return to caller LTORG DROP R12 base no longer neededSTACKDS DSECT dynamic areaSAVE14M DS F saved r14SAVE11M DS F saved r11STACK DS 0F stackN DS F r2 nPOLES DS F r3 polesSTACKLEN EQU *-STACKDS YREGS END HANOITOW
1 Move disc from pole 1 to pole 3 2 Move disc from pole 1 to pole 2 3 Move disc from pole 3 to pole 2 4 Move disc from pole 1 to pole 3 5 Move disc from pole 2 to pole 1 6 Move disc from pole 2 to pole 3 7 Move disc from pole 1 to pole 3 8 Move disc from pole 1 to pole 2 9 Move disc from pole 3 to pole 2 10 Move disc from pole 3 to pole 1 11 Move disc from pole 2 to pole 1 12 Move disc from pole 3 to pole 2 13 Move disc from pole 1 to pole 3 14 Move disc from pole 1 to pole 2 15 Move disc from pole 3 to pole 2
This should work on any Commodore 8-bit computer; just set `temp` to an appropriate zero-page location.
temp = $FB ; this works on a VIC-20 or C-64; adjust for other machines. Need two bytes zero-page space unused by the OS.; kernal print-char routinechrout = $FFD2; Main Towers of Hanoi routine. To call, load the accumulator with the number of disks to move,; the X register with the source peg (1-3), and the Y register with the target peg.hanoi: cmp #$00 ; do nothing if the number of disks to move is zero bne nonzero rtsnonzero: pha ; save registers on stack txa pha tya pha pha ; and make room for the spare peg number ; Parameters are now on the stack at these offsets: count = $0104 source = $0103 target = $0102 spare = $0101 ; compute spare rod number (6 - source - dest) tsx lda #6 sec sbc source, x sec sbc target, x sta spare, x ; prepare for first recursive call tay ; target is the spare peg tsx lda source, x ; source is the same sta temp ; we're using X to access the stack, so save its value here for now lda count, x ; move count - 1 disks sec sbc #1 ldx temp ; now load X for call ; and recurse jsr hanoi ; restore X and Y for print call tsx ldy target, x lda source, x tax ; print instructions to move the last disk jsr print_move ; prepare for final recursive call tsx lda spare, x ; source is now spare sta temp lda target, x ; going to the original target tay lda count, x ; and again moving count-1 disks sec sbc #1 ldx temp jsr hanoi ; pop our stack frame, restore registers, and return pla pla tay pla tax pla rts; constants for printingprelude: .asciiz "MOVE DISK FROM "interlude: .asciiz " TO "postlude: .byte 13,0; print instructions: move disk from (X) to (Y)print_move: pha txa pha tya pha ; Parameters are now on the stack at these offsets: from = $0102 to = $0101 lda #<prelude ldx #>prelude jsr print_string tsx lda from,x clc adc #$30 jsr chrout lda #<interlude ldx #>interlude jsr print_string tsx lda to,x clc adc #$30 jsr chrout lda #<postlude ldx #>postlude jsr print_string pla tay pla tax pla rts; utility routine: print null-terminated string at address AXprint_string: sta temp stx temp+1 ldy #0loop: lda (temp),y beq done_print jsr chrout iny bne loopdone_print: rts
MOVE DISK FROM 1 TO 2MOVE DISK FROM 1 TO 3MOVE DISK FROM 2 TO 3MOVE DISK FROM 1 TO 2MOVE DISK FROM 3 TO 1MOVE DISK FROM 3 TO 2MOVE DISK FROM 1 TO 2MOVE DISK FROM 1 TO 3MOVE DISK FROM 2 TO 3MOVE DISK FROM 2 TO 1MOVE DISK FROM 3 TO 1MOVE DISK FROM 2 TO 3MOVE DISK FROM 1 TO 2MOVE DISK FROM 1 TO 3MOVE DISK FROM 2 TO 3
org100hlhld6; Top of CP/M usable memorysphl; Put the stack therelxib,0401h; Set up first arguments to move()lxid,0203hcallmove; move(4, 1, 2, 3)rst0; quit program;;;Move B disks from C via D to E. move:dcrb; One fewer disk in next iterationjzmvout; If this was the last disk, print move and stoppushb; Otherwise, save registers,pushd mova,d; First recursive callmovd,emove,acallmove; move(B-1, C, E, D)popd; Restore registerspopbcallmvout; Print current movemova,c; Second recursive callmovc,dmovd,ajmpmove; move(B-1, D, C, E) - tail call optimization;;;Print move, saving registers.mvout:pushb; Save registers on stackpushdmova,c; Store 'from' as ASCII digit in 'from' spaceadi'0'staout1mova,e; Store 'to' as ASCII digit in 'to' spaceadi'0'staout2lxid,outstrmvic,9; CP/M call to print the stringcall5popd; Restore register contentspopbret;;;Move output with placeholder for pole numbersoutstr:db'Move disk from pole 'out1:db'* to pole 'out2:db'*',13,10,'$'
Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
cpu8086bits16org100hsection.textmovbx,0402h; Set up first arguments to move()movcx,0103h; Registers chosen s.t. CX contains output;;;Move BH disks from CH via BL to CLmove:decbh; One fewer disk in next iterationjz.out; If this was last disk, just print movepushbx; Save the registers for a recursive callpushcxxchgbl,cl; Swap the 'to' and 'via' registerscallmove; move(BH, CH, CL, BL)popcx; Restore the registers from the stackpopbxcall.out; Print the movexchgch,bl; Swap the 'from' and 'via' registersjmpmove; move(BH, BL, CH, CL);;;Print the move.out:movax,'00'; Add ASCII 0 to both 'from' and 'to'addax,cx; in one 16-bit operationmov[out1],ah; Store 'from' field in outputmov[out2],al; Store 'to' field in outputmovdx,outstr; MS-DOS system call to print stringmovah,9int21hretsection.dataoutstr:db'Movediskfrompole'out1:db'*topole'out2:db'*',13,10,'$'
Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
5var,disksvarsavarsbvarsc:savesc!sb!sa!disks!;:getsa@sb@sc@;:get2getswap;:hanoisavedisks@notif;;thendisks@getdisks@n:1-get2hanoisavecr"movearingfrom".sa@."to".sb@.disks@n:1-get2rothanoi;"TowerofHanoi,with".disks@."rings:".disks@123hanoicrbye
HOW TO MOVE n DISKS FROM src VIA via TO dest: IF n>0: MOVE n-1 DISKS FROM src VIA dest TO via WRITE "Move disk from pole", src, "to pole", dest/ MOVE n-1 DISKS FROM via VIA dest TO srcMOVE 4 DISKS FROM 1 VIA 2 TO 3
Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 1Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 3Move disk from pole 2 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 3
...via PL/M
;;; Iterative Towers of Hanoi; translated from Tiny BASIC via PL/M;;;DEFINE NUMBER_OF_DISCS = "4"PROC Main() INT d, n, x n = 1 FOR d = 1 TO NUMBER_OF_DISCS DO n = n + n OD FOR x = 1 TO n - 1 DO ; as with Algol W, PL/M, Action! has bit and MOD operators Print( "Move disc on peg " ) Put( '1 + ( ( x AND ( x - 1 ) ) MOD 3 ) ) Print( " to peg " ) Put( '1 + ( ( ( x OR ( x - 1 ) ) + 1 ) MOD 3 ) ) PutE() ODRETURN
Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2Move disc on peg 1 to peg 3Move disc on peg 2 to peg 1Move disc on peg 2 to peg 3Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2Move disc on peg 3 to peg 1Move disc on peg 2 to peg 1Move disc on peg 3 to peg 2Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2
publicfunctionmove(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);}}
withAda.Text_Io;useAda.Text_Io;procedureTowersistypePegsis(Left,Center,Right);procedureHanoi(Ndisks:Natural;Start_Peg:Pegs:=Left;End_Peg:Pegs:=Right;Via_Peg:Pegs:=Center)isbeginifNdisks>0thenHanoi(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);endif;endHanoi;beginHanoi(4);endTowers;
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) fiendmove(4, 1, 2, 3)
begin procedure movedisk(n, f, t); integer n, f, t; begin outstring (1, "Move disk from"); outinteger(1, f); outstring (1, "to"); outinteger(1, t); outstring (1, "\n"); end; procedure dohanoi(n, f, t, u); integer n, f, t, u; begin if n < 2 then movedisk(1, f, t) else begin dohanoi(n - 1, f, u, t); movedisk(1, f, t); dohanoi(n - 1, u, t, f); end; end; dohanoi(4, 1, 2, 3); outstring(1,"Towers of Hanoi puzzle completed!")end
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!
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))
COMMENT Disk number is also printed in this code (works with a68g): COMMENT
PROC move = (INT n, from, to, via) VOID: IF n > 0 THEN move(n - 1, from, via, to); printf(($"Move disk "g" from pole "g" to pole "gl$, n, from, to)); move(n - 1, via, to, from) FI ;main: ( move(4, 1,2,3))
beginprocedure move(n, src, via, dest);integer n;string(1) src, via, dest;begin if n > 0 then begin move(n-1, src, dest, via); write("Move disk from pole "); writeon(src); writeon(" to pole "); writeon(dest); move(n-1, via, src, dest); end;end;move(4, "1", "2", "3");endMove disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
Following Agena, Algol 68, AmigaE...
beginproceduremove(integervaluen,from,to,via);ifn>0thenbeginmove(n-1,from,via,to);write(i_w:=1,s_w:=0,"Movediskfrompeg:",from,"topeg:",to);move(n-1,via,to,from)endmove;move(4,1,2,3)end.
begin%iterativetowersofhanoi-translatedfromTinyBasic%integerd,n;whilebeginwriteon("Howmanydisks?");read(d);d<1ord>10enddobeginend;n:=1;whilednot=0dobegind:=d-1;n:=2*nend;forx:=1untiln-1dobeginintegers,t;%AlgolWhasthenecessarybitandmodulooperatorssotheseareusedhere%%insteadofimplementingthemviasubroutines%s:=number(bitstring(x)andbitstring(x-1))rem3;t:=(number(bitstring(x)orbitstring(x-1))+1)rem3;write(i_w:=1,s_w:=0,"Movedisconpeg",s+1,"topeg",t+1)endend.
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) ENDIFENDPROCPROC main() move(4, 1,2,3)ENDPROC#include <hopper.h>#proto hanoi(_X_,_Y_,_Z_,_W_)main: get arg number (2,discos) {discos}!neg? do{fail=0,mov(fail),{"I need a positive (or zero) number here, not: ",fail}println,exit(0)} pos? do{ _hanoi( discos, "A", "B", "C" ) }exit(0).localshanoi(discos,inicio,aux,fin) iif( {discos}eqto(1), {inicio, "->", fin, "\n"};print, _hanoi({discos}minus(1), inicio,fin,aux);\ {inicio, "->", fin, "\n"};print;\ _hanoi({discos}minus(1), aux, inicio, fin))backFor 4 discs:A->BA->CB->CA->BC->AC->BA->BA->CB->CB->AC->AB->CA->BA->CB->C
hanoi←{move←{nfromtovia←⍵n≤0:⍬l←∇(n-1)fromviator←∇(n-1)viatofroml,(⊂fromto),r}'⊂Move disk from pole ⊃,I1,⊂ to pole ⊃,I1'⎕FMT↑move⍵}
hanoi 4 1 2 3Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2Move disk from pole 3 to pole 1Move disk from pole 2 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2
--------------------- TOWERS OF HANOI ---------------------- hanoi :: Int -> (String, String, String) -> [(String, String)]onhanoi(n,abc)scriptgoon|λ|(n,{x,y,z})ifn>0thensetmton-1|λ|(m,{x,z,y})&¬{{x,y}}&|λ|(m,{z,y,x})else{}endifend|λ|endscriptgo's|λ|(n,abc)endhanoi--------------------------- TEST -------------------------onrununlines(map(intercalate(" -> "),¬hanoi(3,{"left","right","mid"})))endrun-------------------- GENERIC FUNCTIONS --------------------- intercalate :: String -> [String] -> Stringonintercalate(delim)scripton|λ|(xs)set{dlm,mytext item delimiters}to¬{mytext item delimiters,delim}setstoxsastextsetmytext item delimiterstodlmsend|λ|endscriptendintercalate-- Lift 2nd class handler function into 1st class script wrapper-- mReturn :: First-class m => (a -> b) -> m (a -> b)onmReturn(f)ifclassoffisscriptthenfelsescriptproperty|λ|:fendscriptendifendmReturn-- map :: (a -> b) -> [a] -> [b]onmap(f,xs)tellmReturn(f)setlngtolengthofxssetlstto{}repeatwithifrom1tolngsetendoflstto|λ|(itemiofxs,i,xs)endrepeatreturnlstendtellendmap-- unlines :: [String] -> Stringonunlines(xs)set{dlm,mytext item delimiters}to¬{mytext item delimiters,linefeed}setstrtoxsastextsetmytext item delimiterstodlmstrendunlines
left -> rightleft -> midright -> midleft -> rightmid -> leftmid -> rightleft -> right
More illustratively:
(I've now eliminated the recursive|move|() handler's tail calls. So it's now only called 2 ^ (n - 1) times as opposed to 2 ^ (n + 1) - 1 with full recursion. The maximum call depth of n is only reached once, whereas with full recursion, the maximum depth was n + 1 and this was reached 2 ^ n times.)
onhanoi(n,source,target)sett1totab&"tower 1: "&tabsett2totab&"tower 2: "&tabsett3totab&"tower 3: "&tabscriptopropertym:0propertytower1:{}propertytower2:{}propertytower3:{}propertytowerRefs:{areference totower1,areference totower2,areference totower3}propertyprocess:missing valueon|move|(n,source,target)setauxto6-source-targetrepeatwithnfromnto2by-1-- Tail call elimination repeat.|move|(n-1,source,aux)setendofitemtargetofmytowerRefstontellitemsourceofmytowerRefstosetitscontentstoreverseofrestofitsreversesetmtom+1setendofmyprocessto¬{(mastext)&". move disc "&n&(" from tower "&source)&(" to tower "&target&":"),¬t1&tower1,¬t2&tower2,¬t3&tower3}tellsourcesetsourcetoauxsetauxtoitendtellendrepeat-- Specific code for n = 1:setendofitemtargetofmytowerRefsto1tellitemsourceofmytowerRefstosetitscontentstoreverseofrestofitsreversesetmtom+1setendofmyprocessto¬{(mastext)&". move disc 1 from tower "&source&(" to tower "&target&":"),¬t1&tower1,¬t2&tower2,¬t3&tower3}end|move|endscriptrepeatwithifromnto1by-1setendofitemsourceofo'stowerRefstoiendrepeatsetastidtoAppleScript'stext item delimiterssetAppleScript'stext item delimitersto", "seto'sprocessto{"Starting with "&n&(" discs on tower "&(source&":")),¬t1&o'stower1,t2&o'stower2,t3&o'stower3}if(n>0)thentelloto|move|(n,source,target)setendofo'sprocessto"That's it!"setAppleScript'stext item delimiterstolinefeedsetprocesstoo'sprocessastextsetAppleScript'stext item delimiterstoastidreturnprocessendhanoi-- Test:setnumberOfDiscsto3setsourceTowerto1setdestinationTowerto2hanoi(numberOfDiscs,sourceTower,destinationTower)
"Starting with 3 discs on tower 1: tower 1: 3, 2, 1 tower 2: tower 3: 1. move disc 1 from tower 1 to tower 2: tower 1: 3, 2 tower 2: 1 tower 3: 2. move disc 2 from tower 1 to tower 3: tower 1: 3 tower 2: 1 tower 3: 23. move disc 1 from tower 2 to tower 3: tower 1: 3 tower 2: tower 3: 2, 14. move disc 3 from tower 1 to tower 2: tower 1: tower 2: 3 tower 3: 2, 15. move disc 1 from tower 3 to tower 1: tower 1: 1 tower 2: 3 tower 3: 26. move disc 2 from tower 3 to tower 2: tower 1: 1 tower 2: 3, 2 tower 3: 7. move disc 1 from tower 1 to tower 2: tower 1: tower 2: 3, 2, 1 tower 3: That's it!"
.text.global_start_start:movr0,#4@ 4 disks,movr1,#1@ from pole 1,movr2,#2@ via pole 2,movr3,#3@ to pole 3.blmovemovr0,#0@ Exit to Linux afterwardsmovr7,#1swi#0@@@Move r0 disks from r1 via r2 to r3move:subsr0,r0,#1@ One fewer disk in next iterationbeqshow@ If last disk, just print movepush{r0-r3,lr}@ Save all the registers incl. link registereorr2,r2,r3@ Swap the 'to' and 'via' registerseorr3,r2,r3eorr2,r2,r3blmove@ Recursive callpop{r0-r3}@ Restore all the registers except LRblshow@ Show current moveeorr1,r1,r3@ Swap the 'to' and 'via' registerseorr3,r1,r3eorr1,r1,r3pop{lr}@ Restore link registerbmove@ Tail call@@@Show moveshow:push{r0-r3,lr}@ Save all the registersaddr1,r1,#'0@ Write the source poleldrlr,=spolestrbr1,[lr] addr3,r3,#'0@ Write the destination poleldrlr,=dpolestrbr3,[lr]movr0,#1@ 1 = stdoutldrr1,=moves@ Pointer to stringldrr2,=mlen@ Length of stringmovr7,#4@ 4 = Linux write syscallswi#0 @ Print the movepop{r0-r3,pc}@ Restore all the registers and return.datamoves:.ascii"Move disk from pole "spole:.ascii"* to pole "dpole:.ascii"*\n"mlen=. - movesMove disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 3 to pole 1Move disk from pole 1 to pole 2Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 2 to pole 3Move disk from pole 3 to pole 1Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 3 to pole 1
hanoi:function[nfdirvia][ifn>0[hanoin-1fviadirprint["Move disk"n"from"f"to"dir]hanoin-1viadirf]]hanoi3'L'M'R
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
voidhanoi(intn,stringorigen,stringauxiliar,stringdestino){if(n==1){write("Move disk 1 from "+origen+" to "+destino);}else{hanoi(n-1,origen,destino,auxiliar);write("Move disk "+string(n)+" from "+origen+" to "+destino);hanoi(n-1,auxiliar,origen,destino);}}hanoi(3,"pole 1","pole 2","pole 3");write("Towers of Hanoi puzzle completed!");
Move disk 1 from pole 1 to pole 3Move disk 2 from pole 1 to pole 2Move disk 1 from pole 3 to pole 2Move disk 3 from pole 1 to pole 3Move disk 1 from pole 2 to pole 1Move disk 2 from pole 2 to pole 3Move disk 1 from pole 1 to pole 3Towers of Hanoi puzzle completed!
move(n,from,to,via) ;n = # of disks, from = start pole, to = end pole, via = remaining pole{if(n=1){msgbox,Movediskfrompole%from%topole%to%}else{move(n-1,from,via,to)move(1,from,to,via)move(n-1,via,to,from)}}move(64,1,3,2)
Funcmove($n,$from,$to,$via)If($n=1)ThenConsoleWrite(StringFormat("Move disk from pole "&$from&" To pole "&$to&"\n"))Elsemove($n-1,$from,$via,$to)move(1,$from,$to,$via)move($n-1,$via,$to,$from)EndIfEndFuncmove(4,1,2,3)
$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 -> rightleft -> middleright -> middleleft -> rightmiddle -> leftmiddle -> rightleft -> rightleft -> middleright -> middleright -> leftmiddle -> leftright -> middleleft -> rightleft -> middleright -> middle
SUBmove(nASInteger,fromPegASInteger,toPegASInteger,viaPegASInteger)IFn>0THENmoven-1,fromPeg,viaPeg,toPegPRINT"Move disk from ";fromPeg;" to ";toPegmoven-1,viaPeg,toPeg,fromPegENDIFENDSUBmove4,1,2,3
GOSUBsHere's an example of implementing recursion in an old BASIC that only has global variables:
10DEPTH=4:REMSHOULDEQUALNUMBEROFDISKS20DIMN(DEPTH),F(DEPTH),T(DEPTH),V(DEPTH):REMSTACKPERPARAMETER30SP=0:REMSTACKPOINTER40N(SP)=4:REMSTARTWITH4DISCS50F(SP)=1:REMONPEG160T(SP)=2:REMMOVETOPEG270V(SP)=3:REMVIAPEG380GOSUB10090END99REM MOVE SUBROUTINE100IFN(SP)=0THENRETURN110OS=SP:REMSTORESTACKPOINTER120SP=SP+1:REMINCREMENTSTACKPOINTER130N(SP)=N(OS)-1:REMMOVEN-1DISCS140F(SP)=F(OS):REMFROMSTARTPEG150T(SP)=V(OS):REMTOVIAPEG160V(SP)=T(OS):REMVIATOPEG170GOSUB100180OS=SP-1:REMOSWILLHAVECHANGED190PRINT"MOVE DISC FROM";F(OS);"TO";T(OS)200N(SP)=N(OS)-1:REMMOVEN-1DISCS210F(SP)=V(OS):REMFROMVIAPEG220T(SP)=T(OS):REMTODESTPEG230V(SP)=F(OS):REMVIAFROMPEG240GOSUB100250SP=SP-1:REMRESTORESTACKPOINTERFORCALLER260RETURN
Very fast version in BASIC V2 on Commodore C-64
10DEFFNM3(X)=X-INT(X/3)*3:REMMODULO320N=4:GOSUB10030END99REMHANOI100:FORM=1TO2^N-1110::PRINTMID$(STR$(M),2);":",FNM3(MANDM-1)+1;"TO";FNM3((MORM-1)+1)+1130:NEXTM140RETURN
1: 1 TO 3 2: 1 TO 2 3: 3 TO 2 4: 1 TO 3 5: 2 TO 1 6: 2 TO 3 7: 1 TO 3 8: 1 TO 2 9: 3 TO 2 10: 3 TO 1 11: 2 TO 1 12: 3 TO 2 13: 1 TO 3 14: 1 TO 2 15: 3 TO 2
call move(4,1,2,3)print "Towers of Hanoi puzzle completed!"endsubroutine 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 ifend subroutine
Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Towers of Hanoi puzzle completed!
100 PROGRAM "Hanoi.bas"110 CALL HANOI(4,1,3,2)120 DEF HANOI(DISK,FRO,TO,WITH)130 IF DISK>0 THEN140 CALL HANOI(DISK-1,FRO,WITH,TO)150 PRINT "Move disk";DISK;"from";FRO;"to";TO160 CALL HANOI(DISK-1,WITH,TO,FRO)170 END IF180 END DEF
100CLS120LETD=4:REMSHOULDEQUALNUMBEROFDISKS130ARRAYN:ARRAYF:ARRAYT:ARRAYV:REMSTACKPERPARAMETER140LETS=0:REMSTACKPOINTER150LETN(S)=4:REMSTARTWITH4DISCS160LETF(S)=1:REMONPEG1170LETT(S)=2:REMMOVETOPEG2180LETV(S)=3:REMVIAPEG3190GOSUB220200END210REM MOVE SUBROUTINE220IFN(S)=0THENRETURN230LETO=S:REMSTORESTACKPOINTER240LETS=S+1:REMINCREMENTSTACKPOINTER250LETN(S)=N(O)-1:REMMOVEN-1DISCS260LETF(S)=F(O):REMFROMSTARTPEG270LETT(S)=V(O):REMTOVIAPEG280LETV(S)=T(O):REMVIATOPEG290GOSUB220300LETO=S-1:REMOWILLHAVECHANGED310PRINT"MOVE DISC FROM ";F(O);" TO ";T(O)320LETN(S)=N(O)-1:REMMOVEN-1DISCS330LETF(S)=V(O):REMFROMVIAPEG340LETT(S)=T(O):REMTODESTPEG350LETV(S)=F(O):REMVIAFROMPEG360GOSUB220370LETS=S-1:REMRESTORESTACKPOINTERFORCALLER380RETURN390END
MOVE DISC FROM 1 TO 3MOVE DISC FROM 1 TO 2MOVE DISC FROM 3 TO 2MOVE DISC FROM 1 TO 3MOVE DISC FROM 2 TO 1MOVE DISC FROM 2 TO 3MOVE DISC FROM 1 TO 3MOVE DISC FROM 1 TO 2MOVE DISC FROM 3 TO 2MOVE DISC FROM 3 TO 1MOVE DISC FROM 2 TO 1MOVE DISC FROM 3 TO 2MOVE DISC FROM 1 TO 3MOVE DISC FROM 1 TO 2MOVE DISC FROM 3 TO 2
@echo offsetlocal enabledelayedexpansion%==The main thing==%%==First param - Number of disks==%%==Second param - Start pole==%%==Third param - End pole==%%==Fourth param - Helper pole==%call:move 4 START END HELPERecho.pauseexit /b 0%==The "function"==%:movesetlocalsetn=%1setfrom=%2setto=%3setvia=%4if%n%gtr 0(set/ax=!n!-1call:move!x!%from%%via%%to%echo Move top disk from pole%from% to pole%to%.call:move!x!%via%%to%%from%)exit /b 0
Move top disk from pole START to pole HELPER.Move top disk from pole START to pole END.Move top disk from pole HELPER to pole END.Move top disk from pole START to pole HELPER.Move top disk from pole END to pole START.Move top disk from pole END to pole HELPER.Move top disk from pole START to pole HELPER.Move top disk from pole START to pole END.Move top disk from pole HELPER to pole END.Move top disk from pole HELPER to pole START.Move top disk from pole END to pole START.Move top disk from pole HELPER to pole END.Move top disk from pole START to pole HELPER.Move top disk from pole START to pole END.Move top disk from pole HELPER to pole END.Press any key to continue . . .
DIMDisc$(13),Size%(3)FORdisc%=1TO13Disc$(disc%)=STRING$(disc%," ")+STR$disc%+STRING$(disc%," ")IFdisc%>=10Disc$(disc%)=MID$(Disc$(disc%),2)Disc$(disc%)=CHR$17+CHR$(128+disc%-(disc%>7))+Disc$(disc%)+CHR$17+CHR$128NEXTdisc%MODE3OFFndiscs%=13FORn%=ndiscs%TO1STEP-1PROCput(n%,1)NEXTINPUTTAB(0,0)"Press Enter to start"dummy$PRINTTAB(0,0)SPC(20);PROChanoi(ndiscs%,1,2,3)VDU30ENDDEFPROChanoi(a%,b%,c%,d%)IFa%=0ENDPROCPROChanoi(a%-1,b%,d%,c%)PROCtake(a%,b%)PROCput(a%,c%)PROChanoi(a%-1,d%,c%,b%)ENDPROCDEFPROCput(disc%,peg%)PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))Disc$(disc%);Size%(peg%)=Size%(peg%)+1ENDPROCDEFPROCtake(disc%,peg%)Size%(peg%)=Size%(peg%)-1PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))STRING$(2*disc%+1," ");ENDPROC
get "libhdr"let start() be move(4, 1, 2, 3)and move(n, src, via, dest) be if n > 0 do $( move(n-1, src, dest, via) writef("Move disk from pole %N to pole %N*N", src, dest); move(n-1, via, src, dest)$)Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
This is loosely based on thePython sample. The number of disks is specified by the first integer on the stack (the initial character4 in the example below). If you want the program to prompt the user for that value, you can replace the4 with a& (the read integer command).
48*2+1>#v_:!#@_0" ksid evoM">:#,_$:8/:.v>8v8:<$#<+9-+*2%3\*3/3:,+55.+1%3:$_,#!>#:<:>/!#^_:0\:8/1-8vv,_$8%:3/1+.>0" gep ot"^^++3-%3\*2/3:%8\*<>:^:"from peg "0\*8-1<
Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 3 from peg 1 to peg 2Move disk 1 from peg 3 to peg 1Move disk 2 from peg 3 to peg 2Move disk 1 from peg 1 to peg 2Move disk 4 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 2 from peg 2 to peg 1Move disk 1 from peg 3 to peg 1Move disk 3 from peg 2 to peg 3Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3
Based on:APL
Move←{𝕩⊑⊸≤0?⟨⟩;𝕊n‿from‿to‿via:l←𝕊⟨n-1,from,via,to⟩r←𝕊⟨n-1,via,to,from⟩l∾(<from‿to)∾r}{"Move disk from pole "∾(•Fmt𝕨)∾" to pole "∾•Fmt𝕩}´˘>Move4‿1‿2‿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 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" ┘
( ( 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));Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2Move disk from pole 3 to pole 1Move disk from pole 2 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 2
[This implementation is recursive and usesa stack, consisting of frames that are 8bytes 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 moveThe 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<]
:import std/Combinator .:import std/Number .:import std/String .hanoi y [[[[=?2 empty go]]]]go [(4 --3 2 0) ++ str ++ (4 --3 0 1)] ((+6) - 1 - 0)str "Move " ++ disk ++ " from " ++ source ++ " to " ++ destination ++ "\n"disk number→string 3source number→string 2destination number→string 1
#include<stdio.h>voidmove(intn,intfrom,intvia,intto){if(n>1){move(n-1,from,to,via);printf("Move disk from pole %d to pole %d\n",from,to);move(n-1,via,from,to);}else{printf("Move disk from pole %d to pole %d\n",from,to);}}intmain(){move(4,1,2,3);return0;}
Animate it for fun:
#include<stdio.h>#include<stdlib.h>#include<unistd.h>typedefstruct{int*x,n;}tower;tower*new_tower(intcap){tower*t=calloc(1,sizeof(tower)+sizeof(int)*cap);t->x=(int*)(t+1);returnt;}tower*t[3];intheight;voidtext(inty,inti,intd,constchar*s){printf("\033[%d;%dH",height-y+1,(height+1)*(2*i+1)-d);while(d--)printf("%s",s);}voidadd_disk(inti,intd){t[i]->x[t[i]->n++]=d;text(t[i]->n,i,d,"==");usleep(100000);fflush(stdout);}intremove_disk(inti){intd=t[i]->x[--t[i]->n];text(t[i]->n+1,i,d," ");returnd;}voidmove(intn,intfrom,intto,intvia){if(!n)return;move(n-1,from,via,to);add_disk(to,remove_disk(from));move(n-1,via,to,from);}intmain(intc,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");return0;}
publicvoidmove(intn,intfrom,intto,intvia){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);}}
voidmove(intn,intfrom,intto,intvia){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);}}
100cls110print"Three disks":print120hanoi(3,1,2,3)130printchr$(10)"Four disks"chr$(10)140hanoi(4,1,2,3)150print:print"Towers of Hanoi puzzle completed!"160end170subhanoi(n,desde,hasta,via)180ifn>0then190hanoi(n-1,desde,via,hasta)200print"Move disk "n"from pole "desde"to pole "hasta210hanoi(n-1,via,hasta,desde)220endif230endsub
(defntowers-of-hanoi[nfromtovia](when(pos?n)(towers-of-hanoi(decn)fromviato)(printf"Move from %s to %s\n"fromto)(recur(decn)viatofrom)))
(defntowers-of-hanoi[nfromtovia](when(pos?n)(lazy-cat(towers-of-hanoi(decn)fromviato)(cons[from'->to](towers-of-hanoi(decn)viatofrom)))))
move = proc (n, from, via, to: int) po: stream := stream$primary_output() if n > 0 then move(n-1, from, to, via) stream$putl(po, "Move disk from pole " || int$unparse(from) || " to pole " || int$unparse(to)) move(n-1, via, from, to) endend movestart_up = proc () move(4, 1, 2, 3)end start_up
Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
>>SOURCEFREEIDENTIFICATIONDIVISION.PROGRAM-ID.towers-of-hanoi.PROCEDUREDIVISION. CALL"move-disk"USING4,1,2,3.END PROGRAMtowers-of-hanoi.IDENTIFICATIONDIVISION.PROGRAM-ID.move-diskRECURSIVE.DATA DIVISION.LINKAGESECTION.01 nPIC 9USAGECOMP.01 from-polePIC 9USAGECOMP.01 to-polePIC 9USAGECOMP.01 via-polePIC 9USAGECOMP.PROCEDUREDIVISIONUSINGn,from-pole,to-pole,via-pole. IFn>0SUBTRACT1FROMnCALL"move-disk"USINGCONTENTn,from-pole,via-pole,to-poleDISPLAY"Move disk from pole "from-pole" to pole "to-poleCALL"move-disk"USINGCONTENTn,via-pole,to-pole,from-pole END-IF.END PROGRAMmove-disk.
IDENTIFICATIONDIVISION.PROGRAM-ID.towers-of-hanoi.PROCEDUREDIVISION. CALL"move-disk"USING4,1,2,3.END PROGRAMtowers-of-hanoi.IDENTIFICATIONDIVISION.PROGRAM-ID.move-diskRECURSIVE.DATA DIVISION.LINKAGESECTION.01 nPIC 9USAGECOMP.01 from-polePIC 9USAGECOMP.01 to-polePIC 9USAGECOMP.01 via-polePIC 9USAGECOMP.PROCEDUREDIVISIONUSINGn,from-pole,to-pole,via-pole. IFn>0SUBTRACT1FROMnCALL"move-disk"USINGCONTENTn,from-pole,via-pole,to-poleADD1TOnDISPLAY"Move disk number "n" from pole "from-pole" to pole "to-poleSUBTRACT1FROMnCALL"move-disk"USINGCONTENTn,via-pole,to-pole,from-pole END-IF.END PROGRAMmove-disk.
Early versions of COBOL did not have recursion. There are no locally-scoped variables and the call of a procedure does not have to use a stack to save return state. Recursion would cause undefined results. It is therefore necessary to use an iterative algorithm. This solution is an adaptation ofKolar's Hanoi Tower algorithm no. 1.
IDENTIFICATIONDIVISION.PROGRAM-ID.ITERATIVE-TOWERS-OF-HANOI.AUTHOR.SORENROUG.DATE-WRITTEN.2019-06-28.ENVIRONMENTDIVISION.CONFIGURATIONSECTION.SOURCE-COMPUTER.LINUX.OBJECT-COMPUTER.KAYPRO4.INPUT-OUTPUTSECTION.FILE-CONTROL.DATADIVISION.WORKING-STORAGESECTION.77NUM-DISKSPIC 9VALUE4.77N1PIC 9COMP.77N2PIC 9COMP.77FROM-POLEPIC 9COMP.77TO-POLEPIC 9COMP.77VIA-POLEPIC 9COMP.77FP-TMPPIC 9COMP.77TO-TMPPIC 9COMP.77P-TMPPIC 9COMP.77TMP-PPIC 9COMP.77IPIC 9COMP.77DIVPIC 9COMP.01STACKNUMS.05NUMSETOCCURS3TIMES.10DNUMPIC 9COMP.01GAMESET.05POLESOCCURS3TIMES.10STACKOCCURS10TIMES.15POLEPIC 9USAGECOMP.PROCEDUREDIVISION.HANOI.DISPLAY"TOWERS OF HANOI PUZZLE WITH ",NUM-DISKS," DISKS.".ADDNUM-DISKS,1GIVINGN1.ADDNUM-DISKS,2GIVINGN2.MOVE1TODNUM(1).MOVEN1TODNUM(2),DNUM(3).MOVEN1TOPOLE(1,N1),POLE(2,N1),POLE(3,N1).MOVE1TOPOLE(1,N2).MOVE2TOPOLE(2,N2).MOVE3TOPOLE(3,N2).MOVE1TOI.PERFORMINIT-PUZZLEUNTILI=N1.MOVE1TOFROM-POLE.DIVIDE2INTONUM-DISKSGIVINGDIV.MULTIPLY2BYDIV.IFDIVNOT=NUM-DISKSPERFORMINITODDELSEPERFORMINITEVEN.PERFORMMOVE-DISKUNTILDNUM(3)NOT>1.DISPLAY"TOWERS OF HANOI PUZZLE COMPLETED!".STOPRUN.INIT-PUZZLE.MOVEITOPOLE(1,I).MOVE0TOPOLE(2,I),POLE(3,I).ADD1TOI.INITEVEN.MOVE2TOTO-POLE.MOVE3TOVIA-POLE.INITODD.MOVE3TOTO-POLE.MOVE2TOVIA-POLE.MOVE-DISK.MOVEDNUM(FROM-POLE)TOFP-TMP.MOVEPOLE(FROM-POLE,FP-TMP)TOI.DISPLAY"MOVE DISK FROM ",POLE(FROM-POLE,N2)," TO ",POLE(TO-POLE,N2).ADD1TODNUM(FROM-POLE).MOVEVIA-POLETOTMP-P.SUBTRACT1FROMDNUM(TO-POLE).MOVEDNUM(TO-POLE)TOTO-TMP.MOVEITOPOLE(TO-POLE,TO-TMP).DIVIDE2INTOIGIVINGDIV.MULTIPLY2BYDIV.IFINOT=DIVPERFORMMOVE-TO-VIAELSEPERFORMMOVE-FROM-VIA.MOVE-TO-VIA.MOVETO-POLETOVIA-POLE.MOVEDNUM(FROM-POLE)TOFP-TMP.MOVEDNUM(TMP-P)TOP-TMP.IFPOLE(FROM-POLE,FP-TMP)>POLE(TMP-P,P-TMP)PERFORMMOVE-FROM-TOELSEMOVETMP-PTOTO-POLE.MOVE-FROM-TO.MOVEFROM-POLETOTO-POLE.MOVETMP-PTOFROM-POLE.MOVEDNUM(FROM-POLE)TOFP-TMP.MOVEDNUM(TMP-P)TOP-TMP.MOVE-FROM-VIA.MOVEFROM-POLETOVIA-POLE.MOVETMP-PTOFROM-POLE.
hanoi=(ndisks, start_peg=1, end_peg=3) ->ifndisksstaging_peg=1+2+3-start_peg-end_peghanoi(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)
(defunmove(nfromtovia)(cond((=n1)(formatt"Move from ~A to ~A.~%"fromto))(t(move(-n1)fromviato)(formatt"Move from ~A to ~A.~%"fromto)(move(-n1)viatofrom))))
importstd.stdio;voidhanoi(inintn,incharfrom,incharto,incharvia){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);}}voidmain(){hanoi(3,'L','M','R');}
Move disk 1 from L to MMove disk 2 from L to RMove disk 1 from M to RMove disk 3 from L to MMove disk 1 from R to LMove disk 2 from R to MMove disk 1 from L to M
See:The shortest and "mysterious" TH algorithm
// Code found and then improved by Glenn C. Rhoads,// then some more by M. Kolar (2000).voidmain(instring[]args){importcore.stdc.stdio,std.conv,std.typetuple;immutablesize_tn=(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(immutablei;1..n+1)printf(" %d",i);"\n|\n|".puts;foreach(immutablesize_tx;1..(1<<n)){{immutablesize_ti1=x&(x-1);immutablesize_tfr=(i1+i1/3)&3;immutablesize_ti2=(x|(x-1))+1;immutablesize_tto=(i2+i2/3)&3;size_tj=1;for(size_tw=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(immutablesize_tk;TypeTuple!(0,1,2)){"\n|".printf;size_tj=1<<n;foreach_reverse(immutablesize_tw;1..n+1){j>>=1;if(j&p[k])printf(" %zd",w);}}'\n'.putchar;}}
| 3 2 1||| 3 2|| 1| 3| 2| 1| 3| 2 1||| 2 1| 3| 1| 2| 3| 1|| 3 2||| 3 2 1
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);}
The same as above, with optional static type annotations and styled according tohttp://www.dartlang.org/articles/style-guide/
main(){Stringsay(Stringfrom,Stringto)=>"$from --->$to";hanoi(intheight,inttoPole,intfromPole,intusePole){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);}
move 1 ---> 3move 1 ---> 2move 3 ---> 2move 1 ---> 3move 2 ---> 1move 2 ---> 3move 1 ---> 3
FromHere
[ # 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()
SeePascal.
proc move(byte n, src, via, dest) void: if n>0 then move(n-1, src, dest, via); writeln("Move disk from pole ",src," to pole ",dest); move(n-1, via, src, dest) ficorpproc nonrec main() void: move(4, 1, 2, 3) corpMove disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
func hanoi(n, a, b, c) { if n > 0 { hanoi(n - 1, a, c, b) print("Move disk from \(a) to \(c)") hanoi(n - 1, b, a, c) }} hanoi(4, "A", "B", "C")Move disk from A to BMove disk from A to CMove disk from B to CMove disk from A to BMove disk from C to AMove disk from C to BMove disk from A to BMove disk from A to CMove disk from B to CMove disk from B to AMove disk from C to AMove disk from B to CMove disk from A to BMove disk from A to CMove disk from B to C
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 {})proc hanoi n src dst aux . . if n >= 1 hanoi n - 1 src aux dst print "Move " & src & " to " & dst hanoi n - 1 aux dst src ..hanoi 5 1 2 3
The Wikipedia article on EDSAC says "recursive calls were forbidden", and this is true if the standard "Wheeler jump" is used. In the Wheeler jump, the caller (in effect) passes the return address to the subroutine, which uses that address to manufacture a "link order", i.e. a jump back to the caller. This link order is normally stored at a fixed location in the subroutine, so if the subroutine were to call itself then the original link order would be overwritten and lost. However, it is easy enough to make a subroutine save its link orders in a stack, so that it can be called recursively, as the Rosetta Code task requires.
The program has a maximum of 9 discs, so as to simplify the printout of the disc numbers. Discs are numbered 1, 2, 3, ... in increasing order of size. The program could be speeded up by shortening the messages, which at present take up most of the runtime.
[Towers of Hanoi task for Rosetta Code.][EDSAC program, Initial Orders 2.] T100K [load program at location 100 (arbitrary)] GK[Number of discs, in the address field] [0] P3F [<--- edit here, value 1..9][Letters to represent the rods] [1] LF [left] [2] CF [centre] [3] RF [right][Main routine. Enter with acc = 0] [4] T1F [1F := 0] [5] A5@ [initialize recursive subroutine] G104@ A@ [number of discs] T1F [pass to subroutines] A1@ [source rod] T4F [pass to subroutines] A3@ [target rod] T5F [pass to subroutines] [13] A13@ [call subroutine to write header ] G18@ [15] A15@ [call recursive subroutine to write moves ] G104@ ZF [stop][Subroutine to write a header][Input: 1F = number of discs (in the address field)] [4F = letter for starting rod] [5F = letter for ending rod][Output: None. 1F, 4F, 5F must be preserved.] [18] A3F [plant return link as usual] T35@ A1F [number of discs] L512F [shift 11 left to make output char] T39@ [plant in message] A4F [starting rod] T53@ [plant in message] A5F [ending rod] T58@ [plant in message] A36@ [O order for first char of message] E30@ [skip next order (code for 'O' is positive)] [29] A37@ [restore acc after test below] [30] U31@ [plant order to write next character] [31] OF [(planted) write next character] A2F [inc address in previous order] S37@ [finished yet?] G29@ [if not, loop back] [35] ZF [(planted) exit with acc = 0] [36] O38@ [O order for start of message] [37] O61@ [O order for exclusive end of message] [38] #F [39] PFK2048F!FDFIFSFCFSF!FFFRFOFMF!F [53] PF!FTFOF!F [58] PF@F&F [61][Subroutine to write a move of one disc.][Input: 1F = disc number 1..9 (in the address field)] [4F = letter for source rod] [5F = letter for target rod][Output: None. 1F, 4F, 5F must be preserved.][Condensed to save space; very similar to previous subroutine.] [61] A3FT78@A1FL512FT88@ A4FT96@A5FT101@A79@E73@ [72] A80@ [73] U74@ [74] OFA2FS80@G72@ [78] ZF [(planted) exit with acc = 0] [79] O81@ [80] O104@ [81] K2048FMFOFVFEF!F#F [88] PFK2048F!FFFRFOFMF!F [96] PF!FTFOF!F [101] PF@F&F [104][Recursive subroutine to move discs 1..n, where 1 <= n <= 9.][Call with n = 0 to initialize.][Input: 1F = n (in the address field)] [4F = letter for source rod] [5F = letter for target rod][Output: None. 1F, 4F, 5F must be preserved.] [104] A3F [plant link as usual ] T167@[The link will be saved in a stack if recursive calls are required.] S1F [load -n] G115@ [jump if n > 0][Here if n = 0. Initialize; no recursive calls.] A169@ [initialize push order to start of stack] T122@ A1@ [find total of the codes for the rod letters] A2@ A3@ T168@ [store for future use] E167@ [jump to link][Here with acc = -n in address field] [115] A2F [add 1] G120@ [jump if n > 1][Here if n = 1. Just write the move; no recursive calls.] [117] A117@ [call write subroutine] G61@ E167@ [jump to link][Here if n > 1. Recursive calls are required.] [120] TF [clear acc] A167@ [load link order] [122] TF [(planted) push link order onto stack] A122@ [inc address in previous order] A2F T122@[First recursive call. Modify parameters 1F and 5F; 4F stays the same] A1F [load n] S2F [make n - 1] T1F [pass as parameter] A168@ [get 3rd rod, neither source nor target] S4F S5F T5F [133] A133@ [recursive call] G104@[Returned, restore parameters] A1F A2F T1F A168@ S4F S5F T5F[Write move of largest disc] [142] A142@ G61@[Second recursive call. Modify parameters 1F and 4F; 5F stays the same][Condensed to save space; very similar to first recursice call.] A1FS2FT1FA168@S4FS5FT4F [151] A151@G104@A1FA2FT1FA168@S4FS5FT4F[Pop return link off stack] A122@ [dec address in push order] S2F U122@ A170@ [make A order with same address] T165@ [plant in code] [165] AF [(planted) pop return link from stack] T167@ [plant in code] [167] ZF [(planted) return to caller][Constants] [168] PF [(planted) sum of letters for rods] [169] T171@ [T order for start of stack] [170] MF [add to T order to make A order, same address][Stack: placed at end of program, grows into free space.] [171] E4Z [define entry point] PF [acc = 0 on entry][end]
3 DISCS FROM L TO RMOVE 1 FROM L TO RMOVE 2 FROM L TO CMOVE 1 FROM R TO CMOVE 3 FROM L TO RMOVE 1 FROM C TO LMOVE 2 FROM C TO RMOVE 1 FROM L TO R
classAPPLICATIONcreatemakefeature{NONE}-- Initializationmakedomove(4,"A","B","C")endfeature-- Towers of Hanoimove(n:INTEGER;frm,to,via:STRING)requiren>0doifn=1thenprint("Move disk from pole "+frm+" to pole "+to+"%N")elsemove(n-1,frm,via,to)move(1,frm,to,via)move(n-1,via,to,frm)endendend
open monad io:::IO//Functional approachhanoi 0 _ _ _ = []hanoi n a b c = hanoi (n - 1) a c b ++ [(a,b)] ++ hanoi (n - 1) c b ahanoiIO n = mapM_ f $ hanoi n 1 2 3 where f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y//Imperative approach using IO monadhanoiM 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
ELENA 4.x :
move = (n,from,to,via){ if (n == 1) { console.printLine("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) }};defmoduleRCdodefhanoi(n)when0<nandn<10,do:hanoi(n,1,2,3)defphanoi(1,f,_,t),do:move(f,t)defphanoi(n,f,u,t)dohanoi(n-1,f,t,u)move(f,t)hanoi(n-1,u,f,t)enddefpmove(f,t),do:IO.puts"Move disk from#{f} to#{t}"endRC.hanoi(3)
Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3
(defunmove(nfromtovia)(if(=n1)(message"Move from %S to %S"fromto)(move(-n1)fromviato)(message"Move from %S to %S"fromto)(move(-n1)viatofrom)))
fun move = void by int n, int from, int to, int via if n == 1 writeLine("Move disk from pole " + from + " to pole " + to) return end move(n - 1, from, via, to) move(1, from, to, via) move(n - 1, via, to, from)endmove(3, 1, 2, 3)Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2
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).
!-----------------------------------------------------------! HANOI.R : solve tower of Hanoi puzzle using a recursive ! modified algorithm.!-----------------------------------------------------------PROGRAM HANOI!$INTEGER!VAR I,J,MOSSE,NUMBERPROCEDURE 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 PROCEDUREPROCEDURE 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 IFEND PROCEDUREBEGIN 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 MOVEEND PROGRAM--- TOWER OF HANOI ---Number of disks ? 3For 3 disks the total number of moves is 7I move a disk from Left to RightI move a disk from Left to CenterI move a disk from Right to CenterI move a disk from Left to RightI move a disk from Center to LeftI move a disk from Center to RightI move a disk from Left to Right
With the names HANOI and SHOWHANOI bound to the following lambdas in the Excel worksheet Name Manager:
(SeeLAMBDA: The ultimate Excel worksheet function)
SHOWHANOI=LAMBDA(n,FILTERP(LAMBDA(x,""<>x))(HANOI(n)("left")("right")("mid")))HANOI=LAMBDA(n,LAMBDA(l,LAMBDA(r,LAMBDA(m,IF(0=n,"",LET(next,n-1,APPEND(APPEND(HANOI(next)(l)(m)(r))(CONCAT(l," -> ",r)))(HANOI(next)(m)(r)(l))))))))
And assuming that these generic lambdas are also bound to the following names in Name Manager:
APPEND=LAMBDA(xs,LAMBDA(ys,LET(nx,ROWS(xs),rowIndexes,SEQUENCE(nx+ROWS(ys)),colIndexes,SEQUENCE(1,MAX(COLUMNS(xs),COLUMNS(ys))),IF(rowIndexes<=nx,INDEX(xs,rowIndexes,colIndexes),INDEX(ys,rowIndexes-nx,colIndexes)))))FILTERP=LAMBDA(p,LAMBDA(xs,FILTER(xs,p(xs))))
In the output below, the expression in B2 defines an array of strings which additionally populate the following cells.
| fx | =SHOWHANOI(A2) | ||
|---|---|---|---|
| A | B | ||
| 1 | Disks | Steps | |
| 2 | 3 | left -> right | |
| 3 | left -> mid | ||
| 4 | right -> mid | ||
| 5 | left -> right | ||
| 6 | mid -> left | ||
| 7 | mid -> right | ||
| 8 | left -> right | ||
# (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)
#lightletrechanoinumstartfinish=matchnumwith|0->[]|_->lettemp=(6-start-finish)(hanoi(num-1)starttemp)@[start,finish]@(hanoi(num-1)tempfinish)[<EntryPoint>]letmainargs=(hanoi412)|>List.iter(funpair->matchpairwith|a,b->printf"Move disc from %A to %A\n"ab)0
USING:formattingkernellocalsmath;IN:rosettacode.hanoi:move(fromto--)"%d->%d\n"printf;::hanoi(nfromtoother--)n0>[n1-fromothertohanoifromtomoven1-othertofromhanoi]when;
In the REPL:
( scratchpad ) 3 1 3 2 hanoi1->31->23->21->32->12->31->3
["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;!%%%Func Hanoi( n, f, t, v ) = if n = 0 then !'';else Hanoi(n - 1, f, v, t); !f;!' -> ';!t;!', '; Hanoi(n - 1, v, t, f) fi.
1 -> 3, 1 -> 2, 3 -> 2, 1 -> 3, 2 -> 1, 2 -> 3, 1 -> 3, 1 -> 2, 3 -> 2, 3 -> 1, 2 -> 1, 3 -> 2, 1 -> 3, 1 -> 2, 3 -> 2,
01.10 S N=4;S S=1;S V=2;S T=301.20 D 201.30 Q02.02 S N(D)=N(D)-1;I (N(D)),2.2,2.0402.04 S D=D+102.06 S N(D)=N(D-1);S S(D)=S(D-1)02.08 S T(D)=V(D-1);S V(D)=T(D-1)02.10 D 202.12 S D=D-102.14 D 302.16 S A=S(D);S S(D)=V(D);S V(D)=A02.18 G 2.0202.20 D 303.10 T %1,"MOVE DISK FROM POLE",S(D)03.20 T " TO POLE",T(D),!
MOVE DISK FROM POLE= 1 TO POLE= 2MOVE DISK FROM POLE= 1 TO POLE= 3MOVE DISK FROM POLE= 2 TO POLE= 3MOVE DISK FROM POLE= 1 TO POLE= 2MOVE DISK FROM POLE= 3 TO POLE= 1MOVE DISK FROM POLE= 3 TO POLE= 2MOVE DISK FROM POLE= 1 TO POLE= 2MOVE DISK FROM POLE= 1 TO POLE= 3MOVE DISK FROM POLE= 2 TO POLE= 3MOVE DISK FROM POLE= 2 TO POLE= 1MOVE DISK FROM POLE= 3 TO POLE= 1MOVE DISK FROM POLE= 2 TO POLE= 3MOVE DISK FROM POLE= 1 TO POLE= 2MOVE DISK FROM POLE= 1 TO POLE= 3MOVE DISK FROM POLE= 2 TO POLE= 3
With locals:
CREATEpeg1,"left"CREATEpeg2,"middle"CREATEpeg3,"right":.$COUNTTYPE;:MOVE-DISKLOCALS|viatofromn|n1=IFCR."Move disk from"from.$."to"to.$ELSEn1-fromviatoRECURSE1fromtoviaRECURSEn1-viatofromRECURSETHEN;
Without locals, executable pegs:
:left."left";:right."right";:middle."middle";:move-disk( v t f n -- v t f )dup0=ifdropexitthen1->RrotswapR@( t v f n-1 )recurserotswap2dupcr."Move disk from"execute." to"executeswaprotR>( f t v n-1 )recurseswaprot;:hanoi( n -- )1max>R[']right[']middle[']leftR>move-diskdropdropdrop;
PROGRAMTOWERCALLMove(4,1,2,3)CONTAINS RECURSIVE SUBROUTINEMove(ndisks,from,to,via)INTEGER,INTENT(IN)::ndisks,from,to,viaIF(ndisks==1)THEN WRITE(*,"(A,I1,A,I1)")"Move disk from pole ",from," to pole ",toELSE CALLMove(ndisks-1,from,via,to)CALLMove(1,from,to,via)CALLMove(ndisks-1,via,to,from)END IF END SUBROUTINEMoveEND PROGRAMTOWER
Template:More informative version
!This is a nice alternative to the usual recursive Hanoi solutions. It runs about 10x! faster than a well crafted recursive solution for 30 disks.SUBROUTINEolives(Numdisk)!> This is an implementation of "Olive's Algorithm"!! The “simpler” algorithm where the smallest disk moves circularly every second!! move is attributed to Raoul Olive, the nephew of Edouard Lucas, the inventor of the!! Towers of Hanoi puzzle. We alternately move disk one in it's established direction!! Then we move the one of the 'non-one' disks, depending on the legality of the move.!! In this implementation, I use a small array of the stack entities. This allows us!! to easily find the stack where the disk to be moved resides.USEdata_defsIMPLICIT NONE!! PARAMETER definitions!INTEGER(int32),PARAMETER::bigm=maxpos*3!! Dummy arguments!INTEGER(int32)::NumdiskINTENT(IN)Numdisk!! Local variables!TYPE(stack),POINTER::a,b,c,on_now!< on_now is where disk 1 isTYPE(stack),TARGET,DIMENSION(3)::abc!< The three stack are put in an array for identification i.e. abc(1)%stack_id = 1INTEGER::direction!< Direction of disk1, negative is counter clockwise, positive = clockwiseINTEGER(int32)::i,jDATA(abc(i)%height,i=1,3)/3*0/DATA(abc(i)%stack_id,i=1,3)/1,2,3/DATA((abc(i)%disks(j),i=1,3),j=1,maxpos)/bigm*0/! Code starts here!! Move numdisks from A to C using B as intermediate!a=>abc(1)b=>abc(2)c=>abc(3)on_now=>a!< Point to the starting polea%height=Numdisk!< A = the starting pole!last_move=-1!a%disks=[(Numdisk+1-j,j=1,Numdisk)]IF(btest(Numdisk,0))THEN!< First move rule always involves disk 1, test odd/even for first moveCALLmove(a,c)direction=-1! Counter clockwiseon_now=>cELSE CALLmove(a,b)direction=1! Clockwiseon_now=>bEND IF!DO WHILE(c%height/=Numdisk)!SELECT CASE(on_now%stack_id)!< Depending where disk one is, make a legal moveCASE(1)!< One is on stack 1 i.e. a so we can only make a legal move in between b and cIF(legal(b,c))THEN CALLmove(b,c)ELSE CALLmove(c,b)END IF CASE(2)! Disk one on stack 2 i.e. "b"IF(legal(a,c))THEN CALLmove(a,c)ELSE CALLmove(c,a)END IF CASE(3)! Disk one on stack 3 i.e. "c"IF(legal(a,b))THEN CALLmove(a,b)ELSE CALLmove(b,a)END IF END SELECT!< Now move disk 1 in the direction it was headingi=on_now%stack_id+direction!< Increment the stack a->b->c->a or vice versa Decrement the stack c->b->a->c!< Note that here we use the stack_id to figure out which disk destination to use. As we increment or decrement the stack counter!! we reset it to the correct disk when it is outside the 1..3 range. It is set so as to maintain the correct disk direction.SELECT CASE(i)CASE(0)i=3CASE(1:3)CASE(4)i=1END SELECT CALLmove(on_now,abc(i))on_now=>abc(i)END DO PRINT'(*(i0,2x))',(c%disks(i),i=1,Numdisk)! Print final disk configurationon_now=>null()!RETURN END SUBROUTINEolivesSUBROUTINEMove(Donor,Receiver)USEData_defsIMPLICIT NONE! Dummy arguments!TYPE(stack)::Donor,ReceiverINTENT(INOUT)Donor,Receiver! Code starts here!$GCC$ attributes INLINE :: MOVE!! Code starts herelast_move=Receiver%Stack_idReceiver%Height=Receiver%Height+1! make slot in receiverReceiver%Disks(Receiver%Height)=Donor%Disks(Donor%Height)!Move the diskDonor%Disks(Donor%Height)=0! Black it outDonor%Height=Donor%Height-1! Decrement the donor heightRETURN END SUBROUTINEMoveModuledata_defsIMPLICIT NONE!! PARAMETER definitions!INTEGER,PARAMETER::int32=selected_int_kind(8),&&int64=selected_int_kind(16)INTEGER(int32),PARAMETER::maxpos=40! Maximum possible disks without a huge blowout!! Derived Type definitions!TYPE::stackINTEGER(int32)::stack_idINTEGER(int32)::heightINTEGER(int32),DIMENSION(maxpos)::disksEND TYPEstack!! Local variables!INTEGER::last_move! Holds the destination of the last moveend moduledata_defs
' FB 1.05.0 Win64Submove(nAsInteger,fromAsInteger,to_AsInteger,viaAsInteger)Ifn>0Thenmove(n-1,from,via,to_)Print"Move disk";n;" from pole";from;" to pole";to_move(n-1,via,to_,from)EndIfEndSubPrint"Three disks":Printmove3,1,2,3PrintPrint"Four disks":Printmove4,1,2,3Print"Press any key to quit"Sleep
Three disksMove disk 1 from pole 1 to pole 2Move disk 2 from pole 1 to pole 3Move disk 1 from pole 2 to pole 3Move disk 3 from pole 1 to pole 2Move disk 1 from pole 3 to pole 1Move disk 2 from pole 3 to pole 2Move disk 1 from pole 1 to pole 2Four disksMove disk 1 from pole 1 to pole 3Move disk 2 from pole 1 to pole 2Move disk 1 from pole 3 to pole 2Move disk 3 from pole 1 to pole 3Move disk 1 from pole 2 to pole 1Move disk 2 from pole 2 to pole 3Move disk 1 from pole 1 to pole 3Move disk 4 from pole 1 to pole 2Move disk 1 from pole 3 to pole 2Move disk 2 from pole 3 to pole 1Move disk 1 from pole 2 to pole 1Move disk 3 from pole 3 to pole 2Move disk 1 from pole 1 to pole 3Move disk 2 from pole 1 to pole 2Move disk 1 from pole 3 to pole 2
/** Set up the recursive call for n disks */hanoi[n] := hanoi[n, 1, 3, 2]/** The recursive call. */hanoi[n, source, target, aux] :={ if n > 0 { hanoi[n-1, source, aux, target] println["Move from $source to $target"] hanoi[n-1, aux, target, source] }}hanoi[7]window 1, @"Towers of Hanoi", ( 0, 0, 300, 300 )void local fn Move( n as long, fromPeg as long, toPeg as long, viaPeg as long ) if n > 0 fn Move( n-1, fromPeg, viaPeg, toPeg ) print "Move disk from "; fromPeg; " to "; toPeg fn Move( n-1, viaPeg, toPeg, fromPeg ) end ifend fnfn Move( 4, 1, 2, 3 )printprint "Towers of Hanoi puzzle solved."HandleEvents
Output:
Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Towers of Hanoi puzzle solved.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in itswebsite.
Inthis page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Test case
PublicSubMain()Print"Three disks\n"move_(3,1,2,3)PrintPrint"Four disks\n"move_(4,1,2,3)EndPublicSubmove_(nAsInteger,fromAsInteger,toAsInteger,viaAsInteger)Ifn>0Thenmove_(n-1,from,via,to)Print"Move disk ";n;" from pole ";from;" to pole ";tomove_(n-1,via,to,from)EndIfEndSub
Same as FreeBASIC entry.
Hanoi:=function(n)localmove;move:=function(n,a,b,c)# from, through, toifn=1thenPrint(a," -> ",c,"\n");elsemove(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 -> CHanoi(2);# A -> B# A -> C# B -> CHanoi(3);# A -> C# A -> B# C -> B# A -> C# B -> A# B -> C# A -> C
packagemainimport"fmt"// a towers of hanoi solver just has one method, playtypesolverinterface{play(int)}funcmain(){vartsolver// declare variable of solver typet=new(towers)// type towers must satisfy solver interfacet.play(4)}// towers is example of type satisfying solver interfacetypetowersstruct{// 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 typefunc(t*towers)play(nint){// drive recursive solution, per task descriptiont.moveN(n,1,2,3)}// recursive algorithmfunc(t*towers)moveN(n,from,to,viaint){ifn>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,toint){fmt.Println("move disk from rod",from,"to rod",to)}
In other words:
packagemainimport"fmt"funcmain(){move(3,"A","B","C")}funcmove(nuint64,a,b,cstring){ifn>0{move(n-1,a,c,b)fmt.Println("Move disk from "+a+" to "+c)move(n-1,b,a,c)}}
{:q;.@.@<@@\)>q\++}:at;{\.@\}:over;{1 [" -> "] at puts}:disp;{ . 0> { over over \ ~[\]+ \( move \ .disp \ over over \ )\~\[@] \( move } *;;}:move;[1 2 3] 3 move1 -> 31 -> 23 -> 21 -> 32 -> 12 -> 31 -> 3
Unlike most solutions here this solution manipulates more-or-less actual stacks of more-or-less actual rings.
deftail={list,n->defm=list.size();list.subList([m-n,0].max(),m)}finalSTACK=[A:[],B:[],C:[]].asImmutable()defreport={it->}defcheck={it->}defmoveRing={from,to->to<<from.pop();report();check(to)}defmoveStackmoveStack={from,to,using=STACK.values().find{!(it.is(from)||it.is(to))}->if(!from)returndefn=from.size()moveStack(tail(from,n-1),using,to)moveRing(from,to)moveStack(tail(using,n-1),to,from)}
Test program:
enumRing{S('°'),M('o'),L('O'),XL('( )');privatesymprivateRing(sym){this.sym=sym}StringtoString(){sym}}report={STACK.each{k,v->println"${k}: ${v}"};println()}check={to->assertto==([]+to).sort().reverse()}Ring.values().reverseEach{STACK.A<<it}report()check(STACK.A)moveStack(STACK.A,STACK.C)
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, °]
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)]hanoi0___=[]hanoinabc=hanoi(n-1)acb++[(a,b)]++hanoi(n-1)cba
You can also do the above with one tail-recursion call:
hanoi::Integer->a->a->a->[(a,a)]hanoinabc=hanoiToListnabc[]wherehanoiToList0___l=lhanoiToListnabcl=hanoiToList(n-1)acb((a,b):hanoiToList(n-1)cbal)
One can use this function to produce output, just like the other programs:
hanoiIOn=mapM_f$hanoin123wheref(x,y)=putStrLn$"Move "++showx++" to "++showy
or, instead, one can of course also program imperatively, using the IO monad directly:
hanoiM::Integer->IO()hanoiMn=hanoiM'n123wherehanoiM'0___=return()hanoiM'nabc=dohanoiM'(n-1)acbputStrLn$"Move "++showa++" to "++showbhanoiM'(n-1)cba
or, defining it as a monoid, and adding some output:
-------------------------- HANOI -------------------------hanoi::Int->String->String->String->[(String,String)]hanoi0___=memptyhanoinlrm=hanoi(n-1)lmr<>[(l,r)]<>hanoi(n-1)mrl--------------------------- TEST -------------------------main::IO()main=putStrLn$showHanoi5------------------------- DISPLAY ------------------------showHanoi::Int->StringshowHanoin=unlines$fmap(\(from,to)->concat[justifyRight5' 'from," -> ",to])(hanoin"left""right""mid")justifyRight::Int->Char->String->StringjustifyRightnc=(drop.length)<*>(replicatenc<>)
left -> right left -> midright -> mid left -> right mid -> left mid -> right left -> right left -> midright -> midright -> left mid -> leftright -> mid left -> right left -> midright -> mid left -> right mid -> left mid -> right left -> right mid -> leftright -> midright -> left mid -> left mid -> right left -> right left -> midright -> mid left -> right mid -> left mid -> right left -> right
U0 Move(U8 n, U8 from, U8 to, U8 via) { if (n > 0) { Move(n - 1, from, via, to); Print("Move disk from pole %d to pole %d\n", from, to); Move(n - 1, via, to, from); }}Move(4, 1, 2, 3);The following is based on a solution in the Unicon book.
proceduremain(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 belowprocedurehanoi(n,needle1,needle2)#: solve towers of hanoi by moving n disks from needle 1 to needle2 via otherlocalothern:=integer(0<n)|runerr(n,101)# 1 ensure integer (this also ensures it's positive too)/needle1:=1# 2 default/needle2:=2# 3 defaultifn=1thenwrite("Move disk from ",needle1," to ",needle2)else{other:=6-needle1-needle2# clever but somewhat un-iconish way to find otherhanoi(n-1,needle1,other)write("Move disk from ",needle1," to ",needle2)hanoi(n-1,other,needle2)}returnend
%begin %routine do hanoi(%integer n, f, t, u) do hanoi(n - 1, f, u, t) %if n >= 2 print string("Move disk from ".itos(f,0)." to ".itos(t,0).to string(nl)) do hanoi(n - 1, u, t, f) %if n >= 2 %end do hanoi(4, 1, 2, 3) print string("Towers of Hanoi puzzle completed!".to string(nl))%end %of %programMove disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Towers of Hanoi puzzle completed!
Hanoi is a room.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.
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)))
=method(n,f,u,t,if(n<2,"#{f} -->#{t}"println,H(n-1,f,t,u)"#{f} -->#{t}"printlnH(n-1,u,f,t)))hanoi=method(n,H(n,1,2,3))
Solutions
H=:i.@,&2`(({&021,02,{&102)@$:@<:)@.*NB. tacit using anonymous recursion
H302012102121020
The result is a 2-column table; a rowi,j is interpreted as: move a disk (the top disk) from pegi to peg j .Or, using explicit rather than implicit code:
H1=:monaddefineNB. explicit equivalent of Hif.ydo.({&021,02,{&102)H1y-1else.i.02end.)
The usage here is the same:
H1 20 10 21 2
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):
hanoi=:monaddefinemoves=.Hydisks=.$~`((],[,])$:@<:)@.*y('move disk ';' from peg ';' to peg ');@,."1":&.>disks,.1+moves)
hanoi3movedisk1frompeg1topeg3movedisk2frompeg1topeg2movedisk1frompeg3topeg2movedisk3frompeg1topeg3movedisk1frompeg2topeg1movedisk2frompeg2topeg3movedisk1frompeg1topeg3
publicvoidmove(intn,intfrom,intto,intvia){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);}}
Where n is the number of disks to move and from, to, and via are the poles.
move(3,1,2,3);
Movediskfrompole1topole2Movediskfrompole1topole3Movediskfrompole2topole3Movediskfrompole1topole2Movediskfrompole3topole1Movediskfrompole3topole2Movediskfrompole1topole2
functionmove(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");
Or, as a functional expression, rather than a statement with side effects:
(function(){// hanoi :: Int -> String -> String -> String -> [[String, String]]functionhanoi(n,a,b,c){returnn?hanoi(n-1,a,c,b).concat([[a,b]]).concat(hanoi(n-1,c,b,a)):[];}returnhanoi(3,'left','right','mid').map(function(d){returnd[0]+' -> '+d[1];});})();
["left -> right","left -> mid","right -> mid","left -> right","mid -> left","mid -> right","left -> right"]
(()=>{"use strict";// ----------------- TOWERS OF HANOI -----------------// hanoi :: Int -> String -> String ->// String -> [[String, String]]consthanoi=n=>(a,b,c)=>{constgo=hanoi(n-1);returnn?[...go(a,c,b),[a,b],...go(c,b,a)]:[];};// ---------------------- TEST -----------------------returnhanoi(3)("left","right","mid").map(d=>`${d[0]} ->${d[1]}`).join("\n");})();
left -> rightleft -> midright -> midleft -> rightmid -> leftmid -> rightleft -> right
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.
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:
The truth of (b) follows from the fact that the algorithm emits an instruction of what to do when moving a single disk.
# n is the number of disks to move from From to Todef 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;
Example:
move(5; "A"; "B"; "C")
From Javascript ES5 entry.
/* Towers of Hanoi, in Jsish */functionmove(n,a,b,c){if(n>0){move(n-1,a,c,b);puts("Move disk from "+a+" to "+c);move(n-1,b,a,c);}}if(Interp.conf('unitTest'))move(4,"A","B","C");/*=!EXPECTSTART!=Move disk from A to BMove disk from A to CMove disk from B to CMove disk from A to BMove disk from C to AMove disk from C to BMove disk from A to BMove disk from A to CMove disk from B to CMove disk from B to AMove disk from C to AMove disk from B to CMove disk from A to BMove disk from A to CMove disk from B to C=!EXPECTEND!=*/
prompt$ jsish -u towersOfHanoi.jsi[PASS] towersOfHanoi.jsi
functionsolve(n::Integer,from::Integer,to::Integer,via::Integer)ifn==1println("Move disk from$from to$to")elsesolve(n-1,from,via,to)solve(1,from,to,via)solve(n-1,via,to,from)endendsolve(4,1,2,3)
Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2
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->32:1->21:3->23:1->31:2->12:2->31:1->34:1->21:3->22:3->11:2->13:3->21:1->32:1->21:3->2
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.
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];s1213121412131211_{*1+&|x}'a:(2_vs!_2^4)121312141213121
include ..\Utilitys.tlhy:moveDisc %B !B %C !C %A !A %n !n { n A C B } $n [ $n 1 - $A $B $C moveDisc ( "Move disc " $n " from pole " $A " to pole " $C ) lprint nl $n 1 - $B $C $A moveDisc ] if; { Move disc 3 from pole 1 to pole 3, with pole 2 as spare }3 1 3 2 moveDisc" " inputMove disc 1 from pole 1 to pole 3Move disc 2 from pole 1 to pole 2Move disc 1 from pole 3 to pole 2Move disc 3 from pole 1 to pole 3Move disc 1 from pole 2 to pole 1Move disc 2 from pole 2 to pole 3Move disc 1 from pole 1 to pole 3
// version 1.1.0classHanoi(disks:Int){privatevarmoves=0init{println("Towers of Hanoi with $disks disks:\n")move(disks,'L','C','R')println("\nCompleted in $moves moves\n")}privatefunmove(n:Int,from:Char,to:Char,via:Char){if(n>0){move(n-1,from,via,to)moves++println("Move disk $n from $from to $to")move(n-1,via,to,from)}}}funmain(args:Array<String>){Hanoi(3)Hanoi(4)}
Towers of Hanoi with 3 disks:Move disk 1 from L to CMove disk 2 from L to RMove disk 1 from C to RMove disk 3 from L to CMove disk 1 from R to LMove disk 2 from R to CMove disk 1 from L to CCompleted in 7 movesTowers of Hanoi with 4 disks:Move disk 1 from L to RMove disk 2 from L to CMove disk 1 from R to CMove disk 3 from L to RMove disk 1 from C to LMove disk 2 from C to RMove disk 1 from L to RMove disk 4 from L to CMove disk 1 from R to CMove disk 2 from R to LMove disk 1 from C to LMove disk 3 from R to CMove disk 1 from L to RMove disk 2 from L to CMove disk 1 from R to CCompleted in 15 moves
PSEUDO-CODE:hanoidisksfromAtoBviaCifnodisksthenstopelsehanoiupperdisksfromAtoCviaBmovelowerdiskfromAtoBhanoiupperdisksfromCtoBviaACODE:{defhanoi{lambda{:disks:a:b:c}{if{A.empty?:disks}thenelse{hanoi{A.rest:disks}:a:c:b}{div>move{A.first:disks}from:ato:b}{hanoi{A.rest:disks}:c:b:a}}}}->hanoi{hanoi{A.new==========}ABC}->>move=fromAtoC>move==fromAtoB>move=fromCtoB>move===fromAtoC>move=fromBtoA>move==fromBtoC>move=fromAtoC>move====fromAtoB>move=fromCtoB>move==fromCtoA>move=fromBtoA>move===fromCtoB>move=fromAtoC>move==fromAtoB>move=fromCtoB
#!/usr/bin/lasso9definetowermove(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")
Called from command line:
./towers
Move disk from A to CMove disk from A to BMove disk from C to BMove disk from A to CMove disk from B to AMove disk from B to CMove disk from A to C
Called from command line:
./towers4
Move disk from A to BMove disk from A to CMove disk from B to CMove disk from A to BMove disk from C to AMove disk from C to BMove disk from A to BMove disk from A to CMove disk from B to CMove disk from B to AMove disk from C to AMove disk from B to CMove disk from A to BMove disk from A to CMove disk from B to C
This looks much better with a GUI interface.
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
on hanoi (n, a, b, c) if n > 0 then hanoi(n-1, a, c, b) put "Move disk from" && a && "to" && c hanoi(n-1, b, a, c) end ifend
hanoi(3, "A", "B", "C")-- "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"
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 :fromendmove 4 "left "middle "right
:-object(hanoi). :-public(run/1). :-mode(run(+integer), one). :-info(run/1, [ commentis'Solves the towers of Hanoi problem for the specified number of disks.', argnamesis ['Disks']]). run(Disks):- move(Disks, left, middle, right). move(1,Left,_,Right):-!, report(Left,Right). move(Disks,Left,Aux,Right):-Disks2isDisks-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.
HAI 1.2 HOW IZ I HANOI YR N AN YR SRC AN YR DST AN YR VIA BTW VISIBLE SMOOSH "HANOI N=" N " SRC=" SRC " DST=" DST " VIA=" VIA MKAY BOTH SAEM N AN 0, O RLY? YA RLY BTW VISIBLE "Done." GTFO NO WAI I HAS A LOWER ITZ DIFF OF N AN 1 I IZ HANOI YR LOWER AN YR SRC AN YR VIA AN YR DST MKAY VISIBLE SMOOSH "Move disc " N " from " SRC " to " DST MKAY I IZ HANOI YR LOWER AN YR VIA AN YR DST AN YR SRC MKAY OICIF U SAY SO I IZ HANOI YR 4 AN YR 1 AN YR 2 AN YR 3 MKAY KTHXBYE
functionmove(n,src,dst,via)ifn>0thenmove(n-1,src,via,dst)print(src,'to',dst)move(n-1,via,dst,src)endendmove(4,1,2,3)
Template:More informative version
functionmove(n,src,via,dst)ifn>0thenmove(n-1,src,dst,via)print('Disk ',n,' from ',src,'to',dst)move(n-1,via,src,dst)endendmove(4,1,2,3)
#!/usr/bin/env luajitlocalfunctionprintf(fmt,...)io.write(string.format(fmt,...))endlocalruns=0localfunctionmove(tower,from,to)if#tower[from]==0or(#tower[to]>0andtower[from][#tower[from]]>tower[to][#tower[to]])thento,from=from,toendif#tower[from]>0thentower[to][#tower[to]+1]=tower[from][#tower[from]]tower[from][#tower[from]]=nilio.write(tower[to][#tower[to]],":",from,"→",to," ")endendlocalfunctionhanoi(n)localsrc,dst,via={},{},{}localtower={src,dst,via}fori=1,ndosrc[i]=n-i+1endlocalone,nxt,lstifn%2==1then-- oddone,nxt,lst=1,2,3elseone,nxt,lst=1,3,2end--repeat::loop::move(tower,one,nxt)if#dst==nthenreturnendmove(tower,one,lst)one,nxt,lst=nxt,lst,onegotoloop--until falseendlocalnum=arg[1]andtonumber(arg[1])or4hanoi(num)
> ./hanoi_iter.lua 51:1→2 2:1→3 1:2→3 3:1→2 1:3→1 2:3→2 1:1→2 4:1→3 1:2→3 2:2→1 1:3→1 3:2→3 1:1→2 2:1→3 1:2→3 5:1→2 1:3→1 2:3→2 1:1→2 3:3→1 1:2→3 2:2→1 1:3→1 4:3→2 1:1→2 2:1→3 1:2→3 3:1→2 1:3→1 2:3→2 1:1→2
#!/usr/bin/env luajit-- binary solutionlocalbit=require"bit"localband,bor=bit.band,bit.borlocalfunctionhanoi(n)localeven=(n-1)%2form=1,2^n-1doio.write(m,":",band(m,m-1)%3+1,"→",(bor(m,m-1)+1)%3+1," ")endendlocalnum=arg[1]andtonumber(arg[1])or4hanoi(num)
> ./hanoi_bit.lua 41:1→3 2:1→2 3:3→2 4:1→3 5:2→1 6:2→3 7:1→3 8:1→2 9:3→2 10:3→1 11:2→1 12:3→2 13:1→3 14:1→2 15:3→2 > time ./hanoi_bit.lua 30 >/dev/null ; on AMD FX-8350 @ 4 GHz./hanoi_bit.lua 30 > /dev/null 297,40s user 1,39s system 99% cpu 4:59,01 total
Module Hanoi { Rem HANOI TOWERS Print "Three disks" : Print move(3, 1, 2, 3) Print Print "Four disks" : Print move(4, 1, 2, 3) Sub move(n, from, to, via) If n <=0 Then Exit Sub move(n - 1, from, via, to) Print "Move disk"; n; " from pole"; from; " to pole"; to move(n - 1, via, to, from) End Sub}Hanoisame as in FreeBasic
.TITLE HANOI .MCALL .PRINT,.EXITHANOI:: MOV #4,R2 MOV #61,R3 MOV #62,R4 MOV #63,R5 JSR PC,MOVE .EXITMOVE: DEC R2 BLT 1$ MOV R2,-(SP) MOV R3,-(SP) MOV R4,-(SP) MOV R5,-(SP) MOV R5,R0 MOV R4,R5 MOV R0,R4 JSR PC,MOVE MOV (SP)+,R5 MOV (SP)+,R4 MOV (SP)+,R3 MOV (SP)+,R2 MOVB R3,3$ MOVB R4,4$ .PRINT #2$ MOV R3,R0 MOV R4,R3 MOV R5,R4 MOV R0,R5 BR MOVE1$: RTS PC2$: .ASCII /MOVE DISK FROM PEG /3$: .ASCII /* TO PEG /4$: .ASCIZ /*/ .EVEN .END HANOI
MOVE DISK FROM PEG 1 TO PEG 3MOVE DISK FROM PEG 1 TO PEG 2MOVE DISK FROM PEG 2 TO PEG 3MOVE DISK FROM PEG 1 TO PEG 3MOVE DISK FROM PEG 3 TO PEG 1MOVE DISK FROM PEG 3 TO PEG 2MOVE DISK FROM PEG 2 TO PEG 1MOVE DISK FROM PEG 1 TO PEG 2MOVE DISK FROM PEG 2 TO PEG 3MOVE DISK FROM PEG 2 TO PEG 1MOVE DISK FROM PEG 1 TO PEG 3MOVE DISK FROM PEG 2 TO PEG 3MOVE DISK FROM PEG 3 TO PEG 2MOVE DISK FROM PEG 3 TO PEG 1MOVE DISK FROM PEG 1 TO PEG 2
NORMAL MODE IS INTEGER DIMENSION LIST(100) SET LIST TO LIST VECTOR VALUES MOVFMT = 0 $20HMOVE DISK FROM POLE ,I1,S1,8HTO POLE ,I1*$ INTERNAL FUNCTION(DUMMY) ENTRY TO MOVE.LOOP NUM = NUM - 1 WHENEVER NUM.E.0 PRINT FORMAT MOVFMT,FROM,DEST OTHERWISE SAVE RETURN SAVE DATA NUM,FROM,VIA,DEST TEMP=DEST DEST=VIA VIA=TEMP MOVE.(0) RESTORE DATA NUM,FROM,VIA,DEST RESTORE RETURN PRINT FORMAT MOVFMT,FROM,DEST TEMP=FROM FROM=VIA VIA=TEMP TRANSFER TO LOOP END OF CONDITIONAL FUNCTION RETURN END OF FUNCTION NUM = 4 FROM = 1 VIA = 2 DEST = 3 MOVE.(0) END OF PROGRAM
MOVE DISK FROM POLE 1 TO POLE 2MOVE DISK FROM POLE 1 TO POLE 3MOVE DISK FROM POLE 2 TO POLE 3MOVE DISK FROM POLE 1 TO POLE 2MOVE DISK FROM POLE 3 TO POLE 1MOVE DISK FROM POLE 3 TO POLE 2MOVE DISK FROM POLE 1 TO POLE 2MOVE DISK FROM POLE 1 TO POLE 3MOVE DISK FROM POLE 2 TO POLE 3MOVE DISK FROM POLE 2 TO POLE 1MOVE DISK FROM POLE 3 TO POLE 1MOVE DISK FROM POLE 2 TO POLE 3MOVE DISK FROM POLE 1 TO POLE 2MOVE DISK FROM POLE 1 TO POLE 3MOVE DISK FROM POLE 2 TO POLE 3
Hanoi := proc(n::posint,a,b,c) if n = 1 then printf("Move disk from tower %a to tower %a.\n",a,c); else Hanoi(n-1,a,c,b); Hanoi(1,a,b,c); Hanoi(n-1,b,a,c); fi;end:printf("Moving 2 disks from tower A to tower C using tower B.\n");Hanoi(2,A,B,C);Moving 2 disks from tower A to tower C using tower B.
Move disk from tower A to tower B.
Move disk from tower A to tower C.
Move disk from tower B to tower C.
Hanoi[0,from_,to_,via_]:=NullHanoi[n_Integer,from_,to_,via_]:=(Hanoi[n-1,from,via,to];Print["Move disk from pole ",from," to ",to,"."];Hanoi[n-1,via,to,from])
This is a direct translation from the Python example given in the Wikipedia entry for the Tower of Hanoi puzzle.
functiontowerOfHanoi(n,A,C,B)if(n~=0)towerOfHanoi(n-1,A,B,C);disp(sprintf('Move plate %d from tower %d to tower %d',[nAC]));towerOfHanoi(n-1,B,C,A);endend
towerOfHanoi(3,1,3,2)Move plate 1 from tower 1 to tower 3Move plate 2 from tower 1 to tower 2Move plate 1 from tower 3 to tower 2Move plate 3 from tower 1 to tower 3Move plate 1 from tower 2 to tower 1Move plate 2 from tower 2 to tower 3Move plate 1 from tower 1 to tower 3
moveDisc = function(n, A, C, B) if n == 0 then return moveDisc n-1, A, B, C print "Move disc " + n + " from pole " + A + " to pole " + C moveDisc n-1, B, C, Aend function// Move disc 3 from pole 1 to pole 3, with pole 2 as sparemoveDisc 3, 1, 3, 2
Move disc 1 from pole 1 to pole 3Move disc 2 from pole 1 to pole 2Move disc 1 from pole 3 to pole 2Move disc 3 from pole 1 to pole 3Move disc 1 from pole 2 to pole 1Move disc 2 from pole 2 to pole 3Move disc 1 from pole 1 to pole 3
main :: [sys_message]main = [Stdout (lay (map showmove (move 4 1 2 3)))]showmove :: (num,num)->[char]showmove (src,dest) = "Move disk from pole " ++ show src ++ " to pole " ++ show destmove :: num->*->*->*->[(*,*)]move n src via dest = [], if n=0 = left ++ [(src,dest)] ++ right, otherwise where left = move (n-1) src dest via right = move (n-1) via src dest
Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
# Towers of Hanoi# MIPS assembly implementation (tested with MARS)# Source: https://stackoverflow.com/questions/50382420/hanoi-towers-recursive-solution-using-mips/50383530#50383530.dataprompt: .asciiz "Enter a number: "part1: .asciiz "\nMove disk "part2: .asciiz " from rod "part3: .asciiz " to rod ".text.globl mainmain: li $v0, 4 # print string la $a0, prompt syscall li $v0, 5 # read integer syscall # parameters for the routine add $a0, $v0, $zero # move to $a0 li $a1, 'A' li $a2, 'B' li $a3, 'C' jal hanoi # call hanoi routine li $v0, 10 # exit syscallhanoi: #save in stack addi $sp, $sp, -20 sw $ra, 0($sp) sw $s0, 4($sp) sw $s1, 8($sp) sw $s2, 12($sp) sw $s3, 16($sp) add $s0, $a0, $zero add $s1, $a1, $zero add $s2, $a2, $zero add $s3, $a3, $zero addi $t1, $zero, 1 beq $s0, $t1, output recur1: addi $a0, $s0, -1 add $a1, $s1, $zero add $a2, $s3, $zero add $a3, $s2, $zero jal hanoi j output recur2: addi $a0, $s0, -1 add $a1, $s3, $zero add $a2, $s2, $zero add $a3, $s1, $zero jal hanoi exithanoi: lw $ra, 0($sp) # restore registers from stack lw $s0, 4($sp) lw $s1, 8($sp) lw $s2, 12($sp) lw $s3, 16($sp) addi $sp, $sp, 20 # restore stack pointer jr $ra output: li $v0, 4 # print string la $a0, part1 syscall li $v0, 1 # print integer add $a0, $s0, $zero syscall li $v0, 4 # print string la $a0, part2 syscall li $v0, 11 # print character add $a0, $s1, $zero syscall li $v0, 4 # print string la $a0, part3 syscall li $v0, 11 # print character add $a0, $s2, $zero syscall beq $s0, $t1, exithanoi j recur2
^2x^yП0<->2/{x}x#0163П32П2БП203П22П31П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В/О10/+С/ПКИП0ИП0x=089331ИНВ^ВП2С/ПВ/ОInstruction: РA = 56; РB = 60; РC = 72; N В/О С/П, where 2 <= N <= 7.
MODULE Towers;FROM FormatString IMPORT FormatString;FROM Terminal IMPORT WriteString,ReadChar;PROCEDURE Move(n,from,to,via : INTEGER);VAR buf : ARRAY[0..63] OF CHAR;BEGIN IF n>0 THEN Move(n-1, from, via, to); FormatString("Move disk %i from pole %i to pole %i\n", buf, n, from, to); WriteString(buf); Move(n-1, via, to, from) ENDEND Move;BEGIN Move(3, 1, 3, 2); ReadCharEND Towers.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.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")
hanoi = (n, src, dest, via) -> if n > 1 hanoi n-1, src, via, dest print "#{src} -> #{dest}" if n > 1 hanoi n-1, via, dest, srchanoi 4,1,3,21 -> 21 -> 32 -> 31 -> 23 -> 13 -> 21 -> 21 -> 32 -> 32 -> 13 -> 12 -> 31 -> 21 -> 32 -> 3
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) } }/* NetRexx */options replace format comments java crossref symbols binaryrunSample(arg)return-- 09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)~~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-- 09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)09:02, 27 August 2022 (UTC)~~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
Minimum moves to solution: 15Move disc from peg 1 to peg 3 - Move No: 1Move disc from peg 1 to peg 2 - Move No: 2Move disc from peg 3 to peg 2 - Move No: 3Move disc from peg 1 to peg 3 - Move No: 4Move disc from peg 2 to peg 1 - Move No: 5Move disc from peg 2 to peg 3 - Move No: 6Move disc from peg 1 to peg 3 - Move No: 7Move disc from peg 1 to peg 2 - Move No: 8Move disc from peg 3 to peg 2 - Move No: 9Move disc from peg 3 to peg 1 - Move No: 10Move disc from peg 2 to peg 1 - Move No: 11Move disc from peg 3 to peg 2 - Move No: 12Move disc from peg 1 to peg 3 - Move No: 13Move disc from peg 1 to peg 2 - Move No: 14Move disc from peg 3 to peg 2 - Move No: 15Solved in 15 moves.
(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)
proc hanoi(disks: int; fromTower, toTower, 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")Move disk 1 from 1 to 3Move disk 2 from 1 to 2Move disk 1 from 3 to 2Move disk 3 from 1 to 3Move disk 1 from 2 to 1Move disk 2 from 2 to 3Move disk 1 from 1 to 3Move disk 4 from 1 to 2Move disk 1 from 3 to 2Move disk 2 from 3 to 1Move disk 1 from 2 to 1Move disk 3 from 3 to 2Move disk 1 from 1 to 3Move disk 2 from 1 to 2Move disk 1 from 3 to 2
MODULE Hanoi; IMPORT Out; PROCEDURE Move(n,from,via,to:INTEGER); BEGIN IF n > 1 THEN Move(n-1,from,to,via); Out.String("Move disk from pole "); Out.Int(from,0); Out.String(" to pole "); Out.Int(to,0); Out.Ln; Move(n-1,via,from,to); ELSE Out.String("Move disk from pole "); Out.Int(from,0); Out.String(" to pole "); Out.Int(to,0); Out.Ln; END; END Move; BEGIN Move(4,1,2,3);END Hanoi.Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
class Hanoi { function : Main(args : String[]) ~ Nil { Move(4, 1, 2, 3); } function: Move(n:Int, f:Int, t:Int, v:Int) ~ Nil { if(n = 1) { "Move disk from pole {$f} to pole {$t}"->PrintLine(); } else { Move(n - 1, f, v, t); Move(1, f, t, v); Move(n - 1, v, t, f); }; }}Fromhere
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;@endThe 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]; }}@endTest code: TowersTest.m:
#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;}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 endlet () = hanoi 4 1 2 3
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); endifendfunctionhanoimove(4, 1, 2, 3);: 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) ] ;5 $left $middle $right) move
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 endin {TowersOfHanoi 4 left middle right}\\ Towers of Hanoi\\ 8/19/2016 aev\\ Where: n - number of disks, sp - start pole, ep - end pole.HanoiTowers(n,sp,ep)={ if(n!=0, HanoiTowers(n-1,sp,6-sp-ep); print("Move disk ", n, " from pole ", sp," to pole ", ep); HanoiTowers(n-1,6-sp-ep,ep); );}\\ Testing n=3:HanoiTowers(3,1,3);> HanoiTower(3,1,3);Move disk 1 from pole 1 to pole 3Move disk 2 from pole 1 to pole 2Move disk 1 from pole 3 to pole 2Move disk 3 from pole 1 to pole 3Move disk 1 from pole 2 to pole 1Move disk 2 from pole 2 to pole 3Move disk 1 from pole 1 to pole 3
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.## procedure Hanoi(n,rfrom,rto,rwork: integer);begin if n = 0 then exit; Hanoi(n-1,rfrom,rwork,rto); Print($'{rfrom}→{rto} '); Hanoi(n-1,rwork,rto,rfrom);end;Hanoi(5,1,3,2);1→3 1→2 3→2 1→3 2→1 2→3 1→3 1→2 3→2 3→1 2→1 3→2 1→3 1→2 3→2 1→3 2→1 2→3 1→3 2→1 3→2 3→1 2→1 2→3 1→3 1→2 3→2 1→3 2→1 2→3 1→3
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); };};constantpoles={"left","middle","right"}enumleft,middle,rightsequencedisksintegermovesprocedureshowpegs(integersrc,integerdest)stringdesc=sprintf("%s to %s:",{poles[src],poles[dest]})disks[dest]&=disks[src][$]disks[src]=disks[src][1..$-1]fori=1tolength(disks)doprintf(1,"%-16s | %s\n",{desc,join(sq_add(disks[i],'0'),' ')})desc=""endforprintf(1,"\n")moves+=1endprocedureprocedurehanoir(integern,src=left,dest=right,via=middle)ifn>0thenhanoir(n-1,src,via,dest)showpegs(src,dest)hanoir(n-1,via,dest,src)endifendprocedureprocedurehanoi(integern)disks={reverse(tagset(n)),{},{}}moves=0hanoir(n)printf(1,"completed in %d moves\n",{moves})endprocedurehanoi(3)-- (output of 4,5,6 also shown)
left to right: | 3 2 | | 1left to middle: | 3 | 2 | 1right to middle: | 3 | 2 1 |left to right: | | 2 1 | 3middle to left: | 1 | 2 | 3middle to right: | 1 | | 3 2left to right: | | | 3 2 1completed in 7 moves
left to middle: | 4 3 2 | 1 |left to right: | 4 3 | 1 | 2middle to right: | 4 3 | | 2 1 ...left to middle: | 2 | 1 | 4 3left to right: | | 1 | 4 3 2middle to right: | | | 4 3 2 1completed in 15 moves
left to right: | 5 4 3 2 | | 1left to middle: | 5 4 3 | 2 | 1right to middle: | 5 4 3 | 2 1 | ...middle to left: | 1 | 2 | 5 4 3middle to right: | 1 | | 5 4 3 2left to right: | | | 5 4 3 2 1completed in 31 moves
left to middle: | 6 5 4 3 2 | 1 |left to right: | 6 5 4 3 | 1 | 2middle to right: | 6 5 4 3 | | 2 1 ...left to middle: | 2 | 1 | 6 5 4 3left to right: | | 1 | 6 5 4 3 2middle to right: | | | 6 5 4 3 2 1completed in 63 moves
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;]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); }}main => hanoi(3, left, center, right).hanoi(0, _From, _To, _Via) => true.hanoi(N, From, To, Via) => hanoi(N - 1, From, Via, To), printf("Move disk %w from pole %w to pole %w\n", N, From, To), hanoi(N - 1, Via, To, From).Move disk 1 from pole left to pole centerMove disk 2 from pole left to pole rightMove disk 1 from pole center to pole rightMove disk 3 from pole left to pole centerMove disk 1 from pole right to pole leftMove disk 2 from pole right to pole centerMove disk 1 from pole left to pole centercount=7, theoretical=7
main => hanoi(64).hanoi(N) => printf("N=%d\n", N), Count = move(N, left, center, right) , printf("count=%w, theoretical=%w\n", Count, 2**N-1). tablemove(0, _From, _To, _Via) = 0.move(N, From, To, Via) = Count => Count1 = move(N - 1, From, Via, To), Count2 = move(N - 1, Via, To, From), Count = Count1+Count2+1.N=64count=18446744073709551615, theoretical=18446744073709551615
(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) ) )
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;Iterative solution as PL/M doesn't do recursion.
... under CP/M (or an emulator)
100H: /* ITERATIVE TOWERS OF HANOI; TRANSLATED FROM TINY BASIC (VIA ALGOL W) */ /* CP/M BDOS SYSTEM CALL */ BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END; /* I/O ROUTINES */ PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END; PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END; DECLARE ( D, N, X, S, T ) ADDRESS; /* FIXED NUMBER OF DISCS: 4 */ N = 1; DO D = 1 TO 4; N = N + N; END; DO X = 1 TO N - 1; /* AS IN ALGOL W, WE CAN USE PL/M'S BIT ABD MOD OPERATORS */ S = ( X AND ( X - 1 ) ) MOD 3; T = ( ( X OR ( X - 1 ) ) + 1 ) MOD 3; CALL PR$STRING( .'MOVE DISC ON PEG $' ); CALL PR$CHAR( '1' + S ); CALL PR$STRING( .' TO PEG $' ); CALL PR$CHAR( '1' + T ); CALL PR$STRING( .( 0DH, 0AH, '$' ) ); END;EOF
MOVE DISC ON PEG 1 TO PEG 3MOVE DISC ON PEG 1 TO PEG 2MOVE DISC ON PEG 3 TO PEG 2MOVE DISC ON PEG 1 TO PEG 3MOVE DISC ON PEG 2 TO PEG 1MOVE DISC ON PEG 2 TO PEG 3MOVE DISC ON PEG 1 TO PEG 3MOVE DISC ON PEG 1 TO PEG 2MOVE DISC ON PEG 3 TO PEG 2MOVE DISC ON PEG 3 TO PEG 1MOVE DISC ON PEG 2 TO PEG 1MOVE DISC ON PEG 3 TO PEG 2MOVE DISC ON PEG 1 TO PEG 3MOVE DISC ON PEG 1 TO PEG 2MOVE DISC ON PEG 3 TO PEG 2
\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}\enddefine 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");
A million-page document, each page showing one move.
%!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 ] [] [] ] defdrawtower 0 1 2 n hanoi%%EOFfunction hanoi($n, $a, $b, $c) { if($n -eq 1) { "$a -> $c" } else{ hanoi ($n - 1) $a $c $b hanoi 1 $a $b $c hanoi ($n - 1) $b $a $c }}hanoi 3 "A" "B" "C"Output:
A -> CA -> BC -> BA -> CB -> AB -> CA -> C
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.
Using DCGs and separating core logic from IO
hanoi(N, Src, Aux, Dest, Moves-NMoves) :- NMoves is 2^N - 1, length(Moves, NMoves), phrase(move(N, Src, Aux, Dest), Moves).move(1, Src, _, Dest) --> !, [Src->Dest].move(2, Src, Aux, Dest) --> !, [Src->Aux,Src->Dest,Aux->Dest].move(N, Src, Aux, Dest) --> { succ(N0, N) }, move(N0, Src, Dest, Aux), move(1, Src, Aux, Dest), move(N0, Aux, Src, Dest).Algorithm according tohttp://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) EndIfEndProcedureFull 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) EndIfEndProcedureIf 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()EndIfMoving 3 pegs.Move the plate from Left Peg to Middle PegMove the plate from Left Peg to Right PegMove the plate from Middle Peg to Right PegMove the plate from Left Peg to Middle PegMove the plate from Right Peg to Left PegMove the plate from Right Peg to Middle PegMove the plate from Left Peg to Middle PegPress ENTER to exit.
def hanoi(ndisks, startPeg=1, endPeg=3): if ndisks: hanoi(ndisks-1, startPeg, 6-startPeg-endPeg) print(f"Move disk {ndisks} from peg {startPeg} to peg {endPeg}") hanoi(ndisks-1, 6-startPeg-endPeg, endPeg) hanoi(4)for ndisks=2
Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3
Or, separating the definition of the data from its display:
'''Towers of Hanoi'''# hanoi :: Int -> String -> String -> String -> [(String, String)]def hanoi(n): '''A list of (from, to) label pairs, where a, b and c are labels for each of the three Hanoi tower positions.''' def go(n, a, b, c): p = n - 1 return ( go(p, a, c, b) + [(a, b)] + go(p, c, b, a) ) if 0 < n else [] return lambda a: lambda b: lambda c: go(n, a, b, c)# TEST ----------------------------------------------------if __name__ == '__main__': # fromTo :: (String, String) -> String def fromTo(xy): '''x -> y''' x, y = xy return x.rjust(5, ' ') + ' -> ' + y print(__doc__ + ':\n\n' + '\n'.join( map(fromTo, hanoi(4)('left')('right')('mid')) ))Towers of Hanoi: left -> mid left -> right mid -> right left -> midright -> leftright -> mid left -> mid left -> right mid -> right mid -> leftright -> left mid -> right left -> mid left -> right mid -> right
Refactoring the version above to recursively generate a simple visualisation:
'''Towers of Hanoi'''from itertools import accumulate, chain, repeatfrom inspect import signatureimport operator# hanoi :: Int -> [(Int, Int)]def hanoi(n): '''A list of index pairs, representing disk moves between indexed Hanoi positions. ''' def go(n, a, b, c): p = n - 1 return ( go(p, a, c, b) + [(a, b)] + go(p, c, b, a) ) if 0 < n else [] return go(n, 0, 2, 1)# hanoiState :: ([Int],[Int],[Int], String) -> (Int, Int) -># ([Int],[Int],[Int], String)def hanoiState(tpl, ab): '''A new Hanoi tower state''' a, b = ab xs, ys = tpl[a], tpl[b] w = 3 * (2 + (2 * max(map(max, filter(len, tpl[:-1]))))) def delta(i): return tpl[i] if i not in ab else xs[1:] if ( i == a ) else [xs[0]] + ys tkns = moveName(('left', 'mid', 'right'))(ab) caption = ' '.join(tkns) return tuple(map(delta, [0, 1, 2])) + ( (caption if tkns[0] != 'mid' else caption.rjust(w, ' ')), )# showHanoi :: ([Int],[Int],[Int], String) -> Stringdef showHanoi(tpl): '''Captioned string representation of an updated Hanoi tower state.''' def fullHeight(n): return lambda xs: list(repeat('', n - len(xs))) + xs mul = curry(operator.mul) lt = curry(operator.lt) rods = fmap(fmap(mul('__')))( list(tpl[0:3]) ) h = max(map(len, rods)) w = 2 + max( map( compose(max)(fmap(len)), filter(compose(lt(0))(len), rods) ) ) xs = fmap(concat)( transpose(fmap( compose(fmap(center(w)(' ')))( fullHeight(h) ) )(rods)) ) return tpl[3] + '\n\n' + unlines(xs) + '\n' + ('___' * w)# moveName :: (String, String, String) -> (Int, Int) -> [String]def moveName(labels): '''(from, to) index pair represented as an a -> b string.''' def go(ab): a, b = ab return [labels[a], ' to ', labels[b]] if a < b else [ labels[b], ' from ', labels[a] ] return lambda ab: go(ab)# TEST ----------------------------------------------------def main(): '''Visualisation of a Hanoi tower sequence for N discs. ''' n = 3 print('Hanoi sequence for ' + str(n) + ' disks:\n') print(unlines( fmap(showHanoi)( scanl(hanoiState)( (enumFromTo(1)(n), [], [], '') )(hanoi(n)) ) ))# GENERIC -------------------------------------------------# center :: Int -> Char -> String -> Stringdef center(n): '''String s padded with c to approximate centre, fitting in but not truncated to width n.''' return lambda c: lambda s: s.center(n, c)# compose (<<<) :: (b -> c) -> (a -> b) -> a -> cdef compose(g): '''Right to left function composition.''' return lambda f: lambda x: g(f(x))# concat :: [[a]] -> [a]# concat :: [String] -> Stringdef concat(xs): '''The concatenation of all the elements in a list or iterable.''' def f(ys): zs = list(chain(*ys)) return ''.join(zs) if isinstance(ys[0], str) else zs return ( f(xs) if isinstance(xs, list) else ( chain.from_iterable(xs) ) ) if xs else []# curry :: ((a, b) -> c) -> a -> b -> cdef curry(f): '''A curried function derived from an uncurried function.''' if 1 < len(signature(f).parameters): return lambda x: lambda y: f(x, y) else: return f# enumFromTo :: (Int, Int) -> [Int]def enumFromTo(m): '''Integer enumeration from m to n.''' return lambda n: list(range(m, 1 + n))# fmap :: (a -> b) -> [a] -> [b]def fmap(f): '''fmap over a list. f lifted to a function over a list. ''' return lambda xs: list(map(f, xs))# scanl :: (b -> a -> b) -> b -> [a] -> [b]def scanl(f): '''scanl is like reduce, but returns a succession of intermediate values, building from the left. ''' return lambda a: lambda xs: ( accumulate(chain([a], xs), f) )# showLog :: a -> IO Stringdef showLog(*s): '''Arguments printed with intercalated arrows.''' print( ' -> '.join(map(str, s)) )# transpose :: Matrix a -> Matrix adef transpose(m): '''The rows and columns of the argument transposed. (The matrix containers and rows can be lists or tuples). ''' if m: inner = type(m[0]) z = zip(*m) return (type(m))( map(inner, z) if tuple != inner else z ) else: return m# unlines :: [String] -> Stringdef unlines(xs): '''A single string derived by the intercalation of a list of strings with the newline character. ''' return '\n'.join(xs)# TEST ----------------------------------------------------if __name__ == '__main__': main()Hanoi sequence for 3 disks: __ ____ ______ ________________________left to right ____ ______ __ ________________________left to mid ______ ____ __ ________________________ mid from right __ ______ ____ ________________________left to right __ ____ ______ ________________________left from mid __ ____ ______ ________________________ mid to right ____ __ ______ ________________________left to right __ ____ ______ ________________________
There is a 3D hanoi-game in the examples that come with VPython,and atgithub.
[ stack ] is rings ( --> [ ) [ rings share depth share - 8 * times sp emit sp emit sp say 'move' cr ] is echomove ( c c --> ) [ dup rings put depth put char a char b char c [ swap decurse rot 2dup echomove decurse swap rot ] 3 times drop depth release rings release ] is hanoi ( n --> n ) say 'How to solve a three ring Towers of Hanoi puzzle:' cr cr 3 hanoi cr
How to solve a three ring Towers of Hanoi puzzle: a c move a b move c b move a c move b a move b c move a c movea b move c b move c a move b a move c b move a c move a b move c b move
'This is implemented on the Quite BASIC website'http://www.quitebasic.com/prj/puzzle/towers-of-hanoi/
1000 REM Towers of Hanoi1010 REM Quite BASIC Puzzle Project1020 CLS1030 PRINT "Towers of Hanoi"1040 PRINT1050 PRINT "This is a recursive solution for seven discs."1060 PRINT1070 PRINT "See the REM statements in the program if you didn't think that recursion was possible in classic BASIC!"1080 REM Yep, recursive GOSUB calls works in Quite BASIC! 1090 REM However, to actually write useful recursive algorithms, it helps to have variable scoping and parameters to subroutines -- something classic BASIC is lacking. In this case we have only one "parameter" -- the variable N. And subroutines are always called with N-1. This is lucky for us because we can keep track of the value by decrementing it when we enter subroutines and incrementing it back when we exit.1100 REM If we had subroutine parameters we could have written a single subroutine for moving discs from peg P to peg Q where P and Q were subroutine parameters, but no such luck. Instead we have to write six different subroutines for moving from peg to peg. See Subroutines 4000, 5000, 6000, 7000, 8000, and 9000.1110 REM ===============================2000 REM A, B, and C are arrays holding the discs2010 REM We refer to the corresponding pegs as peg A, B, and C2020 ARRAY A2030 ARRAY B2040 ARRAY C2050 REM Fill peg A with seven discs2060 FOR I = 0 TO 62070 LET A[I] = 7 - I2080 NEXT I2090 REM X, Y, Z hold the number of discs on pegs A, B, and C2100 LET X = 72110 LET Y = 02120 LET Z = 02130 REM Disc colors2140 ARRAY P2150 LET P[1] = "cyan"2160 LET P[2] = "blue"2170 LET P[3] = "green"2180 LET P[4] = "yellow"2190 LET P[5] = "magenta"2200 LET P[6] = "orange"2210 LET P[7] = "red"2220 REM Draw initial position -- all discs on the A peg2230 FOR I = 0 TO 62240 FOR J = 8 - A[I] TO 8 + A[I]2250 PLOT J, I, P[A[I]]2260 NEXT J2270 NEXT I 2280 REM N is the number of discs to move2290 LET N = 72320 REM Move all discs from peg A to peg B2310 GOSUB 60002320 END3000 REM The subroutines 3400, 3500, 3600, 3700, 3800, 3900 3010 REM handle the drawing of the discs on the canvas as we3020 REM move discs from one peg to another.3030 REM These subroutines also update the variables X, Y, and Z3040 REM which hold the number of discs on each peg.3050 REM ============================== 3400 REM Subroutine -- Remove disc from peg A3410 LET X = X - 13420 FOR I = 8 - A[X] TO 8 + A[X]3430 PLOT I, X, "gray"3440 NEXT I3450 RETURN3500 REM Subroutine -- Add disc to peg A3510 FOR I = 8 - A[X] TO 8 + A[X]3520 PLOT I, X, P[A[X]]3530 NEXT I3540 LET X = X + 13550 PAUSE 400 * (5 - LEVEL) + 10 3560 RETURN3600 REM Subroutine -- Remove disc from peg B3610 LET Y = Y - 13620 FOR I = 24 - B[Y] TO 24 + B[Y]3630 PLOT I, Y, "gray"3640 NEXT I3650 RETURN3700 REM Subroutine -- Add disc to peg B3710 FOR I = 24 - B[Y] TO 24 + B[Y]3720 PLOT I, Y, P[B[Y]]3730 NEXT I3740 LET Y = Y + 13750 PAUSE 400 * (5 - LEVEL) + 10 3760 RETURN3800 REM Subroutine -- Remove disc from peg C3810 LET Z = Z - 13820 FOR I = 40 - C[Z] TO 40 + C[Z]3830 PLOT I, Z, "gray"3840 NEXT I3850 RETURN3900 REM Subroutine -- Add disc to peg C3910 FOR I = 40 - C[Z] TO 40 + C[Z]3920 PLOT I, Z, P[C[Z]]3930 NEXT I3940 LET Z = Z + 13950 PAUSE 400 * (5 - LEVEL) + 10 3960 RETURN4000 REM ======================================4010 REM Recursive Subroutine -- move N discs from peg B to peg A4020 REM First move N-1 discs from peg B to peg C4030 LET N = N - 14040 IF N <> 0 THEN GOSUB 90004050 REM Then move one disc from peg B to peg A 4060 GOSUB 36004070 LET A[X] = B[Y]4080 GOSUB 35004090 REM And finally move N-1 discs from peg C to peg A4100 IF N <> 0 THEN GOSUB 50004110 REM Restore N before returning4120 LET N = N + 14130 RETURN5000 REM ======================================5010 REM Recursive Subroutine -- Move N discs from peg C to peg A5020 REM First move N-1 discs from peg C to peg B5030 LET N = N - 15040 IF N <> 0 THEN GOSUB 80005050 REM Then move one disc from peg C to peg A5060 GOSUB 38005070 LET A[X] = C[Z]5080 GOSUB 35005090 REM And finally move N-1 discs from peg B to peg A5100 IF N <> 0 THEN GOSUB 40005120 REM Restore N before returning5130 LET N = N + 15140 RETURN6000 REM ======================================6000 REM Recursive Subroutine -- Move N discs from peg A to peg B6010 REM First move N-1 discs from peg A to peg C6020 LET N = N - 16030 IF N <> 0 THEN GOSUB 70006040 REM Then move one disc from peg A to peg B6050 GOSUB 34006060 LET B[Y] = A[X]6070 GOSUB 37006090 REM And finally move N-1 discs from peg C to peg B6100 IF N <> 0 THEN GOSUB 80006110 REM Restore N before returning6120 LET N = N + 16130 RETURN7000 REM ======================================7010 REM Recursive Subroutine -- Move N discs from peg A to peg C7020 REM First move N-1 discs from peg A to peg B7030 LET N = N - 17040 IF N <> 0 THEN GOSUB 60007050 REM Then move one disc from peg A to peg C7060 GOSUB 34007070 LET C[Z] = A[X]7080 GOSUB 39007090 REM And finally move N-1 discs from peg B to peg C7100 IF N <> 0 THEN GOSUB 90007110 REM Restore N before returning7120 LET N = N + 17130 RETURN8000 REM ======================================8010 REM Recursive Subroutine -- Move N discs from peg C to peg B8020 REM First move N-1 discs from peg C to peg A8030 LET N = N - 18040 IF N <> 0 THEN GOSUB 50008050 REM Then move one disc from peg C to peg B8060 GOSUB 38008070 LET B[Y] = C[Z]8080 GOSUB 37008090 REM And finally move N-1 discs from peg A to peg B8100 IF N <> 0 THEN GOSUB 60008110 REM Restore N before returning8120 LET N = N + 18130 RETURN9000 REM ======================================9010 REM Recursive Subroutine -- Move N discs from peg B to peg C9020 REM First move N-1 discs from peg B to peg A9030 LET N = N - 19040 IF N <> 0 THEN GOSUB 40009050 REM Then move one disc from peg B to peg C9060 GOSUB 36009070 LET C[Z] = B[Y]9080 GOSUB 39009090 REM And finally move N-1 discs from peg A to peg C9100 IF N <> 0 THEN GOSUB 70009110 REM Restore N before returning9120 LET N = N + 19130 RETURN
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(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)
(formerly Perl 6)
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;}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);}}rascal>hanoi(4,1,3)Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 3 from peg 1 to peg 2Move disk 1 from peg 3 to peg 1Move disk 2 from peg 3 to peg 2Move disk 1 from peg 1 to peg 2Move disk 4 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 2 from peg 2 to peg 1Move disk 1 from peg 3 to peg 1Move disk 3 from peg 2 to peg 3Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3ok
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 - hanoidefine dohanoi use ndisks # startpeg=1, endpeg=3 3 1 ndisks hanoi# 4 disks4 dohanoi
raven hanoi.rv Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 3 from peg 1 to peg 2Move disk 1 from peg 3 to peg 1Move disk 2 from peg 3 to peg 2Move disk 1 from peg 1 to peg 2Move disk 4 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3Move disk 2 from peg 2 to peg 1Move disk 1 from peg 3 to peg 1Move disk 3 from peg 2 to peg 3Move disk 1 from peg 1 to peg 2Move disk 2 from peg 1 to peg 3Move disk 1 from peg 2 to peg 3
REBOL [Title: "Towers of Hanoi"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 toprint [from "->" to] hanoi/poles disks - 1 via to from]hanoi 4left -> rightleft -> middleright -> middleleft -> rightmiddle -> leftmiddle -> rightleft -> rightleft -> middleright -> middleright -> leftmiddle -> leftright -> middleleft -> rightleft -> middleright -> middle
$ENTRY Go { = <Move 4 1 2 3>;};Move { 0 e.X = ; s.N s.Src s.Via s.Dest, <- s.N 1>: s.Next = <Move s.Next s.Src s.Dest s.Via> <Prout "Move disk from pole" s.Src "to pole" s.Dest> <Move s.Next s.Via s.Src s.Dest>;};Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
[[User:Wodan58|Wodan58]] ([[User talk:Wodan58|talk]]){ 'Num 'From 'To 'Via } [ var ] a:for-each :set !Via !To !From !Num ; :display @To @From 'Move_a_ring_from_%n_to_%n\n s:format s:put ; :hanoi (num,from,to,via-) set @Num n:-zero? [ @Num @From @To @Via @Num n:dec @From @Via @To hanoi set display @Num n:dec @Via @To @From hanoi ] if ; #3 #1 #3 #2 hanoi nl [[User:Wodan58|Wodan58]] ([[User talk:Wodan58|talk]])/*REXX program displays the moves to solve the Tower of Hanoi (with N disks). */parse arg N . /*get optional number of disks from CL.*/if N=='' | N=="," then N=3 /*Not specified? Then use the default.*/#= 0 /*#: the number of disk moves (so far)*/z= 2**N - 1 /*Z: " " " minimum # of moves.*/call mov 1, 3, N /*move the top disk, then recurse ··· */say /* [↓] Display the minimum # of moves.*/say 'The minimum number of moves to solve a ' N"─disk Tower of Hanoi is " zexit /*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/mov: procedure expose # z; parse arg @1,@2,@3; L= length(z) if @3==1 then do; #= # + 1 /*bump the (disk) move counter by one. */ say 'step' right(#, L)": move disk on tower" @1 '───►' @2 end 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 /* [↑] this subroutine uses recursion.*/
step 1: move disk on tower 1 ───► 3step 2: move disk on tower 1 ───► 2step 3: move disk on tower 3 ───► 2step 4: move disk on tower 1 ───► 3step 5: move disk on tower 2 ───► 1step 6: move disk on tower 2 ───► 3step 7: move disk on tower 1 ───► 3The minimum number of moves to solve a 3-disk Tower of Hanoi is 7
output when the following was entered (to solve with four disks): 4
step 1: move disk on tower 1 ───► 2step 2: move disk on tower 1 ───► 3step 3: move disk on tower 2 ───► 3step 4: move disk on tower 1 ───► 2step 5: move disk on tower 3 ───► 1step 6: move disk on tower 3 ───► 2step 7: move disk on tower 1 ───► 2step 8: move disk on tower 1 ───► 3step 9: move disk on tower 2 ───► 3step 10: move disk on tower 2 ───► 1step 11: move disk on tower 3 ───► 1step 12: move disk on tower 2 ───► 3step 13: move disk on tower 1 ───► 2step 14: move disk on tower 1 ───► 3step 15: move disk on tower 2 ───► 3The minimum number of moves to solve a 4-disk Tower of Hanoi is 15
This REXX version pictorially shows (via ASCII art) 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 (for each move). "Coloring" of the disks is attempted with dithering.
In addition, it shows each move in a countdown manner (the last move is marked as #1).
It may not be obvious from the pictorial display of the moves, but whenever a disk is moved from one tower to another, it is always the top disk that is moved (to the target tower).
Also, since the pictorial showing of the moves may be voluminous (especially for a larger number of disks), the move counter is started with the maximum and is the count shown is decremented so the viewer can see how many moves are left to display.
/*REXX program displays the moves to solve the Tower of Hanoi (with N disks). */parse arg N . /*get optional number of disks from CL.*/if N=='' | N=="," then N=3 /*Not specified? Then use the default.*/sw= 80; wp= sw%3 - 1; blanks= left('', wp) /*define some default REXX variables. */c.1= sw % 3 % 2 /* [↑] SW: assume default Screen Width*/c.2= sw % 2 - 1 /* ◄─── C.1 C.2 C.2 are the positions*/c.3= sw - 2 - c.1 /* of the 3 columns.*/#= 0; z= 2**N - 1; moveK= z /*#moves; min# of moves; where to move.*/@abc= 'abcdefghijklmnopqrstuvwxyN' /*dithering chars when many disks used.*/ebcdic= ('f2'x==2) /*determine if EBCDIC or ASCII machine.*/if ebcdic then do; bar= 'bf'x; ar= "df"x; dither= 'db9f9caf'x; down= "9a"x tr= 'bc'x; bl= "ab"x; br= 'bb'x; vert= "fa"x; tl= 'ac'x end else do; bar= 'c4'x; ar= "10"x; dither= 'b0b1b2db'x; down= "19"x tr= 'bf'x; bl= "c0"x; br= 'd9'x; vert= "b3"x; tl= 'da'x endverts= vert || vert; Tcorners= tl || tr; box = left(dither, 1)downs= down || down; Bcorners= bl || br; boxChars= dither || @abc$.= 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*/ /*populate the tower of Hanoi spindles.*/call showTowers; call mov 1,3,N; saysay 'The minimum number of moves to solve a ' N"-disk Tower of Hanoi is " zexit /*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/dsk: 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) || tr end if from==2 then do if dest==1 then do; pp= overlay(tl, pp, c.1) pp= overlay(bar, pp, c.1+1, c.2-c.1-1,bar)||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)||tr end 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 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/*──────────────────────────────────────────────────────────────────────────────────────*/mov: if arg(3)==1 then call dsk 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 /* [↑] The MOV subroutine is recursive, */ return /*it uses no variables, is uses BIFs instead*//*──────────────────────────────────────────────────────────────────────────────────────*/showTowers: do j=N by -1 for N; _=@.1.j @.2.j @.3.j; if _\='' then say _; end; return░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓7 └───────────────────────────────────────────────────┐ │ ↓ ▒▒▒▒ ▓▓▓▓▓▓ ░░ ↓6 └─────────────────────────┐ │ ↓ ▓▓▓▓▓▓ ▒▒▒▒ ░░ ↓5 ┌─────────────────────────┘ │ ↓ ░░ ▓▓▓▓▓▓ ▒▒▒▒ ↓4 └───────────────────────────────────────────────────┐ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓3 ┌─────────────────────────┘ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓ ↓2 └─────────────────────────┐ │ ↓ ▒▒▒▒ ░░ ▓▓▓▓▓▓ ↓1 └───────────────────────────────────────────────────┐ │ ↓ ░░ ▒▒▒▒ ▓▓▓▓▓▓The minimum number of moves to solve a 3-disk Tower of Hanoi is 7
move(4, 1, 2, 3)func move n, src, dst, via if n > 0 move(n - 1, src, via, dst) see "" + src + " to " + dst + nl move(n - 1, via, dst, src) ok
≪ → ndisks start end ≪IF ndisksTHEN ndisks 1 - start 6 start - end -HANOI start →STR " → " + end →STR + ndisks 1 - 6 start - end - endHANOIEND≫ ≫ 'HANOI' STO
3 1 3HANOI
7: "1 → 3"6: "1 → 2"5: "3 → 2"4: "1 → 3"3: "2 → 1"2: "2 → 3"1: "1 → 3"
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 endn = 5@towers = [[*1..n].reverse, [], []]move(n)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], []]
# 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 endendsolve([5, 4, 3, 2, 1], [], [])[[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]]
a = move(4, "1", "2", "3")function move(n, a$, b$, c$) if n > 0 thena = move(n-1, a$, c$, b$)print "Move disk from " ; a$ ; " to " ; c$a = move(n-1, b$, a$, c$)end ifend function
Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2
fn move_(n: i32, from: i32, to: i32, via: i32) { if n > 0 { move_(n - 1, from, via, to); println!("Move disk from pole {} to pole {}", from, to); move_(n - 1, via, to, from); }}fn main() { move_(4, 1,2,3);}Copied from SAL manual, Appendix II, answer (3)
hanoi 8 ‘abc"WHEREhanoi 0 (a,b,c,) = ()hanoi n ( a,b,c) = hanoi (n-1) (a,c,b) , ‘move a disc from " , a , ‘ to " , b , NL , hanoi (n-1) (c,b,a)?
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;
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) } }This next example is fromhttp://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] }}Recursive Process
(define (towers-of-hanoi n from to spare) (define (print-move from to) (display "Move[") (display from) (display ", ") (display to) (display "]") (newline)) (cond ((= n 0) "done") (else (towers-of-hanoi (- n 1) from spare to) (print-move from to) (towers-of-hanoi (- n 1) spare to from))))(towers-of-hanoi 3 "A" "B" "C")
Move[A, B]Move[A, C]Move[B, C]Move[A, B]Move[C, A]Move[C, B]Move[A, B]"done"
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;program hanoi; loop for [src, dest] in move(4, 1, 2, 3) do print("Move disk from pole " + src + " to pole " + dest); end loop; proc move(n, src, via, dest); if n=0 then return []; end if; return move(n-1, src, dest, via) + [[src, dest]] + move(n-1, via, src, dest); end proc;end program;Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
func hanoi(n, from=1, to=2, via=3) { if (n == 1) { say "Move disk from pole #{from} to pole #{to}."; } else { hanoi(n-1, from, via, to); hanoi( 1, from, to, via); hanoi(n-1, via, to, from); }}hanoi(4);* # 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')end1: Move disc from A to B2: Move disc from A to C3: Move disc from B to C4: Move disc from A to B5: Move disc from C to A6: Move disc from C to B7: Move disc from A to B8: Move disc from A to C9: Move disc from B to C10: Move disc from B to A11: Move disc from C to A12: Move disc from B to C13: Move disc from A to B14: Move disc from A to C15: Move disc from B to C
As a structured script.
#!/usr/local/bin/sparpragma annotate( summary, "hanoi" ) @( description, "Solve the Towers of Hanoi problem with recursion." ) @( see_also, "https://rosettacode.org/wiki/Towers_of_Hanoi" ) @( author, "Ken O. Burtch" );pragma license( unrestricted );pragma restriction( no_external_commands );procedure hanoi is type pegs is (left, center, right); -- Determine the moves procedure solve( num_disks : natural; start_peg : pegs; end_peg : pegs; via_peg : pegs ) is begin if num_disks > 0 then solve( num_disks - 1, start_peg, via_peg, end_peg ); put( "Move disk" )@( num_disks )@( " from " )@( start_peg )@( " to " )@( end_peg ); new_line; solve( num_disks - 1, via_peg, end_peg, start_peg ); end if; end solve;begin -- solve with 4 disks at the left --solve( 4, left, right, center ); solve( 4, left, right, center ); put_line( "Towers of Hanoi puzzle completed" );end hanoi;
fun hanoi(0, a, b, c) = [] | hanoi(n, a, b, c) = hanoi(n-1, a, c, b) @ [(a,b)] @ hanoi(n-1, c, b, a);
function hanoi(n, a, b, c) {if (n>0) {hanoi(n-1, a, c, b)printf("Move from %f to %f\n", a, b)hanoi(n-1, c, b, a)}}hanoi(3, 1, 2, 3)Move from 1 to 2Move from 1 to 3Move from 2 to 3Move from 1 to 2Move from 3 to 1Move from 3 to 2Move from 1 to 2func 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")Swift 2.1
func hanoi(n:Int, a:String, b:String, c:String) { if (n > 0) { hanoi(n - 1, a: a, b: c, c: b) print("Move disk from \(a) to \(c)") hanoi(n - 1, a: b, b: a, c: c) }} hanoi(4, a:"A", b:"B", c:"C")The use ofinterp alias shown is a sort of closure: keep track of the number of moves required
interp alias {} hanoi {} do_hanoi 0proc 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 41: move from A to B2: move from A to C3: move from B to C4: move from A to B5: move from C to A6: move from C to B7: move from A to B8: move from A to C9: move from B to C10: move from B to A11: move from C to A12: move from B to C13: move from A to B14: move from A to C15: move from B to C
TI-83 BASIC lacks recursion, so technically this task is impossible, however here is a version that uses an iterative method.
PROGRAM:TOHSOLVE0→A1→B0→C0→D0→M1→RWhile A<1 or A>7Input "No. of rings=?",AEndrandM(A+1,3)→[C][[1,2][1,3][2,3]]→[E]Fill(0,[C])For(I,1,A,1)I?[C](I,1)EndClrHomeWhile [C](1,3)≠1 and [C](1,2)≠1For(J,1,3)For(I,1,A)If [C](I,J)≠0:ThenOutput(I+1,3J,[C](I,J))EndEndEndWhile C=0Output(1,3B," ")1→I[E](R,2)→JWhile [C](I,J)=0 and I≤AI+1→IEnd[C](I,J)→D1→I[E](R,1)→JWhile [C](I,J)=0 and I≤AI+1→IEndIf (D<[C](I,J) and D≠0) or [C](I,J)=0:Then[E](R,2)→BElse[E](R,1)→BEnd1→IWhile [C](I,B)=0 and I≤AI+1→IEndIf I≤A:Then[C](I,B)→C0→[C](I,B)Output(I+1,3B," ")EndOutput(1,3B,"V")EndWhile C≠0Output(1,3B," ")If B=[E](R,2):Then[E](R,1)→BElse[E](R,2)→BEnd1→IWhile [C](I,B)=0 and I≤AI+1→IEndIf [C](I,B)=0 or [C](I,B)>C:ThenC→[C](I-1,B)0→CM+1→MEndEndOutput(1,3B,"V")R+1→RIf R=4:Then:1→R:EndEnd
Tiny BASIC does not have recursion, so only an iterative solution is possible... and it has no arrays, so actually keeping track of individual discs is not feasible.
But as if by magic, it turns out that the source and destination pegs on iteration number n are given by (n&n-1) mod 3 and ((n|n-1) + 1) mod 3 respectively, where & and | are the bitwise and and or operators. Line 40 onward is dedicated to implementing those bitwise operations, since Tiny BASIC hasn't got them natively.
5 PRINT "How many disks?" INPUT D IF D < 1 THEN GOTO 5 IF D > 10 THEN GOTO 5 LET N = 110 IF D = 0 THEN GOTO 20 LET D = D - 1 LET N = 2*N GOTO 1020 LET X = 030 LET X = X + 1 IF X = N THEN END GOSUB 40 LET S = S - 3*(S/3) GOSUB 50 LET T = T + 1 LET T = T - 3*(T/3) PRINT "Move disc on peg ",S+1," to peg ",T+1 GOTO 3040 LET B = X - 1 LET A = X LET S = 0 LET Z = 204845 LET C = 0 IF B >= Z THEN LET C = 1 IF A >= Z THEN LET C = C + 1 IF C = 2 THEN LET S = S + Z IF A >= Z THEN LET A = A - Z IF B >= Z THEN LET B = B - Z LET Z = Z / 2 IF Z = 0 THEN RETURN GOTO 4550 LET B = X - 1 LET A = X LET T = 0 LET Z = 204855 LET C = 0 IF B >= Z THEN LET C = 1 IF A >= Z THEN LET C = C + 1 IF C > 0 THEN LET T = T + Z IF A >= Z THEN LET A = A - Z IF B >= Z THEN LET B = B - Z LET Z = Z / 2 IF Z = 0 THEN RETURN GOTO 55
How many discs?4Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2Move disc on peg 1 to peg 3Move disc on peg 2 to peg 1Move disc on peg 2 to peg 3Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2Move disc on peg 3 to peg 1Move disc on peg 2 to peg 1Move disc on peg 3 to peg 2Move disc on peg 1 to peg 3Move disc on peg 1 to peg 2Move disc on peg 3 to peg 2
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
DECLARE SUB hanoiSUB hanoi(n, desde , hasta, via) IF n > 0 THEN CALL hanoi(n - 1, desde, via, hasta) PRINT "Mover disco"; n; "desde posición"; desde; "hasta posición"; hasta CALL hanoi(n - 1, via, hasta, desde) END IFEND SUBPRINT "Tres discos"PRINTCALL hanoi(3, 1, 2, 3)PRINTPRINT "Cuatro discos"PRINTCALL hanoi(4, 1, 2, 3)PRINTPRINT "Pulsa un tecla para salir"END
// 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 )ENDPROC 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
Proc _Move(4, 1,2,3) ' 4 disks, 3 polesEnd_Move Param(4) If (a@ > 0) Then Proc _Move (a@ - 1, b@, d@, c@) Print "Move disk from pole ";b@;" to pole ";c@ Proc _Move (a@ - 1, d@, c@, b@) EndIfReturn
F ← |1.0 ( ⨬( &p $"Move disc from _ to _" °⊟ ⊏[1 2] | F⍜(⊢|-1)⍜(⊏[2 3]|⇌). F⍜(⊢|⋅1). F⍜(⊢|-1)⍜(⊏[1 3]|⇌) )≠1⊢.)F [4 1 2 3]
Move disc from 1 to 3Move disc from 1 to 2Move disc from 3 to 2Move disc from 1 to 3Move disc from 2 to 1Move disc from 2 to 3Move disc from 1 to 3Move disc from 1 to 2Move disc from 3 to 2Move disc from 3 to 1Move disc from 2 to 1Move disc from 3 to 2Move disc from 1 to 3Move disc from 1 to 2Move disc from 3 to 2
function move { typeset -i n=$1 typeset from=$2 typeset to=$3 typeset via=$4 if (( n )); then move $(( n - 1 )) "$from" "$via" "$to" echo "Move disk from pole $from to pole $to" move $(( n - 1 )) "$via" "$to" "$from" fi} move "$@"A strict POSIX (or just really old) shell has no subprogram capability, but scripts are naturally reentrant, so:
#!/bin/shif [ "$1" -gt 0 ]; then "$0" "`expr $1 - 1`" "$2" "$4" "$3" echo "Move disk from pole $2 to pole $3" "$0" "`expr $1 - 1`" "$4" "$3" "$2"fi
Output from any of the above:
$ hanoi 4 1 3 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 2 to pole 1Move disk from pole 3 to pole 1Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3
#import natmove = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC#show+main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'>
start -> middlestart -> endmiddle -> endstart -> middleend -> startend -> middlestart -> middlestart -> endmiddle -> endmiddle -> startend -> startmiddle -> endstart -> middlestart -> endmiddle -> end
%newline { [ LIT2 0a -Console/write ] DEO }|18 @Console/write|0100#0102 #0304 hanoiPOP2 POP2 BRK@hanoi ( from spare to count -- from spare to count ) ( moving 0 disks is no-op ) DUP ?{ JMP2r } ( move disks 1..count-1 to the spare peg ) #01 SUB ROT SWP hanoi ( from to spare count-1 ) ( print the current move ) ;dict/move print/str INCk #30 ORA .Console/write DEO STH2 ;dict/from print/str OVR #30 ORA .Console/write DEO ;dict/to print/str DUP #30 ORA .Console/write DEOnewline STH2r ( move disks 1..count-1 from the spare peg to the goal peg ) STH ROT ROT STHr hanoi ( restore original parameters for convenient recursion ) STH2 SWP STH2r INC JMP2r@print/str ( str* -- ) LDAk .Console/write DEO INC2 LDAk ?/str POP2 JMP2r@dict &move "Move 20 "disk 2000 &from 20 "from 20 "pole 2000 &to 20 "to 20 "pole 2000Move disk 1 from pole 1 to pole 2Move disk 2 from pole 1 to pole 3Move disk 1 from pole 2 to pole 3Move disk 3 from pole 1 to pole 2Move disk 1 from pole 3 to pole 1Move disk 2 from pole 3 to pole 2Move disk 1 from pole 1 to pole 2Move disk 4 from pole 1 to pole 3Move disk 1 from pole 2 to pole 3Move disk 2 from pole 2 to pole 1Move disk 1 from pole 3 to pole 1Move disk 3 from pole 2 to pole 3Move disk 1 from pole 1 to pole 2Move disk 2 from pole 1 to pole 3Move disk 1 from pole 2 to pole 3
Derived from the BASIC256 version.
Sub Move(n,fromPeg,toPeg,viaPeg)If n > 0 ThenMove n-1, fromPeg, viaPeg, toPegWScript.StdOut.Write "Move disk from " & fromPeg & " to " & toPegWScript.StdOut.WriteBlankLines(1)Move n-1, viaPeg, toPeg, fromPegEnd IfEnd SubMove 4,1,2,3WScript.StdOut.Write("Towers of Hanoi puzzle completed!")Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 1 to 3Move disk from 2 to 1Move disk from 2 to 3Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Move disk from 3 to 1Move disk from 2 to 1Move disk from 3 to 2Move disk from 1 to 3Move disk from 1 to 2Move disk from 3 to 2Towers of Hanoi puzzle completed!
This implementation outputs the results in current edit buffer.
#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2Call("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)}Returnfunction TowersOfHanoi(n, from, to, via) if (a:n > 1) call TowersOfHanoi(a:n-1, a:from, a:via, a:to) endif echom("Move a disc from " . a:from . " to " . a:to) if (a:n > 1) call TowersOfHanoi(a:n-1, a:via, a:to, a:from) endifendfunctioncall TowersOfHanoi(4, 1, 3, 2)Move a disc from 1 to 2Move a disc from 1 to 3Move a disc from 2 to 3Move a disc from 1 to 2Move a disc from 3 to 1Move a disc from 3 to 2Move a disc from 1 to 2Move a disc from 1 to 3Move a disc from 2 to 3Move a disc from 2 to 1Move a disc from 3 to 1Move a disc from 2 to 3Move a disc from 1 to 2Move a disc from 1 to 3Move a disc from 2 to 3
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 SubEnd Modulefn main() {hanoi(4, "A", "B", "C")}fn hanoi(n u64, 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) }}Move disk from A to BMove disk from A to CMove disk from B to CMove disk from A to BMove disk from C to AMove disk from C to BMove disk from A to BMove disk from A to CMove disk from B to CMove disk from B to AMove disk from C to AMove disk from B to CMove disk from A to BMove disk from A to CMove disk from B to C
VTL-2 doesn't have procedure parameters, so this stacks and unstacks the return line number and parameters as reuired. The "move" routune starts at line 2000, the routine at 4000 stacks the return line number and parameters for "move" and the routine at 5000 unstacks the return line number and parameters.
1000 N=41010 F=11020 T=21030 V=31040 S=01050 #=20001060 #=99992000 R=!2010 #=N<1*22102020 #=40002030 N=N-12040 A=T2050 T=V2060 V=A2070 #=20002080 #=50002090 ?="Move disk from peg: ";2100 ?=F2110 ?=" to peg: ";2120 ?=T2130 ?=""2140 #=40002150 N=N-12160 A=F2170 F=V2180 V=A2190 #=20002200 #=50002210 #=R4000 S=S+14010 :S)=R4020 S=S+14030 :S)=N4040 S=S+14050 :S)=F4060 S=S+14070 :S)=V4080 S=S+14090 :S)=T4100 #=!5000 T=:S)5010 S=S-15020 V=:S)5030 S=S-15040 F=:S)5050 S=S-15060 N=:S)5070 S=S-15080 R=:S)5090 S=S-15100 #=!
Move disk from peg: 1 to peg: 3Move disk from peg: 1 to peg: 2Move disk from peg: 3 to peg: 2Move disk from peg: 1 to peg: 3Move disk from peg: 2 to peg: 1Move disk from peg: 2 to peg: 3Move disk from peg: 1 to peg: 3Move disk from peg: 1 to peg: 2Move disk from peg: 3 to peg: 2Move disk from peg: 3 to peg: 1Move disk from peg: 2 to peg: 1Move disk from peg: 3 to peg: 2Move disk from peg: 1 to peg: 3Move disk from peg: 1 to peg: 2Move disk from peg: 3 to peg: 2
class Hanoi { construct new(disks) { _moves = 0 System.print("Towers of Hanoi with %(disks) disks:\n") move(disks, "L", "C", "R") System.print("\nCompleted in %(_moves) moves\n") } move(n, from, to, via) { if (n > 0) { move(n - 1, from, via, to) _moves = _moves + 1 System.print("Move disk %(n) from %(from) to %(to)") move(n - 1, via, to, from) } }}Hanoi.new(3)Hanoi.new(4)Towers of Hanoi with 3 disks:Move disk 1 from L to CMove disk 2 from L to RMove disk 1 from C to RMove disk 3 from L to CMove disk 1 from R to LMove disk 2 from R to CMove disk 1 from L to CCompleted in 7 movesTowers of Hanoi with 4 disks:Move disk 1 from L to RMove disk 2 from L to CMove disk 1 from R to CMove disk 3 from L to RMove disk 1 from C to LMove disk 2 from C to RMove disk 1 from L to RMove disk 4 from L to CMove disk 1 from R to CMove disk 2 from R to LMove disk 1 from C to LMove disk 3 from R to CMove disk 1 from L to RMove disk 2 from L to CMove disk 1 from R to CCompleted in 15 moves
PROGRAM"Hanoi"VERSION"0.0000"DECLARE FUNCTION Entry ()DECLARE FUNCTION Hanoi(n, desde , hasta, via)FUNCTION Entry ()PRINT "Three disks\n"Hanoi (3, 1, 2, 3)PRINT "\nFour discks\n"Hanoi (4, 1, 2, 3)PRINT "\nTowers of Hanoi puzzle completed!"END FUNCTIONFUNCTION Hanoi (n, desde , hasta, via) IF n > 0 THEN Hanoi (n - 1, desde, via, hasta) PRINT "Move disk"; n; " from pole"; desde; " to pole"; hasta Hanoi (n - 1, via, hasta, desde) END IFEND FUNCTIONEND PROGRAM
Same as FreeBASIC entry.
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")
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.
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><?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>
<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>
sub hanoi(ndisks, startPeg, endPeg) if ndisks then hanoi(ndisks-1, startPeg, 6-startPeg-endPeg) //print "Move disk ", ndisks, " from ", startPeg, " to ", endPeg hanoi(ndisks-1, 6-startPeg-endPeg, endPeg) end ifend subprint "Be patient, please.\n\n"print "Hanoi 1 ellapsed ... ";t1 = peek("millisrunning")hanoi(22, 1, 3)t2 = peek("millisrunning")print t2-t1, " ms"sub hanoi2(n, from, to_, via) if n = 1 then//print "Move from ", from, " to ", to_ elsehanoi2(n - 1, from, via , to_ ) hanoi2(1 , from, to_ , via ) hanoi2(n - 1, via , to_ , from) end ifend subprint "Hanoi 2 ellapsed ... ";hanoi2(22, 1, 3, 2)print peek("millisrunning") - t2, " ms"Use the /S8 switch on the ZSM4 assembler for 8 significant characters for labels and names
;; Towers of Hanoi using Z80 assembly language;; Runs under CP/M 3.1 on YAZE-AG-2.51.2 Z80 emulator; Assembled with zsm4 on same emulator/OS, uses macro capabilities of said assembler; Created with vim under Windows;; 2023-05-29 Xorph;;; Useful definitions;bdosequ 05h; Call to CP/M BDOS functionstrdelequ 6eh; Set string delimiterwrtstrequ 09h; Write string to consolenulequ 00h; ASCII control characterscrequ 0dhlfequ 0ahcnullequ '0'; ASCII character constantscaequ 'A'cbequ 'B'ccequ 'C'disksequ 4; Number of disks to move;; Macros for BDOS calls;setdel macrochar; Set string delimiter to charldc,strdellde,charcallbdosendmprint macromsg; Output string to consoleldc,wrtstrldde,msgcallbdosendmpushallmacro; Save required registers to stackpushafpushbcpushdeendmpopallmacro; Recall required registers from stackpopdepopbcpopafendm;; =====================; Start of main program; =====================;csegsetdelnul; Set string delimiter to 00hlda,disks; Initialization:ldb,ca; Tower A is sourceldc,cb; Tower B is targetldd,cc; Tower C is intermediatehanoi:;; Parameters in registers:; Move a disks from b (source) to c (target) via d (intermediate);ora; If 0 disks to move, returnretzdeca; Move all but lowest disk from source to intermediate via targetpushall; Save registerslde,c; Exchange c and d (target and intermediate)ldc,dldd,ecallhanoi; First recursionpopall; Restore registersldhl,source; Print move of lowest disk from source to target, save registers during BDOS callld(hl),b; Source is still in bldhl,targetld(hl),c; Target is back in c due to popallpushallprintmovementpopalllde,b; Now move stack from intermediate to target via sourceldb,d; Source is still in b, target in c and intermediate in dldd,ejrhanoi; Optimize tail recursion;; ================; Data definitions; ================;dsegmovement:defb'Move disk from tower 'source:defs1defb' to tower 'target:defs1crlf:defbcr,lf,nul
E>hanoiMove disk from tower A to tower CMove disk from tower A to tower BMove disk from tower C to tower BMove disk from tower A to tower CMove disk from tower B to tower AMove disk from tower B to tower CMove disk from tower A to tower CMove disk from tower A to tower BMove disk from tower C to tower BMove disk from tower C to tower AMove disk from tower B to tower AMove disk from tower C to tower BMove disk from tower A to tower CMove disk from tower A to tower BMove disk from tower C to tower BE>
const std = @import("std");pub fn print(from: u32, to: u32) void { std.log.info("Moving disk from rod {} to rod {}", .{ from, to });}pub fn move(n: u32, from: u32, via: u32, to: u32) void { if (n > 1) { move(n - 1, from, to, via); print(from, to); move(n - 1, via, from, to); } else { print(from, to); }}pub fn main() !void { move(4, 1, 2, 3);}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);Move disk from pole 1 to pole 2Move disk from pole 1 to pole 3Move disk from pole 2 to pole 3Move disk from pole 1 to pole 2Move disk from pole 3 to pole 1Move disk from pole 3 to pole 2Move disk from pole 1 to pole 2