C++ Multithread -- Sudoku Validator Project 1-Sudoku Solution Validator A Sudoku
ID: 3712689 • Letter: C
Question
C++ Multithread -- Sudoku Validator
Project 1-Sudoku Solution Validator 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. Figure 4.19 presents an example of a valid Sudoku puzzle. This project consists of designing a multithreaded application that determines whether the solution to a Sudoku puzzle is valid 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 × 3 subgrids contains the digits 1 through 9 rate 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 This would result in a total of eleven 6 2 45 3 91 87 5 1 972 86 34 8 37 6 1 4 29 5 1 4 3 8 6 5 7 2 9 9 58 2 4 7 3 6 1 7 62 3 9 1 4 5 8 3 7 1 9 5 68 42 4 9 68 2 5 7 3 2 85 4 7 3 9 1 6 Figure 4.19 Solution to a 9 x 9 Sudoku puzzle columns, you could create nine sepa one column. rate threads and have each of them checkExplanation / Answer
Answer :
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#define num_threads 27
int valid[num_threads] = {0};
typedef struct {
int row;
int column;
} parameters;
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}
};
void *isColumnValid(void* param) {
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);
}
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;
}
}
valid[18 + col] = 1;
pthread_exit(NULL);
}
void *isRowValid(void* param) {
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);
}
int validityArray[9] = {0};
int i;
for (i = 0; i < 9; i++) {
int num = sudoku[row][i];
if (num < 1 || num > 9 || validityArray[num - 1] == 1) {
pthread_exit(NULL);
} else {
validityArray[num - 1] = 1;
}
}
valid[9 + row] = 1;
pthread_exit(NULL);
}
void *is3x3Valid(void* param) {
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;
}
}
}
valid[row + col/3] = 1;
pthread_exit(NULL);
}
int main() {
pthread_t threads[num_threads];
int threadIndex = 0;
int i,j;
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);
}
if (i == 0) {
parameters *columnData = (parameters *) malloc(sizeof(parameters));
columnData->row = i;
columnData->column = j;
pthread_create(&threads[threadIndex++], NULL, isColumnValid, columnData);
}
if (j == 0) {
parameters *rowData = (parameters *) malloc(sizeof(parameters));
rowData->row = i;
rowData->column = j;
pthread_create(&threads[threadIndex++], NULL, isRowValid, rowData);
}
}
}
for (i = 0; i < num_threads; i++) {
pthread_join(threads[i], NULL);
}
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.