Results 1 to 10 of 10

Thread: Advice with extra credit assignment

  1. #1
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default Advice with extra credit assignment

    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
    Code:
    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

  2. #2
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    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?
    Last edited by Brandon; 12-04-2014 at 08:30 PM.
    I am Ggzz..
    Hackintosher

  3. #3
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default

    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.

  4. #4
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default

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

  5. #5
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Quote Originally Posted by rmorris7 View Post
    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:

    c Code:
    #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:

    c Code:
    #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..
    Last edited by Brandon; 12-04-2014 at 11:58 PM.
    I am Ggzz..
    Hackintosher

  6. #6
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default

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

  7. #7
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Quote Originally Posted by rmorris7 View Post
    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:

    ASM Code:
    #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.
    Last edited by Brandon; 12-05-2014 at 07:44 PM.
    I am Ggzz..
    Hackintosher

  8. #8
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default

    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?

  9. #9
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    Quote Originally Posted by rmorris7 View Post
    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.


    Asm Code:
    #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:

    ASM Code:
    ##; 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..
    Last edited by Brandon; 12-06-2014 at 08:18 PM.
    I am Ggzz..
    Hackintosher

  10. #10
    Join Date
    Nov 2014
    Posts
    12
    Mentioned
    0 Post(s)
    Quoted
    7 Post(s)

    Default

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

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •