八皇后问题MIPS汇编实现.pdf

八皇后问题 一、 计算的规则和任务 国际象棋中的皇后可以吃掉与它在同一行、同一列、同一对角线 上的棋子。八皇后问题，即在8×8 的国际象棋棋盘上放置8 个皇后， 要求任意两个皇后不能在同一行、同一列或同一条对角线上。求出如 此放置方法的种数。一种解决问题的思路是一行放置皇后，如果当前 放置的皇后与前面的皇后不存在冲突时，则继续摆下一个皇后，否则 跳到上一个皇后，重新摆置。 二、 八皇后问题的C 实现 ：递归放置第 个皇后 ：判断放置第 个皇后时是否无 冲突 ：判断第 个皇后放上去之后，是否合法，即是否无 冲突。 三、 相应的MIPS 实现 .data str:.asciizEight Queen problems, the number of methods of setting eight queens: .text #main 中变量与保存寄存器和临时储存器的对应： #输入n(=8)：寄存器$s1 #输入iCount：寄存器$s2 #函数Queen(n,QUEEENS,iCount)的返回值：寄存器$v0 #函数Queen(n,QUEENS,iCount)中，n:$a0, QUEENS:$a1, iCount:$a2 #函数Valid(n)的返回值：寄存器$v1 #main function# main: addi $sp,$sp,-32 #利用栈开辟八位数组，site[8] addi $s5,$sp,0 #$s5 指向数组的基址site[0] addi $s2,$zero,0 #iCount=0 li $v0,4 #执行syscall 中的print_int 功能 la $a0,str #printf(Eight Queen problems, the number of methods of setting eight queens:) syscall addi $v0,$zero,8 add $s1,$zero,$v0 #$v0 内的值存入n 中 addi $a0,$zero,0 #$a0=0 add $a1,$0,$s1 #$a1=n add $a2,$0,$s2 #$a2=iCount jal Queen #调用Queen 函数 move $a0,$v0 #函数Queen 返回值存入$a0 li $v0,1 #执行syscall 中的输出整型数的功能，输出最终结果 syscall li $v0,10 #结束程序运行 syscall #Queen 函数变量与保存寄存器和临时寄存器对应： #过程调用中的栈指针：$sp #Queen 函数返回的地址：$ra #Queen 函数内，循环中的i 对应的寄存器：$s4 #Queen 函数中site[n]的地址对应的寄存器：$s6 #Queen function # Queen: addi $sp,$sp,-24 #开辟栈空间 sw $ra,20($sp) #$ra 入栈 sw $v0,16($sp) #$v0 入栈 sw $a0,12($sp) #$a0 入栈 sw $a2,8($sp) #$a2 入栈 sw $s6,4($sp) #$s6 入栈 bne $a0,$a1,exit #n 不等于QUEENS 时exit；n 等于QUEENS，执行下一条指令 addi $a2,$a2,1 #iCount=iCount+1 sw $a2,8($sp) #更新iCount 值，存入栈 j EXIT2 #直接跳到EXIT2 exit: addi $s4,$zero,1 #i=1 sw $s4,0($sp)