C 재귀에서 Mips 번역이 잘못 출력되었습니다.

Question

이 문제는 8 개의 퀸즈 문제 (8x8 체스 판에 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 코드 같았다. 문제는 내가 말할 수있는 한 재귀입니다.

내가 잘못하고있는 아이디어가 있습니까? MIP 어셈블리를 읽을 수없는 사람들을 위해, 재귀가없는 "C"솔루션 (광산과 동일)은 괜찮을 것입니다. (직접 번역 할 수 있습니다).

아이디어 나 솔루션이 있습니까?

Answer 1

문제는 내가 알 수있는 한 재귀입니다.

실제로 이것이 주된 문제입니다. 간과 한 결과, solve을 반복적으로 호출하면 $a1 및 $t3이 호출 후 수정되며 (호출 코드로 후자, 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 

에

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

을 변경하여이 문제를 해결할 수 있고, 약간의 오류가 :

• 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이 있어야합니다 있어야합니다
  ,536,913,632 (우리가 $a1, (col - j)에서 j을 필요로하면서, $a0i했다) (attack_or: 후) 10 bnez $a3, attack_or #if hist[j] != i
• sub $t0, $a2, $a0는 sub $t0, $a2, $a1
  이 있어야합니다.