從C遞歸錯誤輸出Mips翻譯

Question

這個問題被稱爲八皇后問題（在一個8×8的棋盤上放置8個皇后，這樣他們都不會互相攻擊/威脅）。我在C中有以下解決方案，它使用遞歸來打印所有可能的解決方案。我想讓它不是遞歸的，但是我遇到了麻煩，所以我直接將它轉換爲MIPS。

但是，我仍然希望它不是遞歸的。

#include <string.h> 
#include <stdio.h> 
#include <stdlib.h> 


int attack(int i, int j, int col, int* hist) 
{ 
    return (hist[j] == i) || (abs(hist[j] - i) == (col - j)); 
} 

int solve(int n, int col, int *hist) 
{ 
    if (col == n) 
    { 
     putchar('\n'); 
     for (int i = 0; i < n; ++i) 
     { 
      for (int j = 0; j < n; ++j) 
      { 
       if (hist[i] == j) 
       { 
        putchar('Q'); 
       } 
       else if((i + j) & 1) 
       { 
        putchar(' '); 
       } 
       else 
       { 
        putchar(178); 
       } 
      } 
      putchar('\n'); 
     } 
     return 0; 
    } 

    for (int i = 0, j = 0; i < n; ++i) 
    { 
     for (j = 0; j < col; ++j) 
     { 
      if (attack(i, j, col, hist) != 0) 
       break; 
     } 

     if (j < col) continue; 

     hist[col] = i; 
     solve(n, col + 1, hist); 
    } 
    return 0; 
} 

int main() 
{ 
    int hist[8]; 
    solve(8, 0, hist); 
} 

，結果是（一個可能的解決方案）：

現在我需要把它翻譯成MIPS和我有：

#include <mips.h> 


.data 
new_line: .asciiz "\n" 
new_lines: .asciiz "\n\n\n" 
black_sq: .asciiz "B" 
white_sq: .asciiz "W" 
queen_sq: .asciiz "Q" 
hist:  .word 0, 0, 0, 0, 0, 0, 0, 0 

i_p: .asciiz "I: " 
j_p: .asciiz " J: " 
.text 
.globl main 

main: 
    subiu $sp, $sp, 32 
    sw $ra, 28($sp) 
    sw $fp, 24($sp) 
    sw $s0, 20($sp) 
    sw $s1, 16($sp) 
    #store stack-frame: end. 

    li $a0, 8 
    li $a1, 0 
    la $a2, hist 
    jal solve 


    #restore stack-frame: beg. 
    sw $s1, 16($sp) 
    sw $s0, 20($sp) 
    lw $fp, 24($sp) 
    lw $ra, 28($sp) 
    addiu $sp, $sp, 32 
    li $v0, 10 
syscall 


