CSC231 Analysis of the Towers of Hanoi
--D. Thiebaut 16:24, 25 November 2012 (EST)
Top Down Approach: Version 1
;;; 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
Top Down Version 2
[231a@beowulf ~/handout]$ cat hanoi2.asm
;;; 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
