Threaded Sudoku Solution Verifier

A Sudoku puzzle uses a 9 x 9 grid in which each column and row, as well as each of the nine 3 x 3 subgrids, must contain all of the digits 1 ... 9. The figure below presents an example of a valid Sudoku puzzle.

This project consists of designing a multithreaded application that verifies a Sudoku puzzle of any size is valid AND whether a Sudoku puzzle that has 0s instead of numbers can be completed to be a valid puzzle. Completing the puzzle only needs to work on 'easy' puzzles.

Important: The starter code defines a 2D array called grid where row-0 and column-0 is ignored. This makes it easier think about the puzzle. For the puzzle below

• grid[1][1] = 6
• grid[1][9] = 7
• grid[9][1] = 2
• grid[9][9] = 6

Figure: see image.

There are several different ways of multithreading this application. One suggested strategy is to create threads that check the following criteria:

• A thread to check that each column contains the digits 1 through 9
• A thread to check that each row contains the digits 1 through 9
• Nine threads to check that each of the 3 x 3 subgrids contains the digits 1 through 9

This would result in a total of eleven separate threads for validating a Sudoku puzzle. However, you are welcome to create even more threads for this project. For example, rather than creating one thread that checks all nine columns, you could create nine separate threads and have each of them check one column.

The purpose of this exercise is to give you experience identifying data and task parallelism rather than performance tuning. Your threaded Sudoku solver will likely be slower than validating a solution serially, but that's okay.

Passing Parameters to Each Thread

The parent thread will create the worker threads, passing each worker the location that it must check in the Sudoku grid. This step will require passing several parameters to each thread. The easiest approach is to create a data structure using a struct. For example, a structure to pass the row and column where a thread must begin validating would appear as follows:

/* structure for passing data to threads */
typedef struct {
int row;
int column;
} parameters;

You may use either pthreads of std::thread in the C++ include. The latter is likely easier.

Passing data to the thread with pthreads:

parameters *data = (parameters *) malloc(sizeof(parameters));
data->row = 1;
data->column = 1;
/* Now create the thread passing it data as a parameter */

The data pointer will be passed to either the pthread create() (Pthreads) function, which in turn will pass it as a parameter to the function that is to run as a separate thread.

You need to eventually either join or detach each thread with pthread_join or pthread_detach. This will reclaim the resources the thread consumes (e.g. kernel thread entry, stack, etc); failing to do this will leak resources and is bad form. See `man 3 pthread_join` and `man 3 pthread_detach` for more information.

Passing data to the thread with std::thread:

parameters data;
data.row = 1;data.column = 1;
std::thread thread = std::thread([=](parameters threadData) {
// do stuff, threadData contains the contents of data.}, data);// ...
// If a thread destructs and you didn't first join or detach it, your program will
// terminate. This forces you to cleanly reclaim resources.thread.join();

Your program will also need to use a struct, but it is up to you what is inside the struct.

Returning Results to the Parent Thread

Each worker thread is assigned the task of determining the validity of a particular region of the Sudoku puzzle or possibly finding if there is a single 0 in the region which could be converted to a number. Once a worker has performed this check, it must pass its results back to the parent.

There are multiple ways to achieve this. The parameter that is passed into the thread could have a result component where all the different threads can access. The ith index in this result array could correspond to the ith worker thread. The worked can use different numbers to indicate its status, say 1 for valid, 0 for invalid, 2 for incomplete, etc.

When all worker threads have completed, the parent thread checks each entry in the result array to determine if the Sudoku puzzle is valid.

Extension

Your program should be able to handle not just 9x9 Sudoku puzzles, but any size Sudoku puzzle. See the starter code on how to take an argument from the command line, indicating the filename for the puzzle, and how to read puzzle.

The format of the puzzle is as follows. A number indicating the Size x Size of the Sudoku puzzle followed by Size x Size of integers.

4
3 4 2 1
2 1 3 4
1 3 4 2
4 2 1 3

The valid numbers for a Sudoku puzzle are 1 to Size. This has the implication that each puzzle contains sqrt(N) subgrids each of size sqrt(N)xsqrt(N). If N does not have an integral square root (e.g. 2, 3, 5, 6, 7, 8, 10, 11, ...), then your program should print an error.

If the puzzle has a zero, that indicate that the puzzle is not yet complete and your program should try to fill it with the correct number.

For example, for the puzzle below.

3 4 2 1
2 1 0 0
1 3 0 2
4 2 1 3

The location grid[3][2] can be filled with "4" since row-3 already has 1, 2, 3 but not 4. Once that is filled, grid[2][3] can be filled with "3" since column-3 has 2, 4, and 1 but not 3. Your Sudoku solver should be able to fill cases of 1-missing-number, but does not need to be any more clever than that.

What to Submit

• Write a multi-threaded program using the starter code that use pthreads or std::thread that
  • Verifies if a given Sudoku puzzle is valid
• If the puzzle is complete, your program should print:
  • "Complete puzzle? true"
• Only for complete puzzles, or puzzles that your program was able to complete, print
  • "Valid puzzle? true"
• Substitute "false" for the above statements is puzzle is not complete or not valid.
• You can, but do not have to use the starter code, but your program must be runnable from command line as follows

./sudoku some-puzzle-file.txt