Towers of Hanoi: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:25, 16 March 2013

In this task, the goal is to solve the Towers of Hanoi problem with recursion.

<lang AutoIt>Func move($n, $from, $to, $via) If ($n = 1) Then ConsoleWrite(StringFormat("Move disk from pole "&$from&" To pole "&$to&"\n")) Else move($n - 1, $from, $via, $to) move(1, $from, $to, $via) move($n - 1, $via, $to, $from) EndIf EndFunc

move(4, 1,2,3)</lang>

AWK

Translation of: Logo

<lang AWK>$ awk 'func hanoi(n,f,t,v){if(n>0){hanoi(n-1,f,v,t);print(f,"->",t);hanoi(n-1,v,t,f)}} BEGIN{hanoi(4,"left","middle","right")}'</lang>

Output:

left -> right
left -> middle
right -> middle
left -> right
middle -> left
middle -> right
left -> right
left -> middle
right -> middle
right -> left
middle -> left
right -> middle
left -> right
left -> middle
right -> middle

BASIC

Works with: FreeBASIC

Works with: RapidQ

<lang freebasic>SUB move (n AS Integer, fromPeg AS Integer, toPeg AS Integer, viaPeg AS Integer)

   IF n>0 THEN
       move n-1, fromPeg, viaPeg, toPeg
       PRINT "Move disk from "; fromPeg; " to "; toPeg
       move n-1, viaPeg, toPeg, fromPeg
   END IF

END SUB

move 4,1,2,3</lang> Here's an example of implementing recursion in an old BASIC that only has global variables:

Works with: Commodore BASIC

<lang freebasic>10 DIM N(1024), F(1024), T(1024), V(1024): REM STACK PER PARAMETER 20 SP = 0: REM STACK POINTER 30 N(SP) = 4: REM START WITH 4 DISCS 40 F(SP) = 1: REM ON PEG 1 50 T(SP) = 2: REM MOVE TO PEG 2 60 V(SP) = 3: REM VIA PEG 3 70 GOSUB 100 80 END 90 REM MOVE SUBROUTINE 100 IF N(SP) = 0 THEN RETURN 110 OS = SP: REMEMBER STACK POINTER 120 SP = SP + 1: REM INCREMENT STACK POINTER 130 N(SP) = N(OS) - 1: REM MOVE N-1 DISCS 140 F(SP) = F(OS) : REM FROM START PEG 150 T(SP) = V(OS) : REM TO VIA PEG 160 V(SP) = T(OS) : REM VIA TO PEG 170 GOSUB 100 180 OS = SP - 1: REM OS WILL HAVE CHANGED 190 PRINT "MOVE DISC FROM"; F(OS); "TO"; T(OS) 200 N(SP) = N(OS) - 1: REM MOVE N-1 DISCS 210 F(SP) = V(OS) : REM FROM VIA PEG 220 T(SP) = T(OS) : REM TO DEST PEG 230 V(SP) = F(OS) : REM VIA FROM PEG 240 GOSUB 100 250 SP = SP - 1 : REM RESTORE STACK POINTER FOR CALLER 260 RETURN</lang>

BASIC256

<lang BASIC256>call move(4,1,2,3) print "Towers of Hanoi puzzle completed!" end

subroutine move (n, fromPeg, toPeg, viaPeg)

   if n>0 then
       call move(n-1, fromPeg, viaPeg, toPeg)
       print "Move disk from "+fromPeg+" to "+toPeg
       call move(n-1, viaPeg, toPeg, fromPeg)
   end if

end subroutine</lang>

Output:
Move disk from 1 to 3
Move disk from 1 to 2
Move disk from 3 to 2
Move disk from 1 to 3
Move disk from 2 to 1
Move disk from 2 to 3
Move disk from 1 to 3
Move disk from 1 to 2
Move disk from 3 to 2
Move disk from 3 to 1
Move disk from 2 to 1
Move disk from 3 to 2
Move disk from 1 to 3
Move disk from 1 to 2
Move disk from 3 to 2
Towers of Hanoi puzzle completed!

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> DIM Disc$(13),Size%(3)

     FOR disc% = 1 TO 13
       Disc$(disc%) = STRING$(disc%," ")+STR$disc%+STRING$(disc%," ")
       IF disc%>=10 Disc$(disc%) = MID$(Disc$(disc%),2)
       Disc$(disc%) = CHR$17+CHR$(128+disc%-(disc%>7))+Disc$(disc%)+CHR$17+CHR$128
     NEXT disc%
     
     MODE 3
     OFF
     ndiscs% = 13
     FOR n% = ndiscs% TO 1 STEP -1
       PROCput(n%,1)
     NEXT
     INPUT TAB(0,0) "Press Enter to start" dummy$
     PRINT TAB(0,0) SPC(20);
     PROChanoi(ndiscs%,1,2,3)
     VDU 30
     END
     
     DEF PROChanoi(a%,b%,c%,d%)
     IF a%=0 ENDPROC
     PROChanoi(a%-1,b%,d%,c%)
     PROCtake(a%,b%)
     PROCput(a%,c%)
     PROChanoi(a%-1,d%,c%,b%)
     ENDPROC
     
     DEF PROCput(disc%,peg%)
     PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))Disc$(disc%);
     Size%(peg%) = Size%(peg%)+1
     ENDPROC
     
     DEF PROCtake(disc%,peg%)
     Size%(peg%) = Size%(peg%)-1
     PRINTTAB(13+26*(peg%-1)-disc%,20-Size%(peg%))STRING$(2*disc%+1," ");
     ENDPROC</lang>

Bracmat

<lang bracmat>( ( move

 =   n from to via
   .   !arg:(?n,?from,?to,?via)
     & (   !n:>0
         & move$(!n+-1,!from,!via,!to)
         & out$("Move disk from pole " !from " to pole " !to)
         & move$(!n+-1,!via,!to,!from)
       | 
       )
 )

& move$(4,1,2,3) );</lang> Output:

Move disk from pole  1  to pole  3
Move disk from pole  1  to pole  2
Move disk from pole  3  to pole  2
Move disk from pole  1  to pole  3
Move disk from pole  2  to pole  1
Move disk from pole  2  to pole  3
Move disk from pole  1  to pole  3
Move disk from pole  1  to pole  2
Move disk from pole  3  to pole  2
Move disk from pole  3  to pole  1
Move disk from pole  2  to pole  1
Move disk from pole  3  to pole  2
Move disk from pole  1  to pole  3
Move disk from pole  1  to pole  2
Move disk from pole  3  to pole  2

C

<lang c>#include <stdio.h>

void move(int n, int from, int to, int via) {

 if (n > 0) {
   move(n - 1, from, via, to);
   printf("Move disk from pole %d to pole %d\n", from, to);
   move(n - 1, via, to, from);
 }

} int main() {

 move(4, 1,2,3);
 return 0;

}</lang>

Animate it for fun:<lang c>#include <stdio.h>

include <stdlib.h>
include <unistd.h>

typedef struct { int *x, n; } tower; tower *new_tower(int cap) { tower *t = calloc(1, sizeof(tower) + sizeof(int) * cap); t->x = (int*)(t + 1); return t; }

tower *t[3]; int height;

void text(int y, int i, int d, const char *s) { printf("\033[%d;%dH", height - y + 1, (height + 1) * (2 * i + 1) - d); while (d--) printf("%s", s); }

void add_disk(int i, int d) { t[i]->x[t[i]->n++] = d; text(t[i]->n, i, d, "==");

usleep(100000); fflush(stdout); }

int remove_disk(int i) { int d = t[i]->x[--t[i]->n]; text(t[i]->n + 1, i, d, " "); return d; }

void move(int n, int from, int to, int via) { if (!n) return;

move(n - 1, from, via, to); add_disk(to, remove_disk(from)); move(n - 1, via, to, from); }

int main(int c, char *v[]) { puts("\033[H\033[J");

if (c <= 1 || (height = atoi(v[1])) <= 0) height = 8; for (c = 0; c < 3; c++) t[c] = new_tower(height); for (c = height; c; c--) add_disk(0, c);

move(height, 0, 2, 1);

text(1, 0, 1, "\n"); return 0; }</lang>

C#

<lang csharp>public void move(int n, int from, int to, int via) {

  if (n == 1) {
    System.Console.WriteLine("Move disk from pole " + from + " to pole " + to);
  } else {
    move(n - 1, from, via, to);
    move(1, from, to, via);
    move(n - 1, via, to, from);
  }
}</lang>

