MIPS assembly language ( Towers of Hanoi) Given three pegs and a stack of circul

Question

MIPS assembly language (Towers of Hanoi)

Given three pegs and a stack of circular disks of various sizes on peg 1 with the largest on the bottom, move the entire stack to peg 3 so that the disks are in the same order. Rules:

1. Only one disk may be moved at a time, and it must be the top disk on its peg.

2. No disk may be placed on top of a smaller disk.

Recursion works perfectly for this game. Suppose we look at the problem as follows: our task is to move N disks from peg 1 to peg 3. We win the game if we do the following:

1. Move (N-1) disks from peg 1 to peg 2.

2. Move the largest disk to peg 3.

3. Move (N-1) disks from peg 2 to peg 3.

Note: Complete this code

=========== code =======below=== MIPS assembly language====

Explanation / Answer

I am writing a generalised code for any number of pegs. You can take hanoi recursive code for your work.

Code for Towers of Hanoi in MIPS Assembly:

   .data
   .align 4
input: .asciiz " Enter number of disks>"
move_d:   .asciiz "Move disk: "
from:   .asciiz " from peg: "
to:   .asciiz " to peg: "
new_line: .asciiz ". "
DONE: .asciiz " Done. "

.text
.globl main
main:
   add    $fp, $zero, $sp;   # set the frame pointer
li    $2,4;           # System call code for print string
la    $4,input;       # Argument string as input
syscall;           # Print the string

li    $2,5;           # System call code to read int input
syscall;           # Read it

   add    $a0, $zero, $v0;   # move number into arg1
   addi    $a1, $zero, 1;       # put one into arg 2
   addi    $a2, $zero, 2;       # put two into arg 3
   addi    $a3, $zero, 3;       # put three into arg 3
   jal    hanoi;           # jump and link to hanoi

Exit:
   li    $v0, 4;        # print done
   la    $a0, DONE;            
   syscall;
li    $2,10;           # System call code for exit
syscall # exit

hanoi:
   addi   $sp,$sp,-4;       # dec sp
   sw   $ra,($sp);       # save return address on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $fp,($sp);       # save fp on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $s0,($sp);       # save s0 on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $s1,($sp);       # save s1 on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $s2,($sp);       # save s2 on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $s3,($sp);       # save s3 on stack
   addi   $sp,$sp,-4;       # dec sp
   addi   $fp, $sp, 32       # set $fp
   beq   $a0, $zero, n_zero;   # is n zero
   sw   $a0,($sp);       # store "n" on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $a1,($sp);       # store "start" on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $a2,($sp);       # store "finish" on stack
   addi   $sp,$sp,-4;       # dec sp
   sw   $a3,($sp);       # store "extra" on stack
   addi   $sp,$sp,-4;       # dec sp  
   addi   $a0,$a0,-1       # put n-1 in arg0
   add   $t2, $zero,$a2;       # put a2 in temp2
   add   $a2, $zero, $a3;   # swap args 2 and 3 for first call
   add   $a3, $zero, $t2;      
   jal   hanoi           # call hanoi
   addi   $sp,$sp,4;       # inc sp  
   lw   $s0,($sp)       # get "extra" =s0
   addi   $sp,$sp,4;       # inc sp  
   lw   $s1,($sp)       # get "finish" =s1
   addi   $sp,$sp,4;       # inc sp  
   lw   $s2,($sp)       # get "start" =s2
   addi   $sp,$sp,4;       # inc sp   
   lw   $s3,($sp)       # get n =s3
   li    $v0, 4;           
   la    $a0, move_d;            
   syscall;
   li    $2,1;   
add    $4, $zero, $s3;   
   syscall;
   li    $v0, 4;       
   la    $a0, from;        
   syscall;
   li    $v0, 1;           
   add    $a0,$zero, $s2;            
   syscall;
   li    $v0, 4;           
   la    $a0, to;            
   syscall;
   li    $v0, 1;           
   add    $a0, $zero, $s1;            
   syscall;
   li    $v0, 4;           
   la    $a0, new_line;            
   syscall;
   addi    $a0,$s3,-1       # put n-1 in arg 0
   add    $a1, $zero, $s0;   # extra is second arg;
   add    $a2, $zero, $s1;   # finish is third arg
   add    $a3, $zero, $s2;   # start is last arg;
   jal    hanoi;           # call hanoi
n_zero:
   addi   $sp,$sp,4;       # inc sp
   lw   $s3,($sp);       # get old s3 off stack
   addi   $sp,$sp,4;       # inc sp
   lw   $s2,($sp);       # get old s2 off stack
   addi   $sp,$sp,4;       # inc sp
   lw   $s1,($sp);       # get old s1 off stack
   addi   $sp,$sp,4;       # inc sp
   lw   $s0,($sp);       # get old s0 off stack
   addi   $sp,$sp,4;       # inc sp
   lw   $fp,($sp);       # get old fp off stack
   addi   $sp,$sp,4;       # inc sp
   lw   $ra,($sp);       # get return address off stack
   addi   $sp,$sp,4;       # inc sp back to where we expect it to start
   jr    $ra;           # go back to caller+4

  
If I select 3 disks as input, I get the following output:

Enter number of disks> 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.

Done.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.