Sukoku Solver
CSEE 3827: Fundamentals of Computer Systems Take Home Programming Test
Prof. Martha Kim
• All work is to be individual, with no collaboration of any sort permitted.
• Youmayrefertoallofthissemester’scoursematerials(i.e.,slides,notes,problemsetsandsolutions,
discussion board history).
• You may also refer to external resources (e.g., slides from other courses or semesters, the Harris and Harris textbook, etc.). Such materials should serve as references and their content should never be presented as your own.
• You may not solicit or consult solutions written by another human.
• AI-based coding assistants such as ChatGPT or Github Copilot are prohibited.
• AcademicintegrityviolationswillbereporteddirectlytotheOfficeofStudentConduct,andstudents found responsible are subject to academic penalties.
• You may pose questions to course staff via private post on ED. As on an in-person test, staff will answer clarifying questions about the prompt, but will not provide assistance writing or debugging code.
• Your code will be tested for both correctness and adherence to calling conventions.
• when possible, partial credit will be given.
• The submission deadline is Tuesday November 21 at 11:59pm. Be sure to leave sufficient time to upload before that deadline, as late submissions will not be accepted.
• To submit, upload a single file named sudoku.s to gradescope.
For this assignment you will implement parts of a Sudoku puzzle solver.
1 Background on Sudoku
Sudoku is a number puzzle played on a 9×9 grid. In a correctly solved puzzle, the digits 1 through 9 appear exactly once in each row, column, and 3×3 box in the grid. Each puzzle starts with some of the cells completed, and the remainder blank. The objective is to find the unique configuration of digits that fills the grid and satisfies the row, column, and box constraints. For a more detailed explanation, see the Wikipedia page on Sudoku: https://en.wikipedia.org/wiki/Sudoku.
2 Solving Tactics
There are a number of Sudoko solving tactics that a solver might employ. The solver for this assignment implements only the most simple tactic: once a cell is solved (i.e., its digit is known) that digit can be ruled out of the row, column, and box containing the cell. The solver will apply this tactic to all solved cells in the board until all 81 cells in the board are solved.
3 Sudoku Cell Representation
We represent each cell as a null-terminated ASCII string in memory. The string is nine characters long, followed by the null character terminal, so each cell occupies ten bytes in all. The contents of this string list, in ascending order, the possible correct digits for that cell. So, a cell where any digit is possible is represented as:
When a digit is ruled out as a possible answer for a cell, the corresponding entry in the cell string is replaced with a period. So, if we were to rule out 3 as a possible answer to the cell above, the updated cell string would be:
A cell is solved when all but one digit have been ruled out. For example, a cell that is determined to be 5 would be represented as:
4 Sudoku Board Representation
The 81 cells of the Sudoku board are arrayed in memory, one after the other. They are ordered in row-major order, meaning that all of the cells from the first row come first, followed by the cells in the second row, then the third, and so on until the 9th row. Within a row, cells are ordered from left to right. With each cell occupying 10 bytes, the whole board occupies 810 bytes of memory.
5 Functions to Implement
There are four functions to be implemented. Each of these four functions is delineated in the scaffolding by a separator line that begins
#### Do not move this separator.
Do not remove any of these separator lines from your submission. When implementing a function, make sure that all of your code for that function appears between the separators for that function. If you call one of the provided helper functions, you do not need to relocate those functions to between the separators.
num candidates
Given a pointer to a cell, this function should return an integer between 0 and 9 (inclusive) indicating how many candidate digits remain for the given cell. The function should leave the string that represents the cell unmodified.
rule out of cell
This function takes two arguments:
• a pointer to a cell
• an integer indicating the digit to be ruled out of the cell; guaranteed to be a valid Sudoku digit, i.e., 1-9 inclusive
The function should update the cell string to eliminate the given digit as a candidate. If the given digit has already been ruled out, the cell string should not change.
count solved cells
Given a pointer to a Sudoku board, this function should return an integer indicating how many of the cells in the board have been solved. The state of the board should be unmodified.
solve board
Given a pointer to a Sudoku board, this function should solve the puzzle, iteratively applying a single solving tactic: for each solved cell, rule its digit out of the corresponding row, column and box. Apply this tactic until all cells in the board are solved.
Note that there are helper functions in the scaffolding. They are described in more detail in the following section, but rule out of row, rule out of col, rule out of box will be particularly useful for solve board.
solve board should solve and modify the original board in place, so that when the function is complete, the solved board is found at the same address as the original board.
Programming Help
6 Helper Functions
In the scaffolding you will find a number of helper functions. You do not need to use all of them, but we describe all of them here for your convenience:
• • • • • • • •
print int: given an int, prints it to the screen
print string: given a pointer to a null-terminated ASCII string, prints the string to the screen
print newline: prints a newline to the screen
print space: prints a space to the screen
print hsep: prints a horizontal line of dashes to the screen
print vsep: prints a vertical pipe character to the screen
print board: given a pointer to a board in memory, prints it to the screen
first candidate: given a pointer to a cell, returns the value of the first possible digit; if there are no possible digits in the cell, returns 0
get row base: given a pointer to a board and a pointer to a cell in that board, returns a pointer to the base of the row in the board that contains the given cell
get col base: given a pointer to a board and a pointer to a cell in that board, returns a pointer to the base of the column in the board that contains the given cell
get box base: given a pointer to a board and a pointer to a cell in that board, returns a pointer to the base of the 3×3 box in the board that contains the given cell
This function will work once num candidates is working:
– is cell solved: given a pointer to a cell, returns 1 if cell is solved, 0 otherwise
These three functions will work only once count solved cells and rule out of cell are working:
– rule out of row: given a pointer to a board and a pointer to a solved cell in that board, rules the digit in the solved cell out of the row containing the solved cell
– rule out of col: given a pointer to a board and a pointer to a solved cell in that board, rules the digit in the solved cell out of the column containing the solved cell
– rule out of box: given a pointer to a board and a pointer to a solved cell in that board, rules the digit in the solved cell out of the box containing the solved cell
Testing and Advice
AsinPS4andPS5,theprovidedmainfunctionmakestestcallstothefunctionstobeimplemented. The expected output for each of these calls is specified in a comment in the body of main. If you are having trouble isolating an error, it helps to comment out or excise all but the one test invocation you are trying to debug.
Code Help
• Additional helper functions beyond what is provided in the scaffolding are not advised; if you do write them, they should adhere to conventions and appear in between the same separators as the function that uses them.
• It is recommended that you implement solve board only after the first three functions are working.
Programming Help, Add QQ: 749389476