CMPUT 229 - Computer Organization and Architecture I

Lab 3: Sudoku Validator

Introduction

The purpose of this lab is to validate the accuracy of a simple number puzzle called Sudoku. While working on this lab you will learn how to write code that handles two-dimensional arrays, register calling conventions, and implementing functions in RISC-V.

Background

What is Sudoku? Sudoku is a number puzzle where the goal is to fill in a 9x9 grid with the correct numbers ranging from 1 to 9. In a correct solution, each of the numbers 1 to 9 appear only once in each row, in each column, and in each 3x3 region. To illustrate, below are four drawings of the same valid solution to a Sudoku puzzle. The blue lines highlight regions, rows, and columns. Inside all blue boxes in each example are all numbers 1 to 9. You can try solving a Sudoku puzzle here.

8
9
2
4
5
6
7
1
3
5
3
1
7
8
2
4
6
9
6
7
4
1
9
3
5
2
8
3
4
6
2
7
1
9
8
5
7
8
5
9
6
4
2
3
1
2
1
9
8
3
5
6
4
7
9
2
3
5
4
8
1
7
6
1
6
7
3
2
9
8
5
4
4
5
8
6
1
7
3
9
2
8
9
2
4
5
6
7
1
3
5
3
1
7
8
2
4
6
9
6
7
4
1
9
3
5
2
8
3
4
6
2
7
1
9
8
5
7
8
5
9
6
4
2
3
1
2
1
9
8
3
5
6
4
7
9
2
3
5
4
8
1
7
6
1
6
7
3
2
9
8
5
4
4
5
8
6
1
7
3
9
2
8
9
2
4
5
6
7
1
3
5
3
1
7
8
2
4
6
9
6
7
4
1
9
3
5
2
8
3
4
6
2
7
1
9
8
5
7
8
5
9
6
4
2
3
1
2
1
9
8
3
5
6
4
7
9
2
3
5
4
8
1
7
6
1
6
7
3
2
9
8
5
4
4
5
8
6
1
7
3
9
2
8
9
2
4
5
6
7
1
3
5
3
1
7
8
2
4
6
9
6
7
4
1
9
3
5
2
8
3
4
6
2
7
1
9
8
5
7
8
5
9
6
4
2
3
1
2
1
9
8
3
5
6
4
7
9
2
3
5
4
8
1
7
6
1
6
7
3
2
9
8
5
4
4
5
8
6
1
7
3
9
2

Assignment

The goal of this lab is to write a program in RISC-V that checks if a completed Sudoku is valid. You must write the functions sudokuValidator, and validateArea with the following specifications: 


sudokuValidator:
This function checks the validity of a given Sudoku.

    Arguments:
    a0: pointer to a 2D 9x9 array of the input Sudoku where each item is a one-byte integer

    Return:
    a0: Sudoku validity
        - returns 1 if valid, 0 if not
    a1: valid rows (more info below)
    a2: valid columns (more info below)
    a3: valid regions (more info below)

a1-a3 return registers are used to show the validity of each row, column, and region.
The values returned in these registers have the following properties:

  • each bit in the register numbered 0 to 8 corresponds to an index (see bit mapping)
  • a bit should be a 1 if the row, column, or region corresponding to the bit index is valid and 0 if it is not valid.
  • All bits of the register that does not correspond to an index must be 0.

The above function should call the following function: 


validateArea:
This function checks if a given row, column, or region is valid.

    Arguments:
    a0: pointer to a 2D 9x9 array of the input Sudoku where each item is a one byte integer
    a1: the type of area to check
        0 for a row
        1 for a column
        2 for a region
    a2: integer value specifying which row, column, or region to validate
        - this value will be from 0 to 8

    Return:
    a0: row, column, or region validity
        - return 1 if valid, 0 if not

You can make any other helper functions as long as they do not share a name with any labels already used in the common.s file.

Bit Mapping