#solve(n, col, hist) 
solve: 
    subiu $sp, $sp, 32 
    sw $ra, 28($sp) 
    sw $a0, 24($sp) 
    sw $a1, 20($sp) 
    sw $a2, 16($sp) 

    bne $a1, $a0, solve_atk 

    li $v0, 4 
    la $a0, new_lines 
    syscall 
    lw $a0, 24($sp) 


    li $t0, 0 #i = 0 
    solve_for_1: 
     beq $t0, $a0, solve_for_1_end 

     li $t1, 0 #j = 0 
     solve_for_2: 
      beq $t1, $a0, solve_for_2_end 


      sll $t2, $t0, 2  #ri = i * sizeof(int) 
      add $t2, $t2, $a2 
      lw $t2, 0($t2)  #hist[i] 
      bne $t2, $t1, solve_for_2_else_if 
      la $a0, queen_sq #putchar('Q') 
      j solve_for_2_if_end 

      solve_for_2_else_if: 
      add $t2, $t1, $t0 
      andi $t3, $t2, 1 
      beqz $t3, solve_for_2_else 
      la $a0, white_sq #putchar(' ') 
      j solve_for_2_if_end 

      solve_for_2_else: 
      la $a0, black_sq #putchar(¦) 

      solve_for_2_if_end: 
      li $v0, 4 
      syscall 
      lw $a0, 24($sp) 

      addiu $t1, $t1, 1 #++j 
      j solve_for_2 
     solve_for_2_end: 

     li $v0, 4 
     la $a0, new_line #putchar('\n') 
     syscall 
     lw $a0, 24($sp) 
     addiu $t0, $t0, 1 #++i 
     j solve_for_1 
    solve_for_1_end: 
    addiu $sp, $sp, 32 
    jr $ra #return; 

    solve_atk: 
     li $t3, 0 #i = 0 
     solve_atk_for_1: 
      beq $t3, $a0, solve_atk_for_1_end 
      li $t4, 0 #j = 0 

      solve_atk_for_2: 
      beq $t4, $a1, solve_atk_for_2_end 

      move $a3, $a2 #hist 
      move $a2, $a1 #col 
      move $a1, $t4 #j 
      move $a0, $t3 #i 
      jal attack  #v0 = attack(i, j, col, hist); 
      lw $a2, 16($sp) 
      lw $a1, 20($sp) 
      lw $a0, 24($sp) 
      lw $ra, 28($sp) 

      beqz $v0, solve_atk_for_2_end #if (attack(i, j, col, hist) != 0) break; 

      addiu $t4, $t4, 1 
      j solve_atk_for_2 
      solve_atk_for_2_end: 

      blt $t4, $a1, solve_atk_for_1_continue #if (j < col) continue; 



      sll $t0, $a1, 2  #ri = col * sizeof(int) 
      add $t0, $t0, $a2 
      sw $t3, 0($t0)  #hist[col] = i 

      lw $a2, 16($sp) 
      lw $a1, 20($sp) 
      lw $a0, 24($sp) 
      lw $ra, 28($sp) 
      addiu $a1, $a1, 1 #solve(i, col + 1, hist) 
      jal solve 

      solve_atk_for_1_continue: 

     addiu $t3, $t3, 1 #++i 
     j solve_atk_for_1 
     solve_atk_for_1_end: 


    lw $a2, 16($sp) 
    lw $a1, 20($sp) 
    lw $a0, 24($sp) 
    lw $ra, 28($sp) 
    addiu $sp, $sp, 32 
jr $ra 


#attack(i, j, col, hist) 
attack: 
    sll $t0, $a1, 2  #ri = j * sizeof(int) 
    add $t0, $t0, $a3 
    lw $t0, 0($t0)  #hist[j]  
    sub $a3, $t0, $a0 

    li $v0, 0 
    beqz $a3, attack_or #if hist[j] != i 
    li $v0, 1   #return true. 
    j attack_done 

    attack_or: 
     abs $a3, $a3 
     sub $t0, $a2, $a0 
     bne $t0, $a3, attack_done 
     li $v0, 1 

    attack_done: 
jr $ra 


abs: 
    sra $t1, $t0, 31 
    xor $t0, $t0, $t1 
    sub $v0, $t0, $t1 
jr $ra 

但它打印出錯誤的結果。我懷疑這是由於遞歸，因爲我之前測試的所有代碼：

solve_atk

畢竟代碼solve_atk分開，這是完全一樣的C代碼。據我所知，問題在於遞歸。

任何想法我做錯了什麼？對於那些不能閱讀MIPs彙編的人來說，沒有遞歸的「C」解決方案（和我的一樣）也不錯（我可以自己翻譯）。

任何想法或解決方案？

Answer 1

就我所知，問題在於遞歸。

確實這是主要問題。您忽略了在遞歸調用solve時，寄存器$a1和$t3被修改（前者由您的調用代碼調用，後者由調用的solve實例修改），而調用後仍需要其原始值。你可以通過改變

  addiu $a1, $a1, 1 #solve(i, col + 1, hist) 
      jal solve 

糾正這

  addiu $a1, $a1, 1 #solve(i, col + 1, hist) 
      sw $t3, 12($sp)  # save $t3 
      jal solve 
      lw $t3, 12($sp)  # restore $t3 
      addiu $a1, $a1, -1 # restore $a1 

除此之外，還有一些小錯誤：

• beqz $v0, solve_atk_for_2_end #if (attack(i, j, col, hist) != 0) break;必須
  bnez $v0, solve_atk_for_2_end #if (attack(i, j, col, hist) != 0) break;
• beqz $a3, attack_or #if hist[j] != i必須
  bnez $a3, attack_or #if hist[j] != i
• sub $t0, $a2, $a0（後attack_or:）必須
  sub $t0, $a2, $a1（$a0爲i，而我們需要$a1，j在(col - j)）。