C++

Works with: g++

<lang cpp>void move(int n, int from, int to, int via) {

 if (n == 1) {
   std::cout << "Move disk from pole " << from << " to pole " << to << std::endl;
 } else {
   move(n - 1, from, via, to);
   move(1, from, to, via);
   move(n - 1, via, to, from);
 }

}</lang>

Clojure

<lang lisp>(defn towers-of-hanoi [n from to via]

 (if (= n 1)
   (println (format "Move from %s to %s" from to))
   (do
     (towers-of-hanoi (dec n) from via to)
     (println (format "Move from %s to %s" from to))
     (recur (dec n) via to from))))</lang>

CoffeeScript

<lang coffeescript>hanoi = (ndisks, start_peg=1, end_peg=3) ->

 if ndisks
   staging_peg = 1 + 2 + 3 - start_peg - end_peg
   hanoi(ndisks-1, start_peg, staging_peg)
   console.log "Move disk #{ndisks} from peg #{start_peg} to #{end_peg}"
   hanoi(ndisks-1, staging_peg, end_peg)

hanoi(4)</lang>

Common Lisp

<lang lisp>(defun move (n from to via)

 (cond ((= n 1)
        (format t "Move from ~A to ~A.~%" from to))
       (t
        (move (- n 1) from via to)
        (format t "Move from ~A to ~A.~%" from to)
        (move (- n 1) via to from))))</lang>

Emacs Lisp

Translation of: Common Lisp

<lang lisp> (defun move (n from to via)

 (cond ((= n 1)
        (print (format "Move from %S to %S" from to)))
       (t

(progn (move (- n 1) from via to) (print (format "Move from %S to %S" from to)) (move (- n 1) via to from))))) </lang>

D

Recursive Version

<lang d>import std.stdio;

void hanoi(in int n, in char from, in char to, in char via) {

   if (n > 0) {
       hanoi(n - 1, from, via, to);
       writefln("Move disk %d from %s to %s", n, from, to);
       hanoi(n - 1, via, to, from);
   }

}

void main() {

   hanoi(3, 'L', 'M', 'R');

}</lang>

Output:

Move disk 1 from L to M
Move disk 2 from L to R
Move disk 1 from M to R
Move disk 3 from L to M
Move disk 1 from R to L
Move disk 2 from R to M
Move disk 1 from L to M

Fast Iterative Version

See: The shortest and "mysterious" TH algorithm <lang d>import std.stdio, std.conv, std.typetuple;

void main(in string[] args) {

   // Code found and then improved by Glenn C. Rhoads,
   // then some more by M. Kolar (2000).

   immutable size_t n = (args.length > 1) ? to!size_t(args[1]) : 3;
   size_t[3] p = [(1 << n) - 1, 0, 0];

   printf("\n|");
   foreach_reverse (size_t i; 1 .. n + 1)
       printf(" %zd", i);
   printf("\n|\n|\n");

   foreach (size_t x; 1 .. (1 << n)) {
       {
           immutable size_t i1 = x & (x - 1);
           immutable size_t fr = (i1 + i1 / 3) & 3;
           immutable size_t i2 = (x | (x - 1)) + 1;
           immutable size_t to = (i2 + i2 / 3) & 3;

           size_t j = 1;
           for (int w = x; !(w & 1); w >>= 1, j <<= 1) {}

           // Now j is not the number of the disk to move,
           // it contains the single bit to be moved:
           p[fr] &= ~j;
           p[to] |= j;
       }

       foreach (immutable(size_t) k; TypeTuple!(0, 1, 2)) {
           printf("\n|");
           size_t j = 1 << n;
           foreach_reverse (size_t w; 1 .. n + 1) {
               j >>= 1;
               if (j & p[k])
                   printf(" %zd", w);
           }
       }

       putchar('\n');
   }

}</lang>

Output:

| 3 2 1
|
|

| 3 2
|
| 1

| 3
| 2
| 1

| 3
| 2 1
|

|
| 2 1
| 3

| 1
| 2
| 3

| 1
|
| 3 2

|
|
| 3 2 1

Dart

<lang dart>main() {

 moveit(from,to) {
   print("move ${from} ---> ${to}");
 }

 hanoi(height,toPole,fromPole,usePole) {
   if (height>0) {
     hanoi(height-1,usePole,fromPole,toPole);  
     moveit(fromPole,toPole);
     hanoi(height-1,toPole,usePole,fromPole);
   }
 }

 hanoi(3,3,1,2);

}</lang>

The same as above, with optional static type annotations and styled according to http://www.dartlang.org/articles/style-guide/ <lang dart>main() {

 String say(String from, String to) => "$from ---> $to";

 hanoi(int height, int toPole, int fromPole, int usePole) {
   if (height > 0) {
     hanoi(height - 1, usePole, fromPole, toPole);  
     print(say(fromPole.toString(), toPole.toString()));
     hanoi(height - 1, toPole, usePole, fromPole);
   }
 }

 hanoi(3, 3, 1, 2);

}</lang>

Output:

move 1 ---> 3
move 1 ---> 2
move 3 ---> 2
move 1 ---> 3
move 2 ---> 1
move 2 ---> 3
move 1 ---> 3

Dc

From Here

 [ # move(from, to)
    n           # print from
    [ --> ]n    # print " --> "
    p           # print to\n
    sw          # p doesn't pop, so get rid of the value
 ]sm
 
 [ # init(n)
    sw          # tuck n away temporarily
    9           # sentinel as bottom of stack
    lw          # bring n back
    1           # "from" tower's label
    3           # "to" tower's label
    0           # processed marker
 ]si
 
 [ # Move()
    lt          # push to
    lf          # push from
    lmx         # call move(from, to)
 ]sM
 
 [ # code block <d>
    ln          # push n
    lf          # push from
    lt          # push to
    1           # push processed marker 1
    ln          # push n
    1           # push 1
    -           # n - 1
    lf          # push from
    ll          # push left
    0           # push processed marker 0
 ]sd
 
 [ # code block <e>
    ln          # push n
    1           # push 1
    -           # n - 1
    ll          # push left
    lt          # push to
    0           # push processed marker 0
 ]se
 
 [ # code block <x>
    ln 1 =M
    ln 1 !=d
 ]sx
 
 [ # code block <y>
    lMx
    lex
 ]sy
 
 [ # quit()
    q           # exit the program
 ]sq
 
 [ # run()
    d 9 =q      # if stack empty, quit()
    sp          # processed
    st          # to
    sf          # from
    sn          # n
    6           #
    lf          #
    -           #
    lt          #
    -           # 6 - from - to
    sl          #
    lp 0 =x     #
    lp 0 !=y    #
    lrx         # loop
 ]sr
 
 5lix # init(n)
 lrx # run()

E

<lang e>def move(out, n, fromPeg, toPeg, viaPeg) {

   if (n.aboveZero()) {
       move(out, n.previous(), fromPeg, viaPeg, toPeg)
       out.println(`Move disk $n from $fromPeg to $toPeg.`)
       move(out, n.previous(), viaPeg, toPeg, fromPeg)
   }

}

move(stdout, 4, def left {}, def right {}, def middle {})</lang>

Erlang

 io:format("Move from ~p to ~p~n", [F, T]);

move(N, F, T, V) ->

 move(N-1, F, V, T), 
 move(1  , F, T, V),
 move(N-1, V, T, F).</lang>

Euphoria

<lang euphoria>procedure move(integer n, sequence From, sequence To, sequence Via)

   if n>0 then
       move(n-1, From, Via, To)
       printf(1, "Move disk %d from the %s pole to the %s pole\n", {n, From, To})
       move(n-1, Via, To, From)
   end if

end procedure

move(3, "left", "right", "middle")</lang>

Output:

Move disk 1 from the left pole to the right pole
Move disk 2 from the left pole to the middle pole
Move disk 1 from the right pole to the middle pole
Move disk 3 from the left pole to the right pole
Move disk 1 from the middle pole to the left pole
Move disk 2 from the middle pole to the right pole
Move disk 1 from the left pole to the right pole

F#

<lang fsharp>#light let rec hanoi num start finish =

 match num with
 | 0 -> [ ]
 | _ -> let temp = (6 - start - finish)
        (hanoi (num-1) start temp) @ [ start, finish ] @ (hanoi (num-1) temp finish)

[<EntryPoint>] let main args =

 (hanoi 4 1 2) |> List.iter (fun pair -> match pair with
                                         | a, b -> printf "Move disc from %A to %A\n" a b)
 0</lang>

