Проблема называется проблемой восьми королей (размещение 8 ферзей на шахматной доске 8 x 8, чтобы никто из них не мог атаковать/угрожать друг другу). У меня есть следующее решение в C, и он использует рекурсию для печати всех возможных решений. Я хочу сделать это нерекурсивным, но у меня были проблемы с этим, поэтому я просто перевел его в MIPS напрямую.Mips перевод с C рекурсия неправильный вывод
Я бы предпочел сделать его нерекурсивным.
#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);
}
И результат (один из возможных решений):
Теперь мне нужно перевести его на трудоемкость и у меня есть:
#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» (то же самое, что и мое) без рекурсии также будет прекрасным (я могу перевести его сам).
Любые идеи или решения?
Проще было придумать итеративную версию в ассемблере, чем в C? –
Да. Если у меня есть итеративный код на C, для меня очень просто преобразовать его в mips .. Я просто не был уверен, как сделать итеративный в C :( – Brandon