SRL Archive - General

Write a MIPS Assembly program that produces a graphical representation of all of the solutions for the Eight Queens Problem.
In a nutshell ( its a problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

This is what I have so far. I need help printing the solution. Any suggestions

main:
    # variables:
    # s0 : curr = 0
    # s1 : count = 0
    # s2 : row = 0
    # s3 : pos = 0
    # s4 : vert = 0
    # s5 : ldiag = 0
    # s6 : rdiag = 0

    li s0, 0
    li s1, 0
    li s2, 0
    li s3, 0
    li s4, 0
    li s5, 0
    li s6, 0
    
    LOOP:
        # if pos == 8 and row == 0: BREAK
            addi t0, s3, -8       # t0 = s3 - 8
            or t0, t0, s2        # t0 = t0 or s2
            beq t0, zero, BREAK   # if not t0 goto BREAK
        
        # if row == 8: SUCCESS
            addi t0, s2, -8
            beq t0, zero, SUCCESS # if t0 == 0 goto SUCCESS
        
        # if pos == 8 and row != 0: POP
            addi t0, s3, -8       # t0 = s2 - 8
            bne t0, zero, PUSH
            bne s2, zero, POP
            j PUSH
        
        SUCCESS:
            andi s3, s0, 7        # pos = curr & 7
            srl s0, s0, 3         # curr = curr >> 3
            
            # vert = vert & (~(1 << pos))
                li t0, 1
                sllv t0, t0, s3
                li t1, -1
                xor t0, t0, t1
                and s4, s4, t0
            
            addi s2, s2, -1       # row -= 1
            
            # ldiag = ldiag & (~(1 << (7 - row + pos)))
                li t0, 1
                li t1, 7
                sub t1, t1, s2
                add t1, t1, s3
                sllv t0, t0, t1
                li t1, -1
                xor t0, t0, t1
                and s5, s5, t0
            
            # rdiag = rdiag & (~(1 << (row + pos)))
                li t0, 1
                add t1, s2, s3
                sllv t0, t0, t1
                li t1, -1
                xor t0, t0, t1
                and s6, s6, t0
            
            addi s3, s3, 1        # pos += 1
            addi s1, s1, 1        # count += 1

            j LOOP                  # continue
            
        POP:
            andi s3, s0, 7        # pos = curr & 7
            srl s0, s0, 3         # curr = curr >> 3
            
            # vert = vert & (~(1 << pos))
                li t0, 1
                sllv t0, t0, s3
                li t1, -1
                xor t0, t0, t1
                and s4, s4, t0
            
            addi s2, s2, -1       # row -= 1
            
            # ldiag = ldiag & (~(1 << (7 - row + pos)))
                li t0, 1
                li t1, 7
                sub t1, t1, s2
                add t1, t1, s3
                sllv t0, t0, t1
                li t1, -1
                xor t0, t0, t1
                and s5, s5, t0
            
            # rdiag = rdiag & (~(1 << (row + pos)))
                li t0, 1
                add t1, s2, s3
                sllv t0, t0, t1
                li t1, -1
                xor t0, t0, t1
                and s6, s6, t0
            
            addi s3, s3, 1        # pos += 1
            
            j LOOP
            
        PUSH:
            li t0, 1
            sllv t6, t0, s3      # t6 = t_vert = 1 << pos
            
            li t0, 1
            li t1, 7
            sub t1, t1, s2
            add t1, t1, s3
            sllv t5, t0, t1      # t5 = t_ldiag = 1 << (7 - row + pos)
            
            li t0, 1
            add t1, s2, s3
            sllv t4, t0, t1      # t4 = t_rdiag = 1 << (row + pos)
            
            and t7, s4, t6       # t7 = fail = vert & t0

            and t0, s5, t5       # t0 = ldiag & t5
            or t7, t7, t0        # fail = fail | t0

            and t0, s6, t4       # t0 = rdiag & t4
            or t7, t7, t0        # fail = fail | t0
            
            # if fail: FAIL
            bne t7, zero, FAIL
                sll s0, s0, 3     # curr = curr << 3
                or s0, s0, s3    # curr = curr | pos
                or s4, s4, t6    # vert = vert | t_vert
                or s5, s5, t5    # ldiag = ldiag | t_ldiag
                or s6, s6, t4    # rdiag = rdiag | t_rdiag
                li s3, 0           # pos = 0
                addi s2, s2, 1    # row += 1
                j LOOP
            FAIL:
                addi s3, s3, 1    # pos += 1
                j LOOP
    
    BREAK:
    li v0, 1
    move a0, s1
   
    
    jr ra

If it's not actually a GUI as in WinAPI or X11 then you can use the console.. Aka ASCII/Unicode characters to draw the board and the pieces:

https://villavu.com/forum/showthread.php?t=57193&page=4

And

http://en.m.wikipedia.org/wiki/Chess_symbols_in_Unicode

I'm posting this from my phone so I have no code for you atm, but you get the idea?

What part of printing are you having difficulty with?

The part im having trouble with is coming up with a way to print the solution with the board and what not. I've been raking my brain but nothing at the moment.

Given that im using MIPS, i more than likely wont be using GUI

From: rmorris7
The part im having trouble with is coming up with a way to print the solution with the board and what not. I've been raking my brain but nothing at the moment.

Do it in another language first then translate it?

Example:

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

void print_slim_row(int black_first, char queen)
{
    int i = 0, j = 0;

    for(; i < 4; ++i)
    {
        for (j = 0; j < 8; ++j)
            printf("%c", !!black_first ? 178 : 32);

        for (j = 0; j < 8; ++j)
            printf("%c", !!black_first ? 32 : 178);
    }

    printf("\r\n");
}

void print_full_board()
{
    int i = 0, j = 0;
    for(; i < 4; ++i)
    {
        for (j = 0; j < 4; ++j)
            print_slim_row(true);

        for (j = 0; j < 4; ++j)
            print_slim_row(false);
    }
}

int main()
{
    print_full_board();
}

Would print the following board:


Then if you modify the above code, and add in the following unicode char: ♕

You may fill in the white spots with the ascii char 178 and fill in the queen spots with \u9813; (the queen character in unicode) and fill in the black spots with ascii char 32 (aka space).

Printing it will show just fine. Or simply print a "Q" for if you want..


And now the finale.. after modifying an already existing rosetta code solution:

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

void solve(int n, int col, int *hist)
{
	if (col == n) {
        printf("\n\n\n\n");
		for (int i = 0; i < n; ++i)
        {
            for (int l = 0; l < 2; ++l)
            {
                for (int j = 0; j < n; ++j)
                {
                    char c = j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : 178;
                    for (int k = 0; k < 4; ++k)
                        putchar(c);
                }
                putchar('\n');
            }
        }

		return;
	}

    #define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
	for (int i = 0, j = 0; i < n; ++i) {
		for (j = 0; j < col && !attack(i, j); ++j);
		if (j < col) continue;

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

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

and the result (note that you can make the board as large as you want by modifying the for-loops):

now.. translate that to assembly (mips) and voila.. If you need help doing that, let me or someone that knows asm/mips know..

Alright yea, translation isnt my forte, but I can see where you're going,how exactly would this look in MIPS

From: rmorris7
Alright yea, translation isnt my forte, but I can see where you're going,how exactly would this look in MIPS

I didn't get to translate/write all of it but here goes:

#include <mips.h>


.data
next_set: .asciiz "\n\n\n"
hist:  .word 4, 5, 6, 7, 0, 0, 0, 0
.text
.globl main


main:
  subiu $sp, $sp, 40  #allocate 40 bytes on the stack
  sw $ra, 36($sp)     #save the return address.
  
  li $4, 8            #push n
  li $5, 0            #push col 
  la $6, hist         #push hist
  jal solve           #call solve  
  
  addiu $sp, $sp, 40  #deallocate 40 bytes on the stack
  sw $ra, 36($sp)     #pop restore return address.
  li $v0, 10          #mov eax, 0
  syscall             #ret
  
  
  
solve:
    bne $5, $4, atk  #if col == n
    li $v0, 4             #get ready to print string.
    la $a0, next_set      #push string onto stack
    syscall               #printf("\n\n\n")
    
    	#for (int i = 0; i < n; ++i)
    	li $t1, 0                #i = 0.
    	lf1:
    		beq $t1, $4, lf1e     #i == 10? end the loop.
    	  	#for (int j = 0; j < 2; ++j)
    	  	li $t2, 0              #j = 0.
    	  	lf2:
    	    		beq $t2, 2, lf2e
    	    		#for (int k = 0; k < n; ++k)
    	    		li $t4, 0            #k = 0
    	    		lf3:
    	      			beq $t4, $4, lf3
    	      			#char c = k == hist[i] ? 'Q' : ((i + k) & 1) ? ' ' : 178
    	      			bne $t4, $6, eff      #if j == hist[i]
    	      			lb  $t9, 'Q'          #c = 'Q'
    	      			j eaf
    	      			
    	      			#else if (i + k & 1)
    	      			eff:
    	      			move $t6, $t1        #put i into temp register for arithmetic.
    	      			add $t6, $t6, $t4    #i + k
    	      			and $t6, $t6, 1      #i + k & 1
    	      			beqz $t6, eee        #if (i + k & 1) == 0 go to the else statement
    	      			lb $t9, 32          #c = ' '
    	      			j eaf
    	      			
    	      			#else
    	      			eee:
    	      			lb $t9, 178         #c = ascii 178.
    	      			
    	      			eaf:
    	      			
    	      			move $13, $t9       #save c.  probably better to use sb instruction.
    	      			#for (int l = 0; l < 4; ++l)
    	      			li $t6, 4
    	     			li $t9, 0           #l = 0
    	      			lf4:
    	        			beq $t9, $t6, lf4e
    	        			li $v0, 4
    	        			move $a0, $13
    	        			syscall          #putchar(c)
    	        			li $a0, 0
    	        			addi $t9, $t9, 1  #++l
    	        			j lf4
    	      			lf4e:
    	      			add $t4, $t4, 1    #++k
    	      			j lf3
    	    		lf3e:
    	    		addi $t2, $t2, 1     #++j
    	    		j lf2
    	  	lf2e:
    	  	addi $t1, $t1, 1       #++i
    	  	j lf1
    	lf1e:


    atk:
    	li $t0, 0  #i = 0
    	li $t1, 0  #j = 0
    	lfatk1:
    		beq $t0, $4, lfatk1e  #if i == n
        	lfatk2:
        		beq $t1, $5, lfatk2e  #if j == col
        		
    			move $7, $t0
    			move $8, $t1
    			jal attack
    			beqz $v0, lfatk2e    #if !attack(i, j)
    			
    			addi $t1, $t1, 1     #++j
    			blt $t1, $5, lfatk2  #continue
    			
    			mul $t2, $5, 4       #calculate array offset.
    			add $t2, $t2, $6     #offset the hist address.
    			sw $t3, 0($t2)       #hist[col] = i
    			addi $5, $5, 1
    			jal solve
    		lfatk2e:
    		addi $t0, $t0, 1
    		j lfatk1
    	lfatk1e:
    atke:
  jr $ra #ret
  
  
  #define attack.. as a separate function:
  attack:
  
    move $t1, $6       #hist
    mul $t2, $7, 4     #calculate true offset
    add $t1, $t1, $t2  #load hist[j] into $t1
    lw $t2, 0($t1)     #t2 = hist[j]
    sub $t3, $t2, $8   #t3 = hist[j] - i
    
    
    #t3 = abs(t3)
    sra $t4, $t3, 31
    xor $t3, $t3, $t4
    sub $t3, $t3, $t4
    
    sub $t4, $5, $7   #t4 = col - j
    
    bne $t2, $8, acmp2   #hist[j] == i
    bne $t2, $t4, acmp1  #[hist[j] == col - j
    lw $v0, 1            #return true.
    jr $ra
    acmp2:
    beqz $t3, acmp1      #abs(hist[j] - i) != 0
    bne $t3, $t4, acmp1  #abs(hist[j] - i) == col - j
    lw $v0, 1            #return true
    jr $ra
    acmp1:
    li $v0, 0            #return false
  jr $ra

I tried to comment as much of it as possible. Probably too much tbh.. Everything is implemented except the LAST TWO for-loops that call "attack". Looks nasty as hell right now.. Hopefully I didn't mess up anything. The above is a direct translation. You can optimise it a ton and change some things.

I can translate the last few things later but I got some stuff to do first.

I am more than grateful for your contribution here, the attack part, I can pretty much follow the code up until here, by chance where are you going with this part?

From: rmorris7
I am more than grateful for your contribution here, the attack part, I can pretty much follow the code up until here, by chance where are you going with this part?

Sorry for the late reply.. Been busy these last few days.. Hopefully you still have time to hand in the assignment..


I re-wrote most of it from scratch and made it customizable so that you can specify which char should be white, what should be black, what should be blank, etc.. I optimised it by hand and made sure things are efficient. I made the code a ton shorter and easier to read and understand..

So far, the first part actually works correctly:

QWBWBWBW
WBWBQBWB
BWBWBWBQ
WBWBWQWB
BWQWBWBW
WBWBWBQB
BQBWBWBW
WBWQWBWB


I just need to figure out what's wrong with my "solve_atk" label/section.

#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, 4, 7, 5, 2, 6, 1, 3

.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:
	jr $ra  #return;
	
	
	solve_atk:
		#SOMETHING WRONG HERE..
	solve_atk_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)
    lw $t1, 12($sp)
    add $t0, $t0, $t1
	lw $t0, 0($t0)      #hist[j]	
	sub $t1, $t0, $a0
	
	li $v0, 0
	beqz $t1, attack_or  #if hist[j] != i
	li $v0, 1            #return true.
	j attack_done
	
	attack_or:
		abs $t1, $t1
		sub $t0, $a2, $a0
		bne $t0, $t1, attack_done
		li $v0, 1
	
    attack_done:
jr $ra


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

For the atk section I used:

##; The following section when translated to ASM is broken.. I messed up somewhere.. ##
#;
#;    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);
#;    }

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)
    		j solve
            
            solve_atk_for_1_continue:
            
        addiu $t3, $t3, 1  #++i
        j solve_atk_for_1
		solve_atk_for_1_end:

I can't see what's wrong with it atm but something is wrong.. Either the recursive call to "solve" is messed up or the entire section itself.
I know it's this specific bit of code that's off somewhere because the test cases all work fine.

I just don't have enough free time atm.. Maybe tonight I'll get around to fixing it so that you can have it fully working. For now, you can try and figure out what went wrong..

Thanks for all your help, ill continue to work on this