c - 从 C 递归错误输出的 Mips 翻译

Question

这个问题被称为八皇后问题(将 8 个皇后放在 8 x 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

The problem is then the recursion as far as I can tell.

这确实是主要问题。您在调用 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) 中)。