CDA3100 - SUMMER 2018 ASSIGNMENT 6 SUDOKU Objectives: Learn how to write an asse
ID: 3910999 • Letter: C
Question
CDA3100 - SUMMER 2018 ASSIGNMENT 6 SUDOKU
Objectives:
Learn how to write an assembly program that consists of functions, learn the MIPS calling conventions, and learn how to access a two-dimensional array in assembly language. This will also be an exercise in gaming and game strategy solutions.
The Classic Sudoku is a number placing puzzle based on a 9x9 grid with several given numbers. The object is to place the numbers 1 to 9 in the empty squares so that each row, each column and each 3x3 box contains the same number only once. The following is an example of a valid Sudoku puzzle.
Write in mips, and make sure it runs on QTSPIM
2
7
1
9
5
4
6
8
3
5
9
3
6
2
8
1
4
7
4
6
8
1
3
7
2
5
9
7
3
6
4
1
5
8
9
2
1
5
9
8
6
2
3
7
4
8
4
2
3
7
9
5
6
1
9
8
5
2
4
1
7
3
6
6
1
7
5
9
3
4
2
8
3
2
4
7
8
6
9
1
5
Specifications:
1. There will be 2 test files:
a. puzzle1.dat # Valid Puzzle.
b. puzzle2.dat # Invalid Puzzle
2. Use the sample code provided to read in the file name, open the file, and read the file into a character array.
3. The file will consist of 81 consecutive integer numbers separated by one space.
a. The first set of 9 numbers will be row 1st, the second set of 9 numbers will be the 2nd row, the third set of 9 numbers will be the 3rd Row, etc.
b. You can assume that the file will be correct and have exactly 81 numbers with no invalid integers ( i.e. less than 0 or greater than 9).
4. Your Program must incorporate the following:
a. parameter passing and return values
b. preserving register values, as presented in class
c. In addition, you should not have any conditional branch instructions that cross function boundaries.
d. A comment beside each instruction is required in the assembly program (or at a minimum a comment for a small group of related instructions) to help make your code more understandable. You should also have comments at the top of the file indicating your name, this course, and the assignment.
5. Your program must indicate whether the file that was submitted represents a valid solution, or whether there is an error in the row, column, and/or 3x3 quadrant.
Grading
In order to be graded the program must assemble and allow the grader to start the program.
- 10% - Proper declaration of the 2d array and references the array properly
- 10% - Program properly documented
- Contains comments that identifies the programmer - Contains comments that describe how the program works.
- 25% - Program is modular.
~ Has functions with at least one instance of passing parameters using standard calling conventions and preserving registers.
~ Has functions with at least one instance of returning a value using standard calling conventions and preserving registers - 55% - Correct implementation.
~ 10% Identifies valid files and continues to ask for a valid false
~ 15% Identifies valid Sudoku solutions
~ 30% Identifies errors with individual errors in Rows, Columns, or 3x3 Quadrants
input.dat File
SampleCode:
#
##################################################################
# # File: ReadFile.s #
# # Description: Query the user for a file name. We assume it #
# # must be a completepath name since we cannot anticipate where #
# # QTSPIM will expect a local file. # #
# # The routine (OFile) will read in the filename and try to #
# # open it. If cannot it will continue to ask the user for a #
# # valid filename. Once successful, the file point will be #
# # passed back to the calling routine. #
# # Author: Dr. David A. Gaitros #
# # #
# # Date: June 25th, 2018 #
# # Copyright: This code is property of FSU Department of #
# # Computer Science, written by Dr. David A. Gaitros for #
# # the sole use of students taking #
# # courses at the University. Distrubution is not #
# # authorized. #
# ###############################################################
.data
Hello: .asciiz "Hello,Enter a file name: "
NoFile: .asciiz "Error encountered, file did not open "
OkFile: .asciiz "File was opened "
Filen: .space 256 # Set aside 256 Characters
EOL: .byte ' '
sudoku: .space 164
NullCh: .word 0 # Just in case we need a null
character
# After the puzzle.
.align 2 # Align on full word boundar
.text
.globl main
main:
#
#################################################################
# Save the return address ($ra) and call the Open File function (Ofile). #
#
#################################################################
addiu $sp,$sp,-4 # Get space from the stack
sw $ra,0($sp) # Store return address on stack
la $a0,Filen # Load $a0 (parameter) with addres to store filename.
jal OFile # Call Open File
#
#################################################################
# # Save the file pointer in saved register $s1. Restore the return address #
# # and stack pointer.
#
#
##################################################################
move $s1,$v0 # Save Filename pointer to $s1
lw $ra,0($sp) # Restore return address
addiu $sp,$sp,4 # Restore stack pointer
la $a0,OkFile # Get ready to print success message
li $v0,4 # Tell syscall to print a string
syscall
li $v0,14
move $a0,$s1 # pass file pointer
la $a1,sudoku # Where to store the data
li $a2,164 # Size of buffer to read in
syscall
#
#################################################################
# # This code just to make sure we read it in properly.
#
#
#################################################################
li $v0,4
la $a0,sudoku
syscall
jr $ra # Close program
#
##################################################################
# Function to read from standard input a filename and open a file.
#
# Send the address of where to store the filename in $a0.
#
# Return the file pointer in $v0.
#
#
##################################################################
OFile:
move $t1,$a0 # Move address of where we want the file name to go to
Again: # $t1
li $v0,4 # Tell syscall to print a string
la $a0,Hello # Load address of string to print
syscall # Print string
move $a0,$t1 # Load $a0 with the address of where we want the Filename to go.
li $a1,264 # Load max size of string
li $v0,8 # Tell syscall to read a string
syscall # Read a string
#
##################################################################
# # Ok, we have read in a string.. Now we want to scan the string and find a line #
# # feed (the number 10 or hex A) and replace it with binary zeros which is a #
# # null character.
#
#
##################################################################
la $t2,EOL # EOL is the character after the filename
# declaration.
sub $t3,$t2,$t1 # Subtract the address of the EOL from the address of the Filen to get the length
move $t4,$t1 # Put address of filename in $t4
GetB: lb $t5,0($t4) # load byte into $t5
li $s5,10 # Load line feed in $s1
beq $t5,$s5,Done # Go to Done when line feed found
addiu $t4,$t4,1 # Get next byte
j GetB
Done:
li $s5,0 # Load zero (null character) into $s1
sb $s5,0($t4) # Replace the line feed with null character
#
##################################################################
# # Try to open the file, If it works move the file pointer to $v0 and return. #
# # If not, go back and read in another filename.
#
#
#################################################################
li $v0,13 # tell syscall to open a file
move $a0,$t1 # Move address of file in $a0
li $a1,0 # Open for reading
li $a2,0 # No purpose
syscall # Open file
move $s6,$v0
ble $s6,$zero,Again # Bad file, try it again.
move $v0,$s6
jr $ra
#
##################################################################
#
#################################################################
2
7
1
9
5
4
6
8
3
5
9
3
6
2
8
1
4
7
4
6
8
1
3
7
2
5
9
7
3
6
4
1
5
8
9
2
1
5
9
8
6
2
3
7
4
8
4
2
3
7
9
5
6
1
9
8
5
2
4
1
7
3
6
6
1
7
5
9
3
4
2
8
3
2
4
7
8
6
9
1
5
Sample Output: puzzlel.dat file 1112131415161718191 14151617181911 12131 71819111213141516 121311151614191718 1516141819171311121 81917121311161415 131112161415181917 614151917181213111 91718131112151614 Valid Sudoku PuzzleExplanation / Answer
data Segment
board db 1,0,0,0,0,0,0,0,0
db 0,2,0,0,0,0,0,0,0
db 0,0,3,0,0,0,0,0,0
db 0,0,0,4,0,0,0,0,0
db 0,0,0,0,5,0,0,0,0
db 0,0,0,0,0,6,0,0,0
db 0,0,0,0,0,0,7,0,0
db 0,0,0,0,0,0,0,8,0
db 0,0,0,0,0,0,0,0,9,'$'
board2 db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,10
db 0,0,0,0,0,0,0,0,0,'$'
data Ends
code Segment
Assume CS:code,DS:data
start:
mov ax,data
mov ds,ax
lea si,board
l1:
mov al,[si]
cmp al,'$' ;stop when end of array
jz EN
cmp al,0 ;find blank space
jz l6
inc si
jmp l1
l6:
mov cx,09
l2:
inc al
call check ;check for validity of number
jc l3
jnc l4
l3:
mov [si],al ;move to next number
push ax
dec cx
push cx
mov bx,si
push bx
inc si
jmp l1
l4: ;check for next number if not possible then
;bactrack
cmp cx,1
jz l5
loop l2
l5:
mov ah,0
mov [si],ah
lh:
pop bx
lea si,board
add si,bx
pop cx
pop ax
cmp cx,00
jz lx
jnz l2
lx:
mov ah,0
mov [si],ah
jmp lh
EN: ;printing the board
mov cx,81
lea si,board
ll:
mov al,[si]
add al,48
mov [si],al
inc si
loop ll
lea di,board2
lea si,board
l22:
mov cx,09
op:
mov al,[si]
mov [di],al
inc si
inc di
loop op
mov al,[di]
inc di
cmp al,'$'
jnz l22
lea si,board2
lea di,board2
mov ah,09
lea dx,board2
int 21h
hlt
check proc ;call to check function
push ax
mov bx,si
push bx
push cx
xor bx,bx
mov bl,al
xor ax,ax
mov ax,si
mov bh,09
div bh
mov bh,ah
lea si,board
mov cx,09
mov ah,00
mul cx
add si,ax
mov ah,bh
xor cx,cx
mov cx,09
l8:
mov bh,[si]
cmp bh,bl
jz l7
inc si
loop l8
mov al,ah
mov ah,00
lea si,board
add si,ax
mov cx,09
l10:
mov bh,[si]
cmp bh,bl
jz l7
add si,09
loop l10
xor ax,ax
mov al,bl
pop cx
pop bx
push bx
push cx
xor cx,cx
mov bh,al
mov al,bl
mov bl,27
push ax
div bl
mov ah,00
mul bl
pop cx
push ax
mov ax,cx
mov bl,09
div bl
mov al,ah
mov ah,00
mov bl,03
div bl
mov ah,00
mul bl
pop cx
add ax,cx
lea si,board
add si,ax
mov bl,[si]
cmp bh,bl
jz l7
inc si
mov bl,[si]
cmp bh,bl
jz l7
inc si
mov bl,[si]
cmp bh,bl
jz l7
add si,09
mov bl,[si]
cmp bh,bl
jz l7
dec si
mov bl,[si]
cmp bh,bl
jz l7
dec si
mov bl,[si]
cmp bh,bl
jz l7
add si,09
mov bl,[si]
cmp bh,bl
jz l7
inc si
mov bl,[si]
cmp bh,bl
jz l7
inc si
mov bl,[si]
cmp bh,bl
jz l7
pop cx
pop bx
lea si,board
add si,bx
pop ax
stc
jmp l11
l7:
pop cx
pop bx
lea si,board
add si,bx
pop ax
clc
l11:
ret
check Endp
code Ends
End start