title: backtracking in mips assembly for puzzle solver
body: <p>I'm working on a backtracking algorithm in MIPS Assembly and I'm getting lost in the dealing with scope, and structure of the code. </p>
  
  <p>We have a few moving parts here, which I'm only confusing myself more with trying to figure out how to deal with them.</p>
  
  <p>The end goal is a puzzle solver that uses backtracking. </p>
  
  <p>The "moving parts".</p>
  
  <blockquote>
    <p>We have the address of an array of indexes which have all of the indexes of the puzzle that we need to change. The rest of the board can not be altered.</p>
    
    <p>We have the address of the puzzle board, simply an array of bytes.</p>
    
    <p>We have the total size of the board, we're going to use this to check if we've looked at the entire board to know we're done. </p>
    
    <p>We have a function is_Legal(arg1, arg2). Arg1 is the address of the board (array) to check, arg2 is the size of the board. Returns 0 if it's legal, 1 if not.</p>
  </blockquote>
  
  <p>So we first load up </p>
  
  <pre><code>   initialize_guessing:
                 .. # build up stack
                 la   $s0, $a0         # s0 = address of board
                 la   $s1, $a1         # s1 = address of index array
                 la   $s2, $a2         # s2 = size of index array
                 la   $s3, $a3         # s3 = size of board 
                 li   $t0, 0           # t0 = values to test
                 li   $t1, 0           # t1 = index counter
     start_guessing:
                 beq  $t1, $s2, done   # if t1 = s2, we've used all indexes
                 lb   $t2, 0($s1)      # get first index 
                 add  $s0, $s0, $t2    # move to first index
                 sb   $t0, 0($s0)      # put t0 into board
                 move $a0, $s0         # a0 = board address for if_legal
                 move $a1, $s3         # a1 = board size for if_legal
                 jal  if_legal         # check if board is legal
                 beq  $v0, $zero, continue_guessing   # if board is legal, continue
                 j    new_guess        # try a new guess
     new_guess:
                 addi $t0, 1           # increment t0 to try a new value
                 jal  start_guessing
     continue_guessing:
                 addi $s1, 1           # increment index array to next index
                 jal  start_guessing
     done:
                # destroy stack
                 jr   $ra
  </code></pre>
  
  <p>This is what I've got so far, I know it's incomplete I believe ultimately that the entire guessing function needs to return something but I don't know when to return that. Any hints would be much appreciated. </p>