CSC231 Analysis of the Towers of Hanoi

--D. Thiebaut 16:24, 25 November 2012 (EST)

---

A High-Level Version in Python

# hanoi.py  (Python V 2.7)
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type 
#        python hanoi.py 
# at the command line

def moveDisk( source, dest, extra, n ):
    if n==1:
        print "move disk from %s to %s" % ( source, dest )
        return
    
    # more than 1 disk...
    moveDisk( source, extra, dest, n-1)
    print "move disk from %s to %s" % ( source, dest )
    moveDisk( extra, dest, source, n-1)

def main():
    while True:
        n = input( "# of disks? " )
        moveDisk( "A", "B", "C", n )

main()

Top Down Approach: Version 1

Source

In this version all we do is simply set a main program that calls the function moveDisks and passes it

• the number of disk to move (in al)
• the source peg (in bl)
• the destination peg (in cl)
• and the extra or temporary peg (in dl)

The moveDisks function prints a single move, testing the printMove function that prints "X Y" on a line by itself, indicating that a disk must be move from X to Y.

;;; hanoi1.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

		section	.data
moveStr		db	"X --> X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 6	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al, 4	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
	
		pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any register
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
		int	0x80
		popad
		ret

Output

[231a@beowulf ~/handout]$ nasmld hanoi1
A --> B

Top Down Version 2

In this version we fully flesh out the recursive function. It would be hard to go half way with the implementation of moveDisks.

Source

;;; hanoi2.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

%define		N	6	; number of disks to move
	
		section	.data
moveStr		db	"X X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 2	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al,  N	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		cmp	al, 1
		ja	.recurse
	
;;; only 1 to move: move from source to dest!
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		jmp	.return

.recurse:
;;; move n-1 disk from source to temp
		dec	al	; al <-- n-1
		xchg	cl, dl	; swap dest and temp
		call	moveDisks
		xchg	cl, dl	; swap back dest and temp
	
;;; move 1 from source to dest
		push	ax
		mov	al, 1
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		pop	ax
	
;;; move n-1 disk from temp to dest
		xchg	bl, dl	; make temp the source
		call	moveDisks
	
.return:	pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any of the registers
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
;;; 		int	0x80
		popad
		ret

Note here that we are using a macro, N, defined by the %define statement. This method of defining a constant is interesting as it allows us to modify the constant at assembly time.

Here's how.

• comment out the %define statement in the program (this will result in an undefined variable if we assemble as usual)
• when assembling the program, provide a value for the macro N as follows:

  nasm -f elf -F stabs -dN=4 hanoi2.asm  ;  ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2

• The result will be that your program will be assembled just as if you had included the line

  %define N 4

inside your program.

The section below shows how to make the program run for several values of N:

Output

[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A B
A C
B C
A B
C A
C B
A B
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
A C
B A
B C
A C
A B
C B
C A
B A
C B
A C
A B
C B

Trick

If we want to count the number of moves for a given number of disk, we can pipe the output of the ./hanoi2 program in the command wc, which stands for word-count. wc outputs the number of lines, number of words, and number of characters in the text given to it.

Below are the same commands as above, but filtered by wc:

[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
      3       6      12
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
      7      14      28
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
     15      30      60

We see that the number of moves for 2 disks is 3, for 3 disks it's 7, for 4 disks it's 15, for n disks, it's 2ⁿ-1.

Execution time?

Call Tree of MoveDisks( 4, 'A', 'B', 'C' )

                                               N, Source, Dest, Extra


                                                     4,A,B,C
                                                        |
                            +---------------------------+-------------------------------+
                            |                           |                               |
                         3,A,C,B                      1,A,B,C                        3,C,B,A
                            |                                                           |
              +-------------+------------+                                 +------------+-------------+
              |             |            |                                 |            |             |
           2,A,B,C       1,A,C,B      2,B,C,A                           2,C,A,B      1,C,B,A       2,A,B,C
              |                          |                                 |                          |
     +--------+--------+        +--------+--------+               +--------+--------+        +--------+--------+
     |        |        |        |        |        |               |        |        |        |        |        |
  1,A,C,B  1,A,B,C  1,C,B,A  1,B,A,C  1,B,C,A  1,A,C,B         1,C,B,A  1,C,A,B  1,B,A,C  1,A,C,B  1,A,B,C  1,C,B,A
     |                 |        |                 |               |                 |        |                 |
  1,A,C,B           1,C,B,A  1,B,A,C           1,A,C,B         1,C,B,A           1,B,A,C  1,A,C,B           1,C,B,A