The bits in the return registers a1-a3 in sudokuValidator that are numbered 0 to 8, which correspond to a row, column, or region, are mapped as shown:

0
1
2
3
4
5
6
7
8
0
0
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8

The above mapping shows the bit index numbers for all rows, columns, and regions. For clarity, see the example on the right which shows the correct validity bit for each bit index number using this mapping.

Example:

2
1
5
6
4
7
8
3
9
9
6
4
8
3
2
7
9
1
8
7
3
9
5
1
6
4
2
1
9
7
4
6
8
5
2
3
4
2
6
3
7
5
1
8
8
3
5
8
2
3
9
4
7
6
7
3
1
5
9
6
2
8
4
5
4
2
1
8
3
9
6
7
6
8
9
7
2
4
3
1
5

                    Bit Index Numbers: 876543210
Sudoku is not valid.                   ↓↓↓↓↓↓↓↓↓
Valid rows are: 00000000000000000000000111001101
Valid cols are: 00000000000000000000000101101111
Valid regs are: 00000000000000000000000111001011

Sudoku Validator in RISC-V

This lab provides the template sudokuValidator.s that should be used to write a sudoku validator for a complete Sudoku. The solution of this lab requires the creation of two functions: sudokuValidator and validateArea. The validateArea function checks if either a single row, column, or region is valid and must be used by the sudokuValidator function. Creating additional helper functions is encouraged.

The directive .include "common.s" in sudokuValidator.s causes RARS to execute the code in the file common.s before executing any code in the solution. The code in common.s allocates space in memory, parses the numbers from the test file into a 2D array of integers, and then calls the sudokuValidator function written as a solution to the lab. It also displays the values for all the return registers from sudokuValidator. You are encouraged to read the code in the common.s file to understand how the whole program works. A solution must have all the required functions, with the exact name, or else it won't run.

Lab Requirements:

2D Arrays

The code in common.s reads a Sudoku text file (see Testing Your Lab for inputting a file) and creates a 2D 9x9 array of 1 byte integers. In memory, a 2D 9x9 array is stored as a linear array of 81 bytes. There are two ways to store an array in memory: row-major order or column-major order. For row-major order, each row is contiguous in memory.

For column-major order, each column is contiguous in memory.

For this lab, the Sudoku is stored in row-major order. For example, in C, you might access a row and column with nums[row][col], but this is equivalent to nums[row*9 + col] or *(nums + row*9 + col), assuming that there are nine elements per row and that each element occupies one byte. In C, this is equivalent to using an array of char.

Functions

A necessary part of this lab is understanding how functions work in RISC-V. Function arguments are stored in the registers a0-a7. Before a function is called these registers must contain the correct values. A function can then be called with a jump-and-link instruction jal ra, myFunction. This instruction stores the return address in the ra register, and jumps to the function myFunction. Before myFunction completes, it should store return values in the registers a0-a7, then call the ret instruction to jump back to the caller whose address is stored in ra.

The sudokuValidator function must contain a return statement so that it will then return to the main program in common.s to display the result.

Calling Conventions and Stack Manipulation

All functions in the solution must follow register-saving conventions. Values from some registers are saved into the stack and are retrieved from the stack later.

The register-saving calling convention separates the registers into different classes. For calee-saved registers, upon the function return to the caller, their values must be exactly the same as at the point of call. The temporary registers t0-t6 and the argument registers a0-a7 are caller-saved registers. A function may change the value of these registers without restoring their values to the original value before returning. Thus, the caller cannot assume that temporary-register values are known after a function call. The function call instruction jal ra, myFunction always changes the value in the ra register. Therefore, any function that calls another function must save the value of ra into the stack before the call is made. It must then restore the original value of ra before executing the return statement. The values of any callee-saved registers s0-s11 must also be saved/restored by the function. The original values should be stored on the stack as illustrated below: 


