A sudoku puzzle uses a 9x9 grid in which each columns and row, as well as each of the nine 3x3 sub-grids must contain all of the digits 1. You are required to write the program in C. This project consists of designing a multithreaded application that determines whether the solution to a Sudoku puzzle is valid or not. A thread to check one row of the gird contains the digits 1 through 9, i.e., nine separate threads to check all rows.
With the above strategy there are 27 worker threads (plus a main thread) to check whether a given Sudoku grid is valid or not.
Your program should ask the user to enter 81 digits from the console (in row-major order, i.e., first the numbers in the first row are entered, then the numbers in the second row, etc.), and the main thread of your program should create the worker threads, passing each worker thread the locations within the grid that it must check. Note that the specific cells to be checked by column validators, row validators, and sub-grid validators are different from each other. You should design your worker threads according to their duties, ensure correct measures on how to obtain the location information from the main thread. In any case this will require passing several parameters to each thread. The simplest approach is to create a data structure using a struct construct of C. For example, a structure to pass the row and column where a thread must begin its validation would appear as follows:
/* structure for passing data to threads */
Both Pthreads and Windows programs can create worker threads using a strategy similar to that shown below:
parameters *data = (parameters *) malloc(sizeof(parameters));
data->row = 1;
data->column = 1;
/* Now create the thread passing it data as parameter */
The data pointer will be passed to either the pthread_create() (Pthreads) function or the CreateThread() (Windows) function, which in turn will pass it as a parameter to the function to run as a separate thread.
Each worker thread is assigned the task of determining the validity of a particular region of the Sudoku puzzle. Once a worker thread has performed this check, it must pass its results back to the parent. One way to handle this is to create a global array of integer values that is visible to each thread. The ith index in this array corresponds to the ith worker thread. If a worker thread sets its corresponding value to 1, it is indicating that its region of the Sudoku puzzle is valid. A value of 0 would indicate otherwise. When all worker threads have completed, the main thread can check each entry in the result array to determine if the Sudoku puzzle is valid or not. After printing the
result to the console, the program should exit.
It is apparent from the above discussion that the main thread should wait for all threads to finish their duties before reaching a final decision. This means that the main thread should wait for all the worker threads to exit, and then makes its final decision. You can implement this with the pthread_join function of the Pthreads library (Linux, MAC OS) or via the WaitForMultipleObjects (Windows) function from the Win32 API, as we have seen during our lectures. Alternatively, you can achieve this step via another global integer variable, say threads_completed, initially set to zero, and incremented by every thread when that thread finishes its job, and before it exits. When the value of this variable reaches 27, it means that every thread finished its job, and the main thread can finalize its decision, output the result, and exit.
Note that you will need to ensure proper synchronization mechanisms between the threads so that this approach works correctly. You will be using either Pthreads mutex or Windows Mutex objects depending on your development environment.