Question

Write the recursive MIPS code (with abundant explanatory comments) for the Tower of Hanoi problem of transferring a stack of N disks (smaller sized disks stacked over the larger sized ones) from a source peg to a destination peg via a third (temporary rest peg) under the constraints:

1. Only one disk is moved at a time from one peg to another

2. At no time, a larger disk will sit on a smaller one.

Answer 1

li $v0, 4   
la $s0, Prompt     #Enter number of disk N in s0
syscall

li $v0, 5
syscall
add $s0, $v0, $zero

addi $p1, $zero, 1                #$p1 = start peg
addi $p2, $zero, 3                #$p2 = end peg
addi $p3, $zero, 2                #$p3 = extra peg
jal hanoi_towers

hanoi_towers: #Equivalent C implementation for reference
# if (num_of_disks == 1)
# move disk to end_peg
# else
# hanoi_towers(num_of_disks-1, start_peg, extra_peg, end_peg)
# move disk from start_peg to end_peg
# hanoi_towers(num_of_disks-1, extra_peg, end_peg, start_peg)

# if (num_of_disks == 1)
addi $t0, $s0, 0
addi $t1, $zero, 1
bne $s0, $t1, else
li $v0, 4
la $s0, Move
syscall
li $v0, 1
move $s0, $p1
syscall
li $v0, 4
la $s0, To
syscall
li $v0, 1
move $s0, $p2
syscall
addi $s0, $t0, 0
jr $ra

else:
addi $sp, $sp, -20

sw $ra, 16($sp)
sw $p3, 12($sp)
sw $p2, 8($sp)                              #store p2(end_peg)
sw $p1, 4($sp)                               #store p1(start_peg)
sw $s0, 0($sp)                               #store s0(num_of_disks)

#recursive call to function hanoi_towers
addi $t3, $p3, 0
addi $p3, $p2, 0                #extra_peg = end_peg
addi $p2, $t3, 0               #end_peg = extra_peg
addi $s0, $s0, -1              #reduce no of disks by 1
jal hanoi_towers
lw $ra, 16($sp)
lw $p3, 12($sp)
lw $p2, 8($sp)
lw $p1, 4($sp)
lw $s0, 0($sp)

#move a disk from start_peg to end_peg
addi $t0, $s0, 0
addi $t1, $zero, 1
li $v0, 4
la $s0, Move
syscall
li $v0, 1
move $s0, $p1
syscall
li $v0, 4 la $s0, To
syscall
li $v0, 1
move $s0, $p2
syscall
addi $s0, $t0, 0

#hanoi_towers(num_of_disks-1, extra_peg, end_peg, start_peg)
addi $t3, $p3, 0
addi $p3, $p1, 0
addi $p1, $t3, 0
addi $s0, $s0, -1              #num of disk--
jal hanoi_towers

lw $ra, 16($sp)
addi $sp, $sp, 20

#return
add $v0, $zero, $t5

jr $ra