Assignment 1: sudoku in MIPS

version: 1.2 last updated: 2025-10-01 08:55:00

Aims

• to give you experience writing MIPS assembly code
• to give you experience translating C to MIPS
• to give you experience with data and control structures in MIPS
• to gain understanding of how a CPU processes and executes your code.

Getting Started

Create a new directory for this assignment called sudoku, change to this directory, and fetch the provided code by running these commands:

mkdir -m 700 sudoku
cd sudoku
1521 fetch sudoku

If you're not working at CSE, you can download the provided files as a zip file or a tar file.

This will add the following files into the directory:

• sudoku.s: a stub MIPS assembly file to complete.
• sudoku.c: a reference implementation of sudoku in C.
• sudoku.simple.c: a copy of the reference implementation of sudoku, for you to simplify.
• input.txt: example user input file for automation.
• sudoku.mk: a make(1) fragment for compiling sudoku.c.

Sudoku: The Game

sudoku.c is an implementation of Sudoku. In classic Sudoku the goal is to fill a 9x9 grid with the digits 1-9 so that each digit appears once in each row, column and box. Each box is a 3x3 subsection of the grid.

Our implementation also supports 4x4 and 16x16 grids.

The provided C program (and eventually, your MIPS translation) implements the following commands:

• e <row> <col> <digit> enters digit at (row, col).
• h prints instructions.
• i gives the user a hint.
• q exits sudoku.

Sudoku is lost if a user makes too many mistakes.

If the user enters a correct digit it is placed on the grid. If the user enters an incorrect digit, they are notified and this counts as a mistake. If the user makes more than 10 mistakes, the game is over.

To get a feel for this game, try it out in a terminal:

dcc sudoku.c -o sudoku
./sudoku

sudoku.s: The Assignment

Your task in this assignment is to translate the provided sudoku.c program into MIPS assembly.

You must add code to the provided sudoku.s file so that it executes exactly the same as sudoku.c.

Any modifications to the .data section are NOT PERMITTED, and will break autotest.

All global variables and strings are already present in the provided .data section.

You have to implement the following functions in MIPS assembly:

• main
• print_welcome
• get_box_num
• in_bounds
• find_box_len
• game_loop
• update_game_state
• option_is_valid
• generate_puzzle
• initialise_game
• cell_display_char
• initialise_board
• initialise_digit_choices
• is_cell_filled
• handle_move
• update_cell
• solve
• make_user_puzzle
• give_hint
• copy_mem

The following functions have already been translated to MIPS assembly for you:

• random_in_range
• process_command
• cell_char_to_num
• do_enter
• print_hint_msg
• initialise_board_tracker
• is_valid_digit
• print_puzzle
• print_row
• print_box_separator

You MUST obey the MIPS calling conventions discussed in lectures.

When translating functions calls, avoid making assumptions about any side effects of the called function. If you make assumptions about the behaviour of called functions that are not made in the provided C implementation, you may be penalised.

Subsets

This assignment is split into four subsets. Later subsets will involve more complex translation.

Please note that the weighting for Subset 3 includes whole_prog automarking.

Running & Testing

To run your MIPS code, simply enter the following in your terminal:

1521 mipsy sudoku.s

Recommended testing approach

After you have translated all functions and your code is passing all of the Function tests, it is recommended to use the Whole program tests to determine if your solution has any bugs missed by the Function tests.

It is particularly common to find bugs relating to your conformance to the MIPS calling convention in Subset 3 (use of clobbered registers, overwriting saved registers), as the provided autotests for Subset 3 do not check for this.

Automated testing

There are two types of autotests for this assignment:

1. Whole program tests
2. Function tests

Whole program tests run your entire sudoku.s file and compare the observed output against the expected output. These tests are generally not practical until most or all of your functions have been implemented in MIPS.

Function tests only test individual functions from sudoku.s. These tests isolate a function and run it separately to the rest of your solution. For example, you can test the main function with:

1521 autotest sudoku main

Manual Testing

The game takes a lot of input, so it's a good idea to write a file with the input you want to test, and then pipe that into your program using the shell commands below.

You have been given a file called input.txt to use for this.

>> compile the C implementation <<
dcc sudoku.c -o sudoku
>> run the C implementation with the inputs in input.txt, storing output in c.out <<
cat input.txt | ./sudoku | tee c.out
>> run the your mips implementation with the inputs in input.txt, storing output in mips.out <<
cat input.txt | 1521 mipsy sudoku.s | tee mips.out
>> automatically compare the two output files and report differences <<
diff -s c.out mips.out
Files c.out and mips.out are identical

Try this with different sequences of inputs (with different inputs stored inside input.txt).

You are not required to use this testing method. Inputting manually is perfectly fine, it is just a bit tedious.

Simplified C code

You are encouraged to simplify your C code to remove any loop constructs and if-else statements, and test that your simplified code works correctly before translating it to MIPS, in a separate file sudoku.simple.c.