FALSE

<lang false>["Move disk from "$!\" to "$!\" "]p: { to from } [n;0>[n;1-n: @\ h;! @\ p;! \@ h;! \@ n;1+n:]?]h: { via to from } 4n:["right"]["middle"]["left"]h;!%%%</lang>

Factor

<lang factor>USING: formatting kernel locals math ; IN: rosettacode.hanoi

move ( from to -- )

   "%d->%d\n" printf ;

hanoi ( n from to other -- )

   n 0 > [
       n 1 - from other to hanoi
       from to move
       n 1 - other to from hanoi
   ] when ;</lang>

In the REPL:

( scratchpad ) 3 1 3 2 hanoi
1->3
1->2
3->2
1->3
2->1
2->3
1->3

Forth

With locals: <lang forth>CREATE peg1 ," left " CREATE peg2 ," middle " CREATE peg3 ," right "

.$ COUNT TYPE ;

MOVE-DISK

 LOCALS| via to from n | 
 n 1 =
 IF   CR ." Move disk from " from .$ ." to " to .$ 
 ELSE n 1- from via to RECURSE 
      1    from to via RECURSE 
      n 1- via to from RECURSE 
 THEN ;</lang>

Without locals, executable pegs: <lang forth>: left ." left" ;

right ." right" ;

middle ." middle" ;

move-disk ( v t f n -- v t f )

 dup 0= if drop exit then
 1-       >R
 rot swap R@ ( t v f n-1 ) recurse
 rot swap
 2dup cr ." Move disk from " execute ."  to " execute
 swap rot R> ( f t v n-1 ) recurse
 swap rot ;

hanoi ( n -- )

 1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ;</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>PROGRAM TOWER

 CALL Move(4, 1, 2, 3)

CONTAINS

 RECURSIVE SUBROUTINE Move(ndisks, from, to, via)
   INTEGER, INTENT (IN) :: ndisks, from, to, via
  
   IF (ndisks == 1) THEN
      WRITE(*, "(A,I1,A,I1)") "Move disk from pole ", from, " to pole ", to
   ELSE
      CALL Move(ndisks-1, from, via, to)
      CALL Move(1, from, to, via)
      CALL Move(ndisks-1, via, to, from)
   END IF
 END SUBROUTINE Move

END PROGRAM TOWER</lang>

GAP

<lang gap>Hanoi := function(n) local move; move := function(n, a, b, c) # from, through, to if n = 1 then Print(a, " -> ", c, "\n"); else move(n - 1, a, c, b); move(1, a, b, c); move(n - 1, b, a, c); fi; end; move(n, "A", "B", "C"); end;

Hanoi(1);

A -> C

Hanoi(2);

A -> B
A -> C
B -> C

Hanoi(3);

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C</lang>

Go

<lang go>package main

import "fmt"

// a towers of hanoi solver just has one method, play type solver interface {

   play(int)

}

func main() {

   var t solver    // declare variable of solver type
   t = new(towers) // type towers must satisfy solver interface
   t.play(4)

}

// towers is example of type satisfying solver interface type towers struct {

   // an empty struct.  some other solver might fill this with some
   // data representation, maybe for algorithm validation, or maybe for
   // visualization.

}

// play is sole method required to implement solver type func (t *towers) play(n int) {

   // drive recursive solution, per task description
   t.moveN(n, 1, 2, 3)

}

// recursive algorithm func (t *towers) moveN(n, from, to, via int) {

   if n > 0 {
       t.moveN(n-1, from, via, to)
       t.move1(from, to)
       t.moveN(n-1, via, to, from)
   }

}

// example function prints actions to screen. // enhance with validation or visualization as needed. func (t *towers) move1(from, to int) {

   fmt.Println("move disk from rod", from, "to rod", to)

}</lang>

In other words:

<lang go>package main

import "fmt"

func main() { move(3, "A", "B", "C") }

func move(n uint64, a, b, c string) { if n > 0 { move(n-1, a, c, b) fmt.Println("Move disk from " + a + " to " + c) move(n-1, b, a, c) } }</lang>

Groovy

Unlike most solutions here this solution manipulates more-or-less actual stacks of more-or-less actual rings. <lang groovy>def tail = { list, n -> def m = list.size(); list[([m - n, 0].max())..<m] }

final STACK = [A:[],B:[],C:[]].asImmutable()

def report = { it -> } def check = { it -> }

def moveRing = { from, to -> to << from.pop(); report(); check(to) }

def moveStack moveStack = { from, to, using = STACK.values().find { !(it.is(from) || it.is(to)) } ->

   if (!from) return
   def n = from.size()
   moveStack(tail(from, n-1), using, to)
   moveRing(from, to)
   moveStack(tail(using, n-1), to, from)

}</lang> Test program: <lang groovy>enum Ring {

   S('°'), M('o'), L('O'), XL('()');
   private sym
   private Ring(sym) { this.sym=sym }
   String toString() { sym }

}

report = { STACK.keySet().each { println "${it}: ${STACK[it]}" }; println() } check = { to -> assert to == ([] + to).sort().reverse() }

Ring.values().reverseEach { STACK.A << it } report() check(STACK.A) moveStack(STACK.A, STACK.C)</lang>

Haskell

Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c: <lang haskell>hanoi :: Integer -> a -> a -> a -> [(a, a)] hanoi 0 _ _ _ = [] hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a</lang> One can use this function to produce output, just like the other programs: <lang haskell>hanoiIO n = mapM_ f $ hanoi n 1 2 3 where

 f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y</lang>

Or, instead one can of course also program imperatively, using the IO monad directly: <lang haskell>hanoiM :: Integer -> IO () hanoiM n = hanoiM' n 1 2 3 where

 hanoiM' 0 _ _ _ = return ()
 hanoiM' n a b c = do
   hanoiM' (n-1) a c b
   putStrLn $ "Move " ++ show a ++ " to " ++ show b
   hanoiM' (n-1) c b a</lang>

Icon and Unicon

The following is based on a solution in the Unicon book. <lang Icon>procedure main(arglist) hanoi(arglist[1]) | stop("Usage: hanoi n\n\rWhere n is the number of disks to move.") end

procedure hanoi(n:integer, needle1:1, needle2:2) # unicon shorthand for icon code 1,2,3 below

procedure hanoi(n, needle1, needle2) #: solve towers of hanoi by moving n disks from needle 1 to needle2 via other local other

n := integer(0 < n) | runerr(n,101) # 1 ensure integer (this also ensures it's positive too) /needle1 := 1 # 2 default /needle2 := 2 # 3 default

if n = 1 then

  write("Move disk from ", needle1, " to ", needle2)

else {

  other := 6 - needle1 - needle2         # clever but somewhat un-iconish way to find other
  hanoi(n-1, needle1, other)             
  write("Move disk from ", needle1, " to ", needle2)
  hanoi(n-1, other, needle2)

} return end</lang>

Inform 7

<lang inform7>Hanoi is a room.

A disk is a kind of supporter.

A post is a kind of supporter. A post is always fixed in place.

The left post, the middle post, and the right post are posts in Hanoi.

A disk is a kind of supporter. The red disk is a disk on the left post. The orange disk is a disk on the red disk. The yellow disk is a disk on the orange disk. The green disk is a disk on the yellow disk.

Definition: a disk is topmost if nothing is on it.

When play begins: move 4 disks from the left post to the right post via the middle post.

To move (N - number) disk/disks from (FP - post) to (TP - post) via (VP - post): if N > 0: move N - 1 disks from FP to VP via TP; say "Moving a disk from [FP] to [TP]..."; let D be a random topmost disk enclosed by FP; if a topmost disk (called TD) is enclosed by TP, now D is on TD; otherwise now D is on TP; move N - 1 disks from VP to TP via FP.</lang>

Io

<lang io>hanoi := method(n, from, to, via,

 if (n == 1) then (
   writeln("Move from ", from, " to ", to)
 ) else (
   hanoi(n - 1, from, via, to  )
   hanoi(1    , from, to , via )
   hanoi(n - 1, via , to , from)
 )

)</lang>

Ioke

<lang ioke> = method(n, f, u, t,

 if(n < 2,
   "#{f} --> #{t}" println,

   H(n - 1, f, t, u)
   "#{f} --> #{t}" println
   H(n - 1, u, f, t)
 )

)

hanoi = method(n,

 H(n, 1, 2, 3)

)</lang>

J

Solutions <lang j>H =: i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * NB. tacit using anonymous recursion</lang>