myFunction:
    addi sp, sp, -12
    sw ra, 0(sp)
    sw s1, 4(sp)
    sw s2, 8(sp)

    # function code here

    lw ra, 0(sp)
    lw s1, 4(sp)
    lw s2, 8(sp)
    addi sp, sp, 12
    ret

Loops

There are many different ways to implement loops in RISC-V. Several examples can be found here: Do-While, While, For.

Bit Manipulation

When manipulating bits, it is useful to work with one bit at a time. One way is to load a single bit into a temporary register. For instance, the instruction li t1, 1 loads the immediate value 1 into t1. Use sll shift left logical to reposition it and use and, or, or xor for combining with other registers. Another useful instruction is not for bit inversion.

Testing Your Lab

Sample test cases can be found in the folder Code/tests/. The correct answers for these tests are provided in the files with same name but '.out' extension. To run a test case, provide the path to testfile as program arguments in RARS simulator. You can also test your lab from terminal with rars LABFILE pa TESTFILE where LABFILE is the path to sudokuValidator.s and TESTFILE is the path to the file that contains the test case you want to test.

The tests provided are not extensive! Additional testing is required to ensure that the solution is correct.

Check My Lab

Link to CheckMyLab

This lab is supported in CheckMyLab. To get started, navigate to the Sudoku Validator lab in CheckMyLab found in the dashboard. From there, students can upload their test cases in the My test cases table (see below). Additionally, students can also upload their `sudokuValidator.s` file in the My solutions table, which will then be tested against all other valid test cases.

Test Case Format

Test cases are plain text files ending in .txt that must be in the following format: 

[a 9x9 sudoku grid, where the numbers are separated by spaces]

Example

8 9 2 4 5 6 7 1 3 
5 3 1 7 8 2 4 6 9 
6 7 4 1 9 3 5 2 8 
3 4 6 2 7 1 9 8 5 
7 8 5 9 6 4 2 3 1 
2 1 9 8 3 5 6 4 7 
9 2 3 5 4 8 1 7 6 
1 6 7 3 2 9 8 5 4 
4 5 8 6 1 7 3 9 2

Assumptions and Notes

  • Do not edit any part of the common.s file. Only the functions written by you will be graded. A solution that requires any edits to common.s to work is likely to be incorrect.
  • Do not use any of the labels that are already used in common.s
  • The Sudokus used for grading will only use numbers 1 to 9 and will always be a complete 9x9 Sudoku.
  • Ensrue that there is a return at the end of your sudokuValidator function to continue executing common.s.
  • Remember to respect all the register-calling conventions or you will lose marks. Always save/restore any s registers that were changed before returning from a function.

Resources

  • Slides used for in-class introduction of the lab (.pptx) (.pdf)
  • Marksheet used to mark the lab (.txt)

Marking Guide

Assignments too short to be adequately judged for code quality will be given a zero for that portion of the evaluation.

Since sudokuValidator return register a0 and any returns from validateArea have only 2 possible values, any incorrect returns will count against a correct return. This means that guessing will not be effective.

  • 10% for correctly determining valid Sudokus (correct a0 return value for sudokuValidator).
  • 10% for correctly determining valid rows register bit pattern (correct a1 return value for sudokuValidator)
  • 10% for correctly determining valid columns register bit pattern (correct a2 return value for sudokuValidator)
  • 10% for correctly determining valid regions register bit pattern (correct a3 return value for sudokuValidator)
  • 10% for correctly determining single valid rows (correct return value for validateArea when a1 is 0)
  • 10% for correctly determining single valid columns (correct return value for validateArea when a1 is 1)
  • 20% for correctly determining single valid regions (correct return value for validateArea when a1 is 2)
  • 20% for code cleanliness, readability, and comments

Submission

There is a single file to be submitted for this lab: sudokuValidator.s which should contain the code for sudokuValidator, validateArea, and all supporting functions.

  • Do not add a main label to this file.
  • Do not modify the line .include "common.s".
  • Keep the file sudokuValidator.s in the Code folder of the git repository.