Design a multithreaded Sudoku Solution Checker program that accepts a Sudoku sol
ID: 3909506 • Letter: D
Question
Design a multithreaded Sudoku Solution Checker program that accepts a Sudoku solution from the user as input, and determines whether the solution is valid or invalid.
The program accepts a Sudoku solution from a file.
Make threads that:
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 × 3 subgrids contains the digits 1through 9
Can someone explain to me the best way to appraoch this? We are writing the assignment in C. I am wondering if I should convert the file to a 2d array first then send data to the threads? I am confused on how the data is being transferred in the above example?
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; l parameters; Both Pthreads and Windows programs will create worker threads using a strategy similar to that shown below parameters *data = (parameters *) malloc (sizeof (parameters)); data->row-1; data->column1; /* Now create the thread passing it data as a parameter */ The data pointer will be passed to either the pthread create0 (Pthreads) function or the CreateThread0 (Windows) function, which in turn will pass it as a parameter to the function that is to run as a separate threadExplanation / Answer
Hello Sir/Madam
Hey consider this program where i implemented following ur conditions
This program defines a sudoku puzzle solution and then determines whether
the puzzle solution is valid using 27 threads. 9 for each 3x3 subsection, 9
for the 9 columns, and 9 for the 9 rows. Each thread updates their index in
a global array to 1 indicating that the corresponding region in the puzzle
they were responsible for is valid. The program then waits for all threads
to complete their execution and checks if all entries in the valid array have
been set to 1. If yes, the solution is valid. If not, solution is invalid.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#define num_threads 27
/*
Initialize the array which worker threads can update to 1 if the
corresponding region of the sudoku puzzle they were responsible
for is valid.
*/
int valid[num_threads] = {0};
// Struct that stores the data to be passed to threads
typedef struct {
int row;
int column;
} parameters;
// Sudoku puzzle to be solved
int sudoku[9][9] = {
{6, 2, 4, 5, 3, 9, 1, 8, 7},
{5, 1, 9, 7, 2, 8, 6, 3, 4},
{8, 3, 7, 6, 1, 4, 2, 9, 5},
{1, 4, 3, 8, 6, 5, 7, 2, 9},
{9, 5, 8, 2, 4, 7, 3, 6, 1},
{7, 6, 2, 3, 9, 1, 4, 5, 8},
{3, 7, 1, 9, 5, 6, 8, 4, 2},
{4, 9, 6, 1, 8, 2, 5, 7, 3},
{2, 8, 5, 4, 7, 3, 9, 1, 6}
};
// Method that determines if numbers 1-9 only appear once in a column
void *isColumnValid(void* param) {
// Confirm that parameters indicate a valid col subsection
parameters *params = (parameters*) param;
int row = params->row;
int col = params->column;
if (row != 0 || col > 8) {
fprintf(stderr, "Invalid row or column for col subsection! row=%d, col=%d ", row, col);
pthread_exit(NULL);
}
// Check if numbers 1-9 only appear once in the column
int validityArray[9] = {0};
int i;
for (i = 0; i < 9; i++) {
int num = sudoku[i][col];
if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
pthread_exit(NULL);
} else {
validityArray[num - 1] = 1;
}
}
// If reached this point, col subsection is valid.
valid[18 + col] = 1;
pthread_exit(NULL);
}
// Method that determines if numbers 1-9 only appear once in a row
void *isRowValid(void* param) {
// Confirm that parameters indicate a valid row subsection
parameters *params = (parameters*) param;
int row = params->row;
int col = params->column;
if (col != 0 || row > 8) {
fprintf(stderr, "Invalid row or column for row subsection! row=%d, col=%d ", row, col);
pthread_exit(NULL);
}
// Check if numbers 1-9 only appear once in the row
int validityArray[9] = {0};
int i;
for (i = 0; i < 9; i++) {
// If the corresponding index for the number is set to 1, and the number is encountered again,
// the valid array will not be updated and the thread will exit.
int num = sudoku[row][i];
if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
pthread_exit(NULL);
} else {
validityArray[num - 1] = 1;
}
}
// If reached this point, row subsection is valid.
valid[9 + row] = 1;
pthread_exit(NULL);
}
// Method that determines if numbers 1-9 only appear once in a 3x3 subsection
void *is3x3Valid(void* param) {
// Confirm that parameters indicate a valid 3x3 subsection
parameters *params = (parameters*) param;
int row = params->row;
int col = params->column;
if (row > 6 || row % 3 != 0 || col > 6 || col % 3 != 0) {
fprintf(stderr, "Invalid row or column for subsection! row=%d, col=%d ", row, col);
pthread_exit(NULL);
}
int validityArray[9] = {0};
int i, j;
for (i = row; i < row + 3; i++) {
for (j = col; j < col + 3; j++) {
int num = sudoku[i][j];
if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
pthread_exit(NULL);
} else {
validityArray[num - 1] = 1;
}
}
}
// If reached this point, 3x3 subsection is valid.
valid[row + col/3] = 1; // Maps the subsection to an index in the first 8 indices of the valid array
pthread_exit(NULL);
}
int main() {
pthread_t threads[num_threads];
int threadIndex = 0;
int i,j;
// Create 9 threads for 9 3x3 subsections, 9 threads for 9 columns and 9 threads for 9 rows.
// This will end up with a total of 27 threads.
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if (i%3 == 0 && j%3 == 0) {
parameters *data = (parameters *) malloc(sizeof(parameters));
data->row = i;
data->column = j;
pthread_create(&threads[threadIndex++], NULL, is3x3Valid, data); // 3x3 subsection threads
}
if (i == 0) {
parameters *columnData = (parameters *) malloc(sizeof(parameters));
columnData->row = i;
columnData->column = j;
pthread_create(&threads[threadIndex++], NULL, isColumnValid, columnData); // column threads
}
if (j == 0) {
parameters *rowData = (parameters *) malloc(sizeof(parameters));
rowData->row = i;
rowData->column = j;
pthread_create(&threads[threadIndex++], NULL, isRowValid, rowData); // row threads
}
}
}
for (i = 0; i < num_threads; i++) {
pthread_join(threads[i], NULL); // Wait for all threads to finish
}
// If any of the entries in the valid array are 0, then the sudoku solution is invalid
for (i = 0; i < num_threads; i++) {
if (valid[i] == 0) {
printf("Sudoku solution is invalid! ");
return EXIT_SUCCESS;
}
}
printf("Sudoku solution is valid! ");
return EXIT_SUCCESS;
}
Hope It works and looking forward to help if have any doubts..
Thank You Sir/Madam
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.