This file will not be marked - you do not need to submit it.

In order to allow you to check that your simplified code works correctly, we have provided a simple set of automated tests.

You can run these tests using the following command:

1521 autotest sudoku.simple

Hints

• You should implement all the functions from one subset before moving on to the next.

• You may find the provided function implementations to be useful guidance for your implementation, including comments, label names, indentation and register usage.

An example game of Sudoku

1521 mipsy sudoku.s
Welcome to Sudoku!
To enter a number, use: e   
To get a hint, use: i
To see this message again, use: h
To exit, use: q
You can use up to 10 hints.
If you make more than 10 mistakes, you lose :(

Board size options: 4 => 4x4, 9 => 9x9, 16 => 16x16
Enter a board size: 4
Difficulty options: 1 => easy, 2 => medium, 3 => hard, 4 => extreme
Enter a difficulty level: 2
Enter a random seed: 18
 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|     | 4 1 |
-+-----+-----|
2|   4 | 3 2 |
3| 3   | 1   |
-+-----+-----|
8 cells remaining...
0/10 mistakes before game over.
0/10 hints used.
> e 2 0 1
Success!!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|     | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3   | 1   |
-+-----+-----|
7 cells remaining...
0/10 mistakes before game over.
0/10 hints used.
> e 3 1 3
Mistake!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|     | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3   | 1   |
-+-----+-----|
7 cells remaining...
1/10 mistakes before game over.
0/10 hints used.
> e 3 1 2
Success!!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|     | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1   |
-+-----+-----|
6 cells remaining...
1/10 mistakes before game over.
0/10 hints used.
> e 3 3 4
Success!!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|     | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|
5 cells remaining...
1/10 mistakes before game over.
0/10 hints used.
> i
HINT: 3 at (1, 1)
1 hints used, 9 left.

 | 0 1 | 2 3 |
-+-----+-----|
0| 4   |     |
1|   3 | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|
4 cells remaining...
1/10 mistakes before game over.
1/10 hints used.
> i
HINT: 1 at (0, 1)
2 hints used, 8 left.

 | 0 1 | 2 3 |
-+-----+-----|
0| 4 1 |     |
1|   3 | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|
3 cells remaining...
1/10 mistakes before game over.
2/10 hints used.
> e 1 0 2
Success!!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4 1 |     |
1| 2 3 | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|
2 cells remaining...
1/10 mistakes before game over.
2/10 hints used.
> e 0 2 2
Success!!

 | 0 1 | 2 3 |
-+-----+-----|
0| 4 1 | 2   |
1| 2 3 | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|
1 cells remaining...
1/10 mistakes before game over.
2/10 hints used.
> e 0 3 3
Success!!
 | 0 1 | 2 3 |
-+-----+-----|
0| 4 1 | 2 3 |
1| 2 3 | 4 1 |
-+-----+-----|
2| 1 4 | 3 2 |
3| 3 2 | 1 4 |
-+-----+-----|

You win!

Assumptions, Clarifications, and Restrictions

Like all good programmers, you should make as few assumptions as possible.

• Your submitted code must be hand-written MIPS assembly, which you yourself have written.
  You may not submit code in other languages.
  You may not submit compiled output.

• You may not copy a solution from an online source. e.g. GitHub.

• Your functions will be tested individually. They must exactly match the behaviour of the corresponding C function and they must follow the MIPS calling conventions described below.

• You may assume that the input provided to sudoku.s will be correctly formatted. For example, where a number is expected, the input will not be a letter.

• The C code defines constants using #define. Your MIPS translation should use the corresponding provided named constants in the places where a #define is used in the C code. You should not use a #define constant in your MIPS translation if it is not used in the corresponding part of the C code.

• There will be a correctness penalty for assignments that do not follow standard MIPS calling conventions including:

  • Function arguments are passed in registers $a0..$a3.

  • Function return values are passed in register $v0

  • Values in registers $s0..$s7 are preserved across function calls.
    If a function changes these registers, it must restore the original value before returning.

  • The only registers' values that can be relied upon across a function call are $s0..$s7, $gp, $sp, and $fp.
    All other registers must be assumed to be have an undefined value after a function call, except $v0 which has the function return value.

• If you need clarification on what you can and cannot use or do for this assignment, ask in the class forum.

• You are required to submit intermediate versions of your assignment. See below for details.

Change Log

Version 1.0
(2025-10-01 09:00:00)

• Initial release

Version 1.1
(2025-10-01 13:03:00)

• Update sudoku.simple.c to match sudoku.c

Version 1.2
(2025-10-01 08:55:00)

• Add overview video, minor typo in sudoku.s

Assessment

Testing

1521 autotest sudoku

1521 autotest sudoku main

1521 autotest sudoku S1

1521 autotest sudoku whole_prog

1521 autotest sudoku main_S0_0

Submission

When you are finished working on the assignment, you must submit your work by running give:

give cs1521 ass1_sudoku sudoku.s

You must run give before Week 5 Friday 18:00:00 to obtain the marks for this assignment. Note that this is an individual exercise, the work you submit with give must be entirely your own.

You can run give multiple times.
Only your last submission will be marked.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

You cannot obtain marks by emailing your code to tutors or lecturers.

You can check your latest submission on CSE servers with:

1521 classrun check ass1_sudoku

You can check the files you have submitted here.

Manual marking will be done by your tutor, who will mark for style and readability, as described in the Assessment section below. After your tutor has assessed your work, you can view your results here; The resulting mark will also be available via give's web interface.

Due Date

This assignment is due Week 5 Friday 18:00:00 (2025-10-17 18:00:00).

The UNSW standard late penalty for assessment is 5% per day for 5 days - this is implemented hourly for this assignment.

Your assignment mark will be reduced by 0.2% for each hour (or part thereof) late past the submission deadline.

For example, if an assignment worth 60% was submitted half an hour late, it would be awarded 59.8%, whereas if it was submitted past 10 hours late, it would be awarded 57.8%.

Beware - submissions 5 or more days late will receive zero marks. This again is the UNSW standard assessment policy.

Assessment Scheme

This assignment will contribute 15 marks to your final COMP1521 mark.

80% of the marks for assignment 1 will come from the performance of your code on a large series of tests.

20% of the marks for assignment 1 will come from hand marking. These marks will be awarded on the basis of clarity, commenting, elegance and style. In other words, you will be assessed on how easy it is for a human to read and understand your program.

An indicative assessment scheme for performance follows.
The lecturer may vary the assessment scheme after inspecting the assignment submissions, but it is likely to be broadly similar to the following:

An indicative assessment scheme for style follows.
The lecturer may vary the assessment scheme after inspecting the assignment submissions, but it is likely to be broadly similar to the following:

An indicative style rubric follows.
The lecturer may vary the assessment scheme after inspecting the assignment submissions, but it is likely to be broadly similar to the following:

• Formatting (8/20):
  • Whitespace
  • Indentation (consistent, tabs or spaces are okay)
  • Line length (below 180 characters unless very exceptional)
  • Line breaks (using vertical whitespace to improve readability)
• Documentation (12/20):
  • Header comment (with name, zID, description of program)
  • Function comments (above each function with a description)
  • Sensible commenting throughout the code
  • Descriptive label names, indicating structure

Note that the following penalties apply to your total mark for plagiarism:

Intermediate Versions of Work

You are required to submit intermediate versions of your assignment.

Every time you work on the assignment and make some progress you should copy your work to your CSE account and submit it using the give command above. It is fine if intermediate versions do not compile or otherwise fail submission tests. Only the final submitted version of your assignment will be marked.

Assignment Conditions

• Joint work is not permitted on this assignment.

  This is an individual assignment. The work you submit must be entirely your own work: submission of work even partly written by any other person is not permitted.

  Do not request help from anyone other than the teaching staff of COMP1521 — for example, in the course forum, or in help sessions.

  Do not post your assignment code to the course forum. The teaching staff can view code you have recently submitted with give, or recently autotested.

  Assignment submissions are routinely examined both automatically and manually for work written by others.

  Rationale: this assignment is designed to develop the individual skills needed to produce an entire working program. Using code written by, or taken from, other people will stop you learning these skills. Other CSE courses focus on skills needed for working in a team.

• The use of code-synthesis tools, such as GitHub Copilot, ChatGPT, Google Gemini, etc. are not permitted on this assignment.

  Rationale: this assignment is designed to develop your understanding of basic concepts. Using synthesis tools will stop you learning these fundamental concepts, which will significantly impact your ability to complete future courses.

• Sharing, publishing, or distributing your assignment work is not permitted.

  Do not provide or show your assignment work to any other person, other than the teaching staff of COMP1521. For example, do not message your work to friends.

  Do not publish your assignment code via the Internet. For example, do not place your assignment in a public GitHub repository.

  Rationale: by publishing or sharing your work, you are facilitating other students using your work. If other students find your assignment work and submit part or all of it as their own work, you may become involved in an academic integrity investigation.

• Sharing, publishing, or distributing your assignment work after the completion of COMP1521 is not permitted.

  For example, do not place your assignment in a public GitHub repository after this offering of COMP1521 is over.

  Rationale: COMP1521 may reuse assignment themes covering similar concepts and content. If students in future terms find your assignment work and submit part or all of it as their own work, you may become involved in an academic integrity investigation.

Violation of any of the above conditions may result in an academic integrity investigation, with possible penalties up to and including a mark of 0 in COMP1521, and exclusion from future studies at UNSW. For more information, read the UNSW Student Code, or contact the course account.