Links: [Course Home] [Schedule] [Learning Objectives] [Resources] [Moodle]
Due Wednesday, May 11 April 12 at 10:00 AM. There is an automatic grace period of 24 hours associated with this deadline. This is the
only consideration that will be given for minor emergencies.
You may work in groups of up to three students. Please have just one group member submit the assignment (see instructions below).
As a reminder, the course collaboration policy will be strictly enforced on this assignment.
For this project, you will write a multi-threaded application that reads 81 integers (i.e. a 9x9 matrix) from a text file and verifies whether or not the input is a valid Sudoku solution. Here is an example of a valid Sudoku:
You should write a C program that uses pthreads to verify whether or not the input is a valid Sudoku. Use this algorithm:
read and store the input in a 2D array
for each row:
create a thread for this row to determine if it contains digits 1 through 9
for each column:
create a thread for this column to determine if it contains digits 1 through 9
for each 3x3 subgrid:
create a thread for this grid to determine if it contains digits 1 through 9
wait on each of the threads:
if the thread found any missing digit, print a specific error message (see below).
if no thread encountered a missing value, print the message "The input is a valid Sudoku."
You will NOT be allowed to use global variables to communicate between threads. I strongly recommend that you define a struct to contain all the information you'll need to pass between the master thread and its children. For example, the master will need to send the children the matrix as well as the ID of the row, column, or subgrid the child thread is supposed to check. The child will need to send the parent a boolean value indicating whether or not it found a problem. You should package all of this information into a single struct, and you should pass each thread a reference to an instance of this struct.
The following is a sample input. The spaces are used to make the input easier to read. Your program should only assume that the integers are separated by whitespace.
7 2 6 3 5 9 4 1 8 4 5 8 1 6 7 2 3 9 9 1 3 8 2 4 7 6 5 1 6 2 9 7 5 3 8 4 3 9 4 2 8 6 1 5 7 8 7 5 4 1 3 9 2 6 5 3 7 6 4 1 8 9 2 6 8 9 7 3 2 5 4 1 2 4 1 5 9 8 6 7 3For the above input, your program should print the following line:
The input is a valid Sudoku.
For the following input, which is not a valid Sudoku (see the digit in red):
7 2 6 3 5 9 4 1 8
4 5 8 1 6 7 2 3 9
9 1 3 8 2 4 7 6 5
1 6 1 9 7 5 3 8 4
3 9 4 2 8 6 1 5 7
8 7 5 4 1 3 9 2 6
5 3 7 6 4 1 8 9 2
6 8 9 7 3 2 5 4 1
2 4 1 5 9 8 6 7 3
your program should print
Row 4 doesn't have the required values. Column 3 doesn't have the required values. The left middle subgrid doesn't have the required values. The input is not a valid Sudoku.
To get any points at all for the items below, your program must be a C program using pthreads to follow the algorithm in the "Project Description" section. Specifically, it must spawn a thread to check each row, column, and 3x3 grid. The master thread should use the results of each thread to print the final output. It should not validate any part of the grid itself. Finally, your threads should not use global variables to communicate.
| Accurately identifies a valid Sudoku | 15 points |
| Invalid Sudoku: accurately identifies row | 20 points |
| Invalid Sudoku: accurately identifies column | 20 points |
| Invalid Sudoku: accurately identifies subgrid | 20 points |
| Destroys all threads and deletes all dynamically allocated memory | 5 points |
| Design and style (see below) | 20 points |
| Total for assignment | 100 points |
|---|
Design and style will be assessed on the following criteria:
You should turn in one file, called sudoku.c. I should be able to compile and run your program on blue using the following commands:
gcc sudoku.c -o sudoku.x -lpthread ./sudoku.x < someInputFile
Submit your C file on Moodle. Please make only one submission per group.