Example use:

<lang j> H 3 0 2 0 1 2 1 0 2 1 2 1 0 2 0</lang> The result is a 2-column table; a row i,j is interpreted as: move a disk (the top disk) from peg i to peg j . Or, using explicit rather than implicit code: <lang j>H1=: monad define NB. explicit equivalent of H

 if. y do.
   ({&0 2 1 , 0 2 , {&1 0 2) H1 y-1
 else.
   i.0 2
 end.

)</lang> The usage here is the same:

Alternative solution

If a textual display is desired, similar to some of the other solutions here (counting from 1 instead of 0, tracking which disk is on the top of the stack, and of course formatting the result for a human reader instead of providing a numeric result): <lang J>hanoi=: monad define

 moves=. H y
 disks=.  $~` ((],[,]) $:@<:) @.* y
 ('move disk ';' from peg ';' to peg ');@,."1 ":&.>disks,.1+moves

)</lang>

Demonstration:

<lang J> hanoi 3 move disk 1 from peg 1 to peg 3 move disk 2 from peg 1 to peg 2 move disk 1 from peg 3 to peg 2 move disk 3 from peg 1 to peg 3 move disk 1 from peg 2 to peg 1 move disk 2 from peg 2 to peg 3 move disk 1 from peg 1 to peg 3</lang>

Java

<lang java>public void move(int n, int from, int to, int via) {

 if (n == 1) {
   System.out.println("Move disk from pole " + from + " to pole " + to);
 } else {
   move(n - 1, from, via, to);
   move(1, from, to, via);
   move(n - 1, via, to, from);
 }

}</lang>

JavaScript

<lang javascript>function move(n, a, b, c) { if (n > 0) { move(n-1, a, c, b); console.log("Move disk from " + a + " to " + c); move(n-1, b, a, c); } } move(4, "A", "B", "C");</lang>

Joy

From here <lang joy>DEFINE hanoi == [[rolldown] infra] dip

               [ [ [null] [pop pop] ] 
                 [ [dup2 [[rotate] infra] dip pred] 
                   [ [dup rest put] dip 
                     [[swap] infra] dip pred ] 
                   [] ] ] 
               condnestrec.</lang>

Using it (5 is the number of disks.) <lang joy>[source destination temp] 5 hanoi.</lang>

K

<lang K> h:{[n;a;b;c]if[n>0;_f[n-1;a;c;b];`0:,//$($n,":",$a,"->",$b,"\n");_f[n-1;c;b;a]]}

  h[4;1;2;3]

1:1->3 2:1->2 1:3->2 3:1->3 1:2->1 2:2->3 1:1->3 4:1->2 1:3->2 2:3->1 1:2->1 3:3->2 1:1->3 2:1->2 1:3->2</lang> The disk to move in the i'th step is the same as the position of the leftmost 1 in the binary representation of 1..2^n. <lang K> s:();{[n;a;b;c]if[n>0;_f[n-1;a;c;b];s,:n;_f[n-1;c;b;a]]}[4;1;2;3];s 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

  1_{*1+&|x}'a:(2_vs!_2^4)

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1</lang>

Liberty BASIC

This looks much better with a GUI interface. <lang lb> source$ ="A"

   via$    ="B"
   target$ ="C"

   call hanoi 4, source$, target$, via$        '   ie call procedure to move legally 4 disks from peg A to peg C via peg B

   wait

   sub hanoi numDisks, source$, target$, via$
       if numDisks =0 then
           exit sub
       else
           call hanoi numDisks -1, source$, via$, target$
           print " Move disk "; numDisks; " from peg "; source$; " to peg "; target$
           call hanoi numDisks -1, via$, target$, source$
       end if
   end sub

   end</lang>

Logo

<lang logo>to move :n :from :to :via

 if :n = 0 [stop]
 move :n-1 :from :via :to
 (print [Move disk from] :from [to] :to)
 move :n-1 :via :to :from

end move 4 "left "middle "right</lang>

Logtalk

<lang logtalk>:- object(hanoi).

   :- public(run/1).
   :- mode(run(+integer), one).
   :- info(run/1, [
       comment is 'Solves the towers of Hanoi problem for the specified number of disks.',
       argnames is ['Disks']]).

   run(Disks) :-
       move(Disks, left, middle, right).

   move(1, Left, _, Right):-
       !,
       report(Left, Right).
   move(Disks, Left, Aux, Right):-
       Disks2 is Disks - 1,
       move(Disks2, Left, Right, Aux),
       report(Left, Right),
       move(Disks2, Aux, Left, Right).

   report(Pole1, Pole2):-
       write('Move a disk from '),
       writeq(Pole1),
       write(' to '),
       writeq(Pole2),
       write('.'),
       nl.

- end_object.</lang>

Lua

<lang Lua>function move(n, src, dst, via)

   if n > 0 then
       move(n - 1, src, via, dst)
       print(src, 'to', dst)
       move(n - 1, via, dst, src)
   end

end

move(4, 1, 2, 3)</lang>

Mathematica

<lang mathematica>Hanoi[0, from_, to_, via_] := Null Hanoi[n_Integer, from_, to_, via_] :=

 (Hanoi[n-1, from, via, to];
  Print["Move disk from pole ", from, " to ", to, "."];
  Hanoi[n-1, via, from, to])</lang>

MATLAB

This is a direct translation from the Python example given in the Wikipedia entry for the Tower of Hanoi puzzle. <lang MATLAB>function towerOfHanoi(n,A,C,B)

   if (n~=0)
       towerOfHanoi(n-1,A,B,C);
       disp(sprintf('Move plate %d from tower %d to tower %d',[n A C]));
       towerOfHanoi(n-1,B,C,A);
   end

end</lang>

Sample output:

<lang MATLAB>towerOfHanoi(3,1,3,2) Move plate 1 from tower 1 to tower 3 Move plate 2 from tower 1 to tower 2 Move plate 1 from tower 3 to tower 2 Move plate 3 from tower 1 to tower 3 Move plate 1 from tower 2 to tower 1 Move plate 2 from tower 2 to tower 3 Move plate 1 from tower 1 to tower 3</lang>

Modula-3

<lang modula3>MODULE Hanoi EXPORTS Main;

FROM IO IMPORT Put; FROM Fmt IMPORT Int;

PROCEDURE doHanoi(n, from, to, using: INTEGER) =

 BEGIN
   IF n > 0 THEN
     doHanoi(n - 1, from, using, to);
     Put("move " & Int(from) & " --> " & Int(to) & "\n");
     doHanoi(n - 1, using, to, from);
   END;
 END doHanoi;

BEGIN

 doHanoi(4, 1, 2, 3);

END Hanoi.</lang>

Nemerle

<lang Nemerle>using System; using System.Console;

module Towers {

   Hanoi(n : int, from = 1, to = 3, via = 2) : void
   {
       when (n > 0)
       {
           Hanoi(n - 1, from, via, to);
           WriteLine("Move disk from peg {0} to peg {1}", from, to);
           Hanoi(n - 1, via, to, from);
       }
   }
   
   Main() : void
   {
       Hanoi(4)
   }

}</lang>

Nimrod

<lang Python>proc hanoi(disks: int, fromTower: string, toTower: string, viaTower: string) =

 if disks != 0:
   hanoi(disks - 1, fromTower, viaTower, toTower)
   echo("Move disk ", disks, " from ", fromTower, " to ", toTower)
   hanoi(disks - 1, viaTower, toTower, fromTower)

hanoi(4, "1", "2", "3")</lang>

Output:

Move disk 1 from 1 to 3
Move disk 2 from 1 to 2
Move disk 1 from 3 to 2
Move disk 3 from 1 to 3
Move disk 1 from 2 to 1
Move disk 2 from 2 to 3
Move disk 1 from 1 to 3
Move disk 4 from 1 to 2
Move disk 1 from 3 to 2
Move disk 2 from 3 to 1
Move disk 1 from 2 to 1
Move disk 3 from 3 to 2
Move disk 1 from 1 to 3
Move disk 2 from 1 to 2
Move disk 1 from 3 to 2

NewLISP

<lang lisp>(define (move n from to via) (if (> n 0) (move (- n 1) from via to (print "move disk from pole " from " to pole " to "\n") (move (- n 1) via to from))))

(move 4 1 2 3)</lang>

Objective-C

From here

Works with: GNUstep

It should be compatible with XCode/Cocoa on MacOS too.

The Interface - TowersOfHanoi.h: <lang objc>#import <Foundation/NSObject.h>

@interface TowersOfHanoi: NSObject { int pegFrom; int pegTo; int pegVia; int numDisks; }

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks; -(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks; @end</lang> The Implementation - TowersOfHanoi.m: <lang objc>#import "TowersOfHanoi.h" @implementation TowersOfHanoi

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks { pegFrom = from; pegTo = to; pegVia = via; numDisks = disks; }

-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks { if (disks == 1) {

           printf("Move disk from pole %i to pole %i\n", from, to);
       } else {
			[self movePegFrom: from andMovePegTo: via andMovePegVia: to andWithNumDisks: disks-1];

[self movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: 1]; [self movePegFrom: via andMovePegTo: to andMovePegVia: from andWithNumDisks: disks-1];

}

@end</lang> Test code: TowersTest.m: <lang objc>#import <stdio.h>

import "TowersOfHanoi.h"

int main( int argc, const char *argv[] ) { TowersOfHanoi *tower = [[TowersOfHanoi alloc] init];

int from = 1; int to = 3; int via = 2; int disks = 3;

[tower setPegFrom: from andSetPegTo: to andSetPegVia: via andSetNumDisks: disks];

[tower movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: disks];

[tower release];

return 0; }</lang>

OCaml

<lang ocaml>let rec hanoi n a b c =

 if n <> 0 then begin
   hanoi (pred n) a c b;
   Printf.printf "Move disk from pole %d to pole %d\n" a b;
   hanoi (pred n) c b a
 end

let () =

 hanoi 4 1 2 3</lang>

Octave

<lang octave>function hanoimove(ndisks, from, to, via)

 if ( ndisks == 1 )
   printf("Move disk from pole %d to pole %d\n", from, to);
 else
   hanoimove(ndisks-1, from, via, to);
   hanoimove(1, from, to, via);
   hanoimove(ndisks-1, via, to, from);
 endif

endfunction

hanoimove(4, 1, 2, 3);</lang>

Oz

<lang oz>declare

 proc {TowersOfHanoi N From To Via}
    if N > 0 then
       {TowersOfHanoi N-1 From Via To}
       {System.showInfo "Move from "#From#" to "#To}
       {TowersOfHanoi N-1 Via To From}
    end
 end

in

 {TowersOfHanoi 4 left middle right}</lang>

Pascal

Works with: Free Pascal version 2.0.4

I think it is standard pascal, except for the constant array "strPole". I am not sure if constant arrays are part of the standard. However, as far as I know, they are a "de facto" standard in every compiler. <lang pascal>program Hanoi; type

 TPole = (tpLeft, tpCenter, tpRight);

const

 strPole:array[TPole] of string[6]=('left','center','right');

procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole);
begin
 if Ndisks >0 then begin
    MoveStack(Ndisks - 1, Origin,Auxiliary, Destination );
    Writeln('Move disk ',Ndisks ,' from ',strPole[Origin],' to ',strPole[Destination]);
    MoveStack(Ndisks - 1, Auxiliary, Destination, origin);
 end;
end;

begin

MoveStack(4,tpLeft,tpCenter,tpRight);

end.</lang> A little longer, but clearer for my taste <lang pascal>program Hanoi; type

 TPole = (tpLeft, tpCenter, tpRight);

const

 strPole:array[TPole] of string[6]=('left','center','right');

procedure MoveOneDisk(const DiskNum:integer; const Origin,Destination:TPole);
begin
 Writeln('Move disk ',DiskNum,' from ',strPole[Origin],' to ',strPole[Destination]);
end;

procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole);
begin
 if Ndisks =1 then
      MoveOneDisk(1,origin,Destination)
 else begin
      MoveStack(Ndisks - 1, Origin,Auxiliary, Destination );
      MoveOneDisk(Ndisks,origin,Destination);
      MoveStack(Ndisks - 1, Auxiliary, Destination, origin);
 end;
end;

begin

MoveStack(4,tpLeft,tpCenter,tpRight);

end.</lang>

Perl

<lang perl>sub hanoi {

   my ($n, $from, $to, $via) = (@_, 1, 2, 3);

   if ($n == 1) {
       print "Move disk from pole $from to pole $to.\n";
   } else {
       hanoi($n - 1, $from, $via, $to);
       hanoi(1, $from, $to, $via);
       hanoi($n - 1, $via, $to, $from);
   };

};</lang>

Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

<lang perl6>subset Peg of Int where * == 1|2|3;

multi hanoi (0, Peg $a, Peg $b, Peg $c) { } multi hanoi (Int $n, Peg $a = 1, Peg $b = 2, Peg $c = 3) {

   hanoi $n - 1, $a, $c, $b;
   say "Move $a to $b.";
   hanoi $n - 1, $c, $b, $a;

}</lang>

PHP

Translation of: Java

<lang php>function move($n,$from,$to,$via) {

   if ($n === 1) {
       print("Move disk from pole $from to pole $to");
   } else {
       move($n-1,$from,$via,$to);
       move(1,$from,$to,$via);
       move($n-1,$via,$to,$from);
   }

}</lang>

PicoLisp

<lang PicoLisp>(de move (N A B C) # Use: (move 3 'left 'center 'right)

  (unless (=0 N)
     (move (dec N) A C B)
     (println 'Move 'disk 'from A 'to B)
     (move (dec N) C B A) ) )</lang>

Pop11

<lang pop11>define hanoi(n, src, dst, via); if n > 0 then

   hanoi(n - 1, src, via, dst);
   'Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.' =>
   hanoi(n - 1, via, dst, src);

endif; enddefine;

hanoi(4, "left", "middle", "right");</lang>

PL/I

Translation of: Fortran

<lang PL/I>tower: proc options (main);

  call Move (4,1,2,3);

Move: procedure (ndiscs, from, to, via) recursive;

  declare (ndiscs, from, to, via) fixed binary;

  if ndiscs = 1 then
     put skip edit ('Move disc from pole ', trim(from), ' to pole ',
        trim(to) ) (a);
  else
     do;
        call Move (ndiscs-1, from, via, to);
        call Move (1, from, to, via);
        call Move (ndiscs-1, via, to, from);
     end;

end Move;

end tower;</lang>

PostScript

A million-page document, each page showing one move. <lang PostScript>%!PS-Adobe-3.0 %%BoundingBox: 0 0 300 300

/plate {

       exch 100 mul 50 add exch th mul 10 add moveto
       dup s mul neg 2 div 0 rmoveto
       dup s mul 0 rlineto
       0 th rlineto
       s neg mul 0 rlineto
       closepath gsave .5 setgray fill grestore 0 setgray stroke

} def

/drawtower {

       0 1 2 { /x exch def /y 0 def
               tower x get {
                       dup 0 gt { x y plate /y y 1 add def } {pop} ifelse
               } forall
       } for showpage

} def

/apop { [ exch aload pop /last exch def ] last } def /apush{ [ 3 1 roll aload pop counttomark -1 roll ] } def

/hanoi {

       0 dict begin /from /mid /to /h 5 -1 2 { -1 roll def } for
       h 1 eq {        
               tower from get apop tower to get apush
               tower to 3 -1 roll put
               tower from 3 -1 roll put
               drawtower
       } {     
               /h h 1 sub def
               from to mid h hanoi
               from mid to 1 hanoi
               mid from to h hanoi
       } ifelse
       end

} def

/n 12 def /s 90 n div def /th 180 n div def /tower [ [n 1 add -1 2 { } for ] [] [] ] def

drawtower 0 1 2 n hanoi

%%EOF</lang>

Prolog

From Programming in Prolog by W.F. Clocksin & C.S. Mellish <lang prolog>hanoi(N) :- move(N,left,center,right).

move(0,_,_,_) :- !. move(N,A,B,C) :-

   M is N-1,
   move(M,A,C,B),
   inform(A,B),
   move(M,C,B,A).

inform(X,Y) :- write([move,a,disk,from,the,X,pole,to,Y,pole]), nl.</lang>

PureBasic

Algorithm according to http://en.wikipedia.org/wiki/Towers_of_Hanoi <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

 If n
   Hanoi(n-1, A, B, C)
   PrintN("Move the plate from "+A+" to "+C)
   Hanoi(n-1, B, C, A)
 EndIf

EndProcedure</lang> Full program <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

 If n
   Hanoi(n-1, A, B, C)
   PrintN("Move the plate from "+A+" to "+C)
   Hanoi(n-1, B, C, A)
 EndIf

EndProcedure

If OpenConsole()

 Define n=3
 PrintN("Moving "+Str(n)+" pegs."+#CRLF$)
 Hanoi(n,"Left Peg","Middle Peg","Right Peg")
 PrintN(#CRLF$+"Press ENTER to exit."): Input()

EndIf</lang>

Output:

Moving 3 pegs.

Move the plate from Left Peg to Middle Peg
Move the plate from Left Peg to Right Peg
Move the plate from Middle Peg to Right Peg
Move the plate from Left Peg to Middle Peg
Move the plate from Right Peg to Left Peg
Move the plate from Right Peg to Middle Peg
Move the plate from Left Peg to Middle Peg

Press ENTER to exit.

Python

<lang python>def hanoi(ndisks, startPeg=1, endPeg=3):

   if ndisks:
       hanoi(ndisks-1, startPeg, 6-startPeg-endPeg)
       print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg)
       hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)

hanoi(ndisks=4)</lang>

R

Translation of: Octave

<lang R>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>

Rascal

Translation of: Python

<lang rascal>public void hanoi(ndisks, startPeg, endPeg){ if(ndisks>0){ hanoi(ndisks-1, startPeg, 6 - startPeg - endPeg); println("Move disk <ndisks> from peg <startPeg> to peg <endPeg>"); hanoi(ndisks-1, 6 - startPeg - endPeg, endPeg); } }</lang> Output <lang rascal>rascal>hanoi(4,1,3) Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 3 from peg 1 to peg 2 Move disk 1 from peg 3 to peg 1 Move disk 2 from peg 3 to peg 2 Move disk 1 from peg 1 to peg 2 Move disk 4 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 Move disk 2 from peg 2 to peg 1 Move disk 1 from peg 3 to peg 1 Move disk 3 from peg 2 to peg 3 Move disk 1 from peg 1 to peg 2 Move disk 2 from peg 1 to peg 3 Move disk 1 from peg 2 to peg 3 ok</lang>

REBOL

<lang REBOL>REBOL [ Title: "Towers of Hanoi" Author: oofoe Date: 2009-12-08 URL: http://rosettacode.org/wiki/Towers_of_Hanoi ]

hanoi: func [ {Begin moving the golden disks from one pole to the next. Note: when last disk moved, the world will end.} disks [integer!] "Number of discs on starting pole." /poles "Name poles." from to via ][

   if disks = 0 [return]

if not poles [from: 'left to: 'middle via: 'right]

   hanoi/poles disks - 1 from via to

print [from "->" to]

   hanoi/poles disks - 1 via to from

]

hanoi 4</lang>

Output:

left -> right
left -> middle
right -> middle
left -> right
middle -> left
middle -> right
left -> right
left -> middle
right -> middle
right -> left
middle -> left
right -> middle
left -> right
left -> middle
right -> middle

Retro

<lang Retro>4 elements a b c n

vars !c !b !a !n ;

hanoi ( num from to via -- )

 vars
 @n 0 <>
 [
   @n @a @b @c
   @n 1- @a @c @b hanoi
   vars
   @b @a "\nMove a ring from %d to %d" puts
   @n 1- @c @b @a hanoi
 ] ifTrue ;

4 1 3 2 hanoi</lang>

REXX

simple text moves

<lang rexx>/*REXX program to show the moves to solve the Tower of Hanoi (3 disks). */ arg z . /*get possible specification of Z*/ if z== then z=3 /*Not given? Use default 3 towers*/ move=0 /*number of ring moves so far. */ call mov 1,3,z /*move top ring, then recurse... */ say say 'The minimum number of moves to solve a' z "ring Tower of Hanoi is" 2**z-1 exit /*stick a fork in it, we're done.*/ /*─────────────────────────────MOV subroutine───────────────────────────*/ mov: procedure expose move; arg #1, #2, #3 if #3==1 then call dsk #1, #2

        else do
             call mov #1,        6-#1-#2,   #3-1
             call mov #1,        #2,        1
             call mov 6-#1-#2,   #2,        #3-1
             end

return /*─────────────────────────────DSK subroutine───────────────────────────*/ dsk: move=move+1 say 'step' right(move,length(moves))": move disk " arg(1) '──►' arg(2) return</lang>

Output:

step 1:  move disk  1 ──► 3
step 2:  move disk  1 ──► 2
step 3:  move disk  3 ──► 2
step 4:  move disk  1 ──► 3
step 5:  move disk  2 ──► 1
step 6:  move disk  2 ──► 3
step 7:  move disk  1 ──► 3

The minimum number of moves to solve a 3 ring Tower of Hanoi is 7.

output when the following was entered (to solve with four disks): 4

step  1:  move disk  1 ──► 2
step  2:  move disk  1 ──► 3
step  3:  move disk  2 ──► 3
step  4:  move disk  1 ──► 2
step  5:  move disk  3 ──► 1
step  6:  move disk  3 ──► 2
step  7:  move disk  1 ──► 2
step  8:  move disk  1 ──► 3
step  9:  move disk  2 ──► 3
step 10:  move disk  2 ──► 1
step 11:  move disk  3 ──► 1
step 12:  move disk  2 ──► 3
step 13:  move disk  1 ──► 2
step 14:  move disk  1 ──► 3
step 15:  move disk  2 ──► 3

The minimum number of moves to solve a 4 ring Tower of Hanoi is 15.

pictorial moves

This version pictorially shows the moves for solving the Town of Hanoi.

Quite a bit of code has been dedicated to showing a picture of the towers with the disks on them, and the movement of the disk (the move). Coloring of the rings is attempted with dithering.

In addition, it shows each move in a countdown manner (the last move is move #1).

No attempt is mode to explain this version of the REXX program 'cause of the complexity and somewhat obtuse features of the REXX language, the smallest of which is support for ASCII and EBCDIC "graphic" characters. It may not be obvious, but whenever a ring is moved from one tower to another, it is always the top ring that is moved. <lang rexx>/*REXX program shows pictorial moves to solve Tower of Hanoi (3 disks). */ arg z .; if z== then z=3 sw=80; wp=sw%3-1; blanks=centre(,wp) c.1=sw%3%2 c.2=sw%2-1 c.3=sw-1-c.1-1 move=0; totmoves=2**z-1; movek=totmoves; lentot=length(totmoves) @abc='abcdefghijklmnopqrstuvwxyz' ebcdic= 'f0'x==0 if ebcdic then do

              bar='bf'x;ar='df'x;boxen='db9f9caf'x;tl='ac'x;tr='bf'x;bl='ab'x;br='bb'x;vert='fa'x;down='9a'x
              end
         else do
              bar='c4'x;ar='10'x;boxen='b0b1b2db'x;tl='da'x;tr='bf'x;bl='c0'x;br='d9'x;vert='b3'x;down='19'x
              end

verts=vert || vert downs=down || down Tcorners=tl || tr Bcorners=bl || br box=left(boxen,1); boxchars=boxen || @abc bararrow=bar || bar || ar $.=0; $.1=z; k=z; kk=k+k

 do j=1 for z
 @.3.j=blanks;   @.2.j=blanks
 @.1.j=centre(copies(box,kk),wp)
 if z<=length(boxchars) then @.1.j=,
                             translate(@.1.j,substr(boxchars,kk%2,1),box)
 kk=kk-2
 end   /*j*/

call showtowers; call mov 1,3,z say say "The minimum number of moves for a" z 'ring Tower of Hanoi is' totmoves exit /*─────────────────────────────MOV subroutine───────────────────────────*/ mov: if arg(3)==1 then call rng arg(1) arg(2)

                 else do
                      call mov arg(1),6-arg(1)-arg(2),arg(3)-1
                      call mov arg(1),arg(2),1
                      call mov 6-arg(1)-arg(2),arg(2),arg(3)-1
                      end

return /*─────────────────────────────RNG subroutine───────────────────────────*/ rng: parse arg from dest; move=move+1; pp= if from==1 then do

               pp=overlay(bl,pp,c.1)
               pp=overlay(bar,pp,c.1+1,c.dest-c.1-1,bar)
               pp=pp || tr
               end

if from==3 then do

               pp=overlay(br,pp,c.3)
               pp=overlay(bar,pp,c.dest+1,c.3-c.dest-1,bar)
               pp=overlay(tl,pp,c.dest)
               end

if from==2 then do

               lpost=min(2,dest)
               hpost=max(2,dest)
               if dest==1 then do
                               pp=overlay(tl,pp,c.1)
                               pp=overlay(bar,pp,c.1+1,c.2-c.1-1,bar)
                               pp=pp || br
                               end
               if dest==3 then do
                               pp=overlay(bl,pp,c.2)
                               pp=overlay(bar,pp,c.2+1,c.3-c.2-1,bar)
                               pp=pp || tr
                               end
               end

say translate(pp,verts,Bcorners||Tcorners||bar); say overlay(movek,pp,1) say translate(pp,verts,Tcorners||Bcorners||bar) say translate(pp,downs,Tcorners||Bcorners||bar) movek=movek-1 $.from=$.from-1; $.dest=$.dest+1; _f=$.from+1; _t=$.dest @.dest._t=@.from._f; @.from._f=blanks call showtowers return /*─────────────────────────────SHOWTOWERS subroutine────────────────────*/ showtowers: do j=z to 1 by -1

             _p=@.1.j  @.2.j  @.3.j;   if _p\= then say _p
             end    /*j*/

return</lang>

Output:

           ░░
          ▒▒▒▒
         ▓▓▓▓▓▓
            │
7           └───────────────────────────────────────────────────┐
                                                                │
                                                                ↓
          ▒▒▒▒
         ▓▓▓▓▓▓                                                ░░
            │
6           └─────────────────────────┐
                                      │
                                      ↓
         ▓▓▓▓▓▓                     ▒▒▒▒                       ░░
                                                                │
5                                     ┌─────────────────────────┘
                                      │
                                      ↓
                                     ░░
         ▓▓▓▓▓▓                     ▒▒▒▒
            │
4           └───────────────────────────────────────────────────┐
                                                                │
                                                                ↓
                                     ░░
                                    ▒▒▒▒                     ▓▓▓▓▓▓
                                      │
3           ┌─────────────────────────┘
            │
            ↓
           ░░                       ▒▒▒▒                     ▓▓▓▓▓▓
                                      │
2                                     └─────────────────────────┐
                                                                │
                                                                ↓
                                                              ▒▒▒▒
           ░░                                                ▓▓▓▓▓▓
            │
1           └───────────────────────────────────────────────────┐
                                                                │
                                                                ↓
                                                               ░░
                                                              ▒▒▒▒
                                                             ▓▓▓▓▓▓

The minimum number of moves for a 3 ring Tower of Hanoi is 7

Ruby

<lang ruby>def move(num_disks, starting_stick, target_stick, using_stick)

 if num_disks == 1
   target_stick << starting_stick.shift
   status
 else
   move(num_disks-1, starting_stick, using_stick, target_stick)
   move(1, starting_stick, target_stick, using_stick)
   move(num_disks-1, using_stick, target_stick, starting_stick)
 end

end</lang>

<lang ruby> require 'pp'

solve(source, via, target)
Example:
solve([5, 4, 3, 2, 1], [], [])
Note this will also solve randomly placed disks.

def solve(*towers)

 # total number of disks
 disks = towers.inject(0){|sum, tower| sum+tower.length}
 x=0 # sequence number
 pp 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)
       pp towers # trace
     end
   end
 end

end </lang>

Sather

Translation of: Fortran

<lang sather>class MAIN is

 move(ndisks, from, to, via:INT) is
   if ndisks = 1 then
     #OUT + "Move disk from pole " + from + " to pole " + to + "\n";
   else
     move(ndisks-1, from, via, to);
     move(1, from, to, via);
     move(ndisks-1, via, to, from);
   end;
 end;

 main is
   move(4, 1, 2, 3);
 end;

end;</lang>

Scala

<lang scala>def move(n: int, from: int, to: int, via: int) = {

   if (n == 1) {
     Console.println("Move disk from pole " + from + " to pole " + to)
   } else {
     move(n - 1, from, via, to)
     move(1, from, to, via)
     move(n - 1, via, to, from)
   }
 }</lang>

This next example is from http://gist.github.com/66925 it is a translation to Scala of a Prolog solution and solves the problem at compile time <lang scala>object TowersOfHanoi {

 import scala.reflect.Manifest
 
 def simpleName(m:Manifest[_]):String = {
   val name = m.toString
   name.substring(name.lastIndexOf('$')+1)
 }
 
 trait Nat
 final class _0 extends Nat
 final class Succ[Pre<:Nat] extends Nat

 type _1 = Succ[_0]
 type _2 = Succ[_1]
 type _3 = Succ[_2]
 type _4 = Succ[_3]

 case class Move[N<:Nat,A,B,C]()

 implicit def move0[A,B,C](implicit a:Manifest[A],b:Manifest[B]):Move[_0,A,B,C] = {
       System.out.println("Move from "+simpleName(a)+" to "+simpleName(b));null
 }

 implicit def moveN[P<:Nat,A,B,C](implicit m1:Move[P,A,C,B],m2:Move[_0,A,B,C],m3:Move[P,C,B,A])
  :Move[Succ[P],A,B,C] = null
 
 def run[N<:Nat,A,B,C](implicit m:Move[N,A,B,C]) = null
 
 case class Left()
 case class Center()
 case class Right()
 
 def main(args:Array[String]){
   run[_2,Left,Right,Center]
 }

}</lang>

Scheme

<lang scheme>(define (hanoi n a b c)

 (if (> n 0)
   (begin
     (hanoi (- n 1) a c b)
     (display "Move disk from pole ")
     (display a)
     (display " to pole ")
     (display b)
     (newline)
     (hanoi (- n 1) c b a))))

(hanoi 4 1 2 3)</lang>

Seed7

<lang seed7>const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func

 begin
   if disk > 0 then
     hanoi(pred(disk), source, via, dest);
     writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest);
     hanoi(pred(disk), via, dest, source);
   end if;
 end func;</lang>

SNOBOL4

<lang SNOBOL4>* # Note: count is global

       define('hanoi(n,src,trg,tmp)') :(hanoi_end)

hanoi hanoi = eq(n,0) 1 :s(return)

       hanoi(n - 1, src, tmp, trg)
       count = count + 1
       output = count ': Move disc from ' src ' to ' trg
       hanoi(n - 1, tmp, trg, src) :(return)

hanoi_end

# Test with 4 discs

       hanoi(4,'A','C','B')

end</lang>

Output:

1: Move disc from A to B
2: Move disc from A to C
3: Move disc from B to C
4: Move disc from A to B
5: Move disc from C to A
6: Move disc from C to B
7: Move disc from A to B
8: Move disc from A to C
9: Move disc from B to C
10: Move disc from B to A
11: Move disc from C to A
12: Move disc from B to C
13: Move disc from A to B
14: Move disc from A to C
15: Move disc from B to C

Tcl

The use of interp alias shown is a sort of closure: keep track of the number of moves required <lang tcl>interp alias {} hanoi {} do_hanoi 0

proc do_hanoi {count n {from A} {to C} {via B}} {

   if {$n == 1} {
       interp alias {} hanoi {} do_hanoi [incr count]
       puts "$count: move from $from to $to"
   } else {
       incr n -1
       hanoi $n $from $via $to
       hanoi 1  $from $to $via
       hanoi $n $via $to $from
   }

}

hanoi 4</lang>

Output:

1: move from A to B
2: move from A to C
3: move from B to C
4: move from A to B
5: move from C to A
6: move from C to B
7: move from A to B
8: move from A to C
9: move from B to C
10: move from B to A
11: move from C to A
12: move from B to C
13: move from A to B
14: move from A to C
15: move from B to C

TI-83 BASIC

TI-83 BASIC lacks recursion, so technically this task is impossible, however here is a version that uses an iterative method. <lang ti-83b>PROGRAM:TOHSOLVE 0→A 1→B 0→C 0→D 0→M 1→R While A<1 or A>7 Input "No. of rings=?",A End randM(A+1,3)→[C] [[1,2][1,3][2,3]]→[E]

Fill(0,[C]) For(I,1,A,1) I?[C](I,1) End ClrHome While [C](1,3)≠1 and [C](1,2)≠1

For(J,1,3) For(I,1,A) If [C](I,J)≠0:Then Output(I+1,3J,[C](I,J)) End End End While C=0 Output(1,3B," ") 1→I [E](R,2)→J While [C](I,J)=0 and I≤A I+1→I End [C](I,J)→D 1→I [E](R,1)→J While [C](I,J)=0 and I≤A I+1→I End If (D<[C](I,J) and D≠0) or [C](I,J)=0:Then [E](R,2)→B Else [E](R,1)→B End

1→I While [C](I,B)=0 and I≤A I+1→I End If I≤A:Then [C](I,B)→C 0→[C](I,B) Output(I+1,3B," ") End Output(1,3B,"V") End

While C≠0 Output(1,3B," ") If B=[E](R,2):Then [E](R,1)→B Else [E](R,2)→B End

1→I While [C](I,B)=0 and I≤A I+1→I End If [C](I,B)=0 or [C](I,B)>C:Then C→[C](I-1,B) 0→C M+1→M End End Output(1,3B,"V") R+1→R If R=4:Then:1→R:End

End </lang>

Toka

<lang toka>value| sa sb sc n | [ to sc to sb to sa to n ] is vars! [ ( num from to via -- )

 vars!
 n 0 <>
 [
   n sa sb sc 
   n 1- sa sc sb recurse
   vars!
   ." Move a ring from " sa . ." to " sb . cr
   n 1- sc sb sa recurse
 ] ifTrue

] is hanoi</lang>

TSE SAL

<lang TSESAL>// library: program: run: towersofhanoi: recursive: sub <description></description> <version>1.0.0.0.0</version> <version control></version control> (filenamemacro=runprrsu.s) [kn, ri, tu, 07-02-2012 19:54:23] PROC PROCProgramRunTowersofhanoiRecursiveSub( INTEGER totalDiskI, STRING fromS, STRING toS, STRING viaS, INTEGER bufferI )

IF ( totalDiskI == 0 )
 RETURN()
ENDIF
PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI - 1, fromS, viaS, toS, bufferI )
AddLine( Format( "Move disk", " ", totalDiskI, " ", "from peg", " ", "'", fromS, "'", " ", "to peg", " ", "'", toS, "'" ), bufferI )
PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI - 1, viaS, toS, fromS, bufferI )

END

// library: program: run: towersofhanoi: recursive <description></description> <version>1.0.0.0.6</version> <version control></version control> (filenamemacro=runprtre.s) [kn, ri, tu, 07-02-2012 19:40:45] PROC PROCProgramRunTowersofhanoiRecursive( INTEGER totalDiskI, STRING fromS, STRING toS, STRING viaS )

INTEGER bufferI = 0
PushPosition()
bufferI = CreateTempBuffer()
PopPosition()
PROCProgramRunTowersofhanoiRecursiveSub( totalDiskI, fromS, toS, viaS, bufferI )
GotoBufferId( bufferI )

END

PROC Main() STRING s1[255] = "4" IF ( NOT ( Ask( "program: run: towersofhanoi: recursive: totalDiskI = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF

PROCProgramRunTowersofhanoiRecursive( Val( s1 ), "source", "target", "via" )

END</lang>

UNIX Shell

Works with: bash

<lang bash>#!/bin/bash

move() {

 local n="$1"
 local from="$2"
 local to="$3"
 local via="$4"

 if "$n" == "1" 
 then
   echo "Move disk from pole $from to pole $to"
 else
   move $(($n - 1)) $from $via $to
   move 1 $from $to $via
   move $(($n - 1)) $via $to $from
 fi

}

move $1 $2 $3 $4</lang>

Ursala

<lang Ursala>#import nat

move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC

show+

main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'></lang>

Output:

start -> middle
start -> end
middle -> end
start -> middle
end -> start
end -> middle
start -> middle
start -> end
middle -> end
middle -> start
end -> start
middle -> end
start -> middle
start -> end
middle -> end

Vedit macro language

This implementation outputs the results in current edit buffer. <lang vedit>#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2 Call("MOVE_DISKS") Return

// Move disks // #1 = from, #2 = to, #3 = via, #4 = number of disks //

MOVE_DISKS:

if (#4 > 0) {

   Num_Push(1,4)
       #9=#2; #2=#3; #3=#9; #4--       // #1 to #3 via #2
       Call("MOVE_DISKS")
   Num_Pop(1,4)

   Ins_Text("Move a disk from ")       // move one disk
   Num_Ins(#1, LEFT+NOCR)
   Ins_Text(" to ")
   Num_Ins(#2, LEFT)

   Num_Push(1,4)
       #9=#1; #1=#3; #3 = #9; #4--     // #3 to #2 via #1
       Call("MOVE_DISKS")
   Num_Pop(1,4)

} Return</lang>

Visual Basic .NET

<lang vbnet>Module TowersOfHanoi

   Sub MoveTowerDisks(ByVal disks As Integer, ByVal fromTower As Integer, ByVal toTower As Integer, ByVal viaTower As Integer)
       If disks > 0 Then
           MoveTowerDisks(disks - 1, fromTower, viaTower, toTower)
           System.Console.WriteLine("Move disk {0} from {1} to {2}", disks, fromTower, toTower)
           MoveTowerDisks(disks - 1, viaTower, toTower, fromTower)
       End If
   End Sub

   Sub Main()
       MoveTowerDisks(4, 1, 2, 3)
   End Sub

End Module</lang>

XPL0

<lang XPL0>code Text=12;

proc MoveTower(Discs, From, To, Using); int Discs, From, To, Using; [if Discs > 0 then

   [MoveTower(Discs-1, From, Using, To);
   Text(0, "Move from ");  Text(0, From);
   Text(0, " peg to ");  Text(0, To);  Text(0, " peg.^M^J");
   MoveTower(Discs-1, Using, To, From);
   ];

];

MoveTower(3, "left", "right", "center")</lang>

Output:

Move from left peg to right peg.
Move from left peg to center peg.
Move from right peg to center peg.
Move from left peg to right peg.
Move from center peg to left peg.
Move from center peg to right peg.
Move from left peg to right peg.

XSLT

<lang xml><xsl:template name="hanoi"> <xsl:param name="n"/> <xsl:param name="from">left</xsl:param> <xsl:param name="to">middle</xsl:param> <xsl:param name="via">right</xsl:param>

 <xsl:if test="$n > 0">
   <xsl:call-template name="hanoi">
     <xsl:with-param name="n"    select="$n - 1"/>
     <xsl:with-param name="from" select="$from"/>
     <xsl:with-param name="to"   select="$via"/>
     <xsl:with-param name="via"  select="$to"/>
   </xsl:call-template>
   <fo:block>
     <xsl:text>Move disk from </xsl:text>
     <xsl:value-of select="$from"/>
     <xsl:text> to </xsl:text>
     <xsl:value-of select="$to"/>
   </fo:block>
   <xsl:call-template name="hanoi">
     <xsl:with-param name="n"    select="$n - 1"/>
     <xsl:with-param name="from" select="$via"/>
     <xsl:with-param name="to"   select="$to"/>
     <xsl:with-param name="via"  select="$from"/>
   </xsl:call-template>
 </xsl:if>

</xsl:template></lang>

<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template>

XQuery

<lang xquery>declare function local:hanoi($disk as xs:integer, $from as xs:integer,

   $to as xs:integer, $via as xs:integer) as element()*

{

 if($disk > 0)
 then (
   local:hanoi($disk - 1, $from, $via, $to),
   <move disk='{$disk}'><from>{$from}</from><to>{$to}</to></move>,
   local:hanoi($disk - 1, $via, $to, $from)
 ) 
 else ()

};

<hanoi> {

 local:hanoi(4, 1, 2, 3)

} </hanoi></lang>

Output:

  <move disk="1">
     <from>1</from>
     <to>3</to>
  </move>
  <move disk="2">
     <from>1</from>
     <to>2</to>
  </move>
  <move disk="1">
     <from>3</from>
     <to>2</to>
  </move>
  <move disk="3">
     <from>1</from>
     <to>3</to>
  </move>
  <move disk="1">
     <from>2</from>
     <to>1</to>
  </move>
  <move disk="2">
     <from>2</from>
     <to>3</to>
  </move>
  <move disk="1">
     <from>1</from>
     <to>3</to>
  </move>
  <move disk="4">
     <from>1</from>
     <to>2</to>
  </move>
  <move disk="1">
     <from>3</from>
     <to>2</to>
  </move>
  <move disk="2">
     <from>3</from>
     <to>1</to>
  </move>
  <move disk="1">
     <from>2</from>
     <to>1</to>
  </move>
  <move disk="3">
     <from>3</from>
     <to>2</to>
  </move>
  <move disk="1">
     <from>1</from>
     <to>3</to>
  </move>
  <move disk="2">
     <from>1</from>
     <to>2</to>
  </move>
  <move disk="1">
     <from>3</from>
     <to>2</to>
  </move>

</hanoi></lang>