Question

In: Computer Science

PLEASE CAN YOU DO IN C LANGUAGE. A Sudoku puzzle uses a 9 × 9 grid...

PLEASE CAN YOU DO IN C LANGUAGE.

A Sudoku puzzle uses a 9 × 9 grid in which each column and row, as well as each of the nine 3 × 3subgrids, must contain all of the digits 1 ⋯ 9. Figure 4.26 presents an example of a valid Sudoku puzzle. This 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

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 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.

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; 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->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 or the CreateThread() (Windows) function, which in turn will pass it as a parameter to the function that is to run as a separate thread.

II. 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. Once a worker has performed this check, it must pass its results back to the parent. One good way to handle this is to create an 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 sets its corresponding value to 1, it is indicating that its region of the Sudoku puzzle is valid. A value of 0 indicates otherwise. When all worker threads have completed, the parent thread checks each entry in the result array to determine if the Sudoku puzzle is valid.

Solutions

Expert Solution

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.

Here's the code:

#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\n", 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\n", 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\n", 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!\n");

return EXIT_SUCCESS;

}

}

printf("Sudoku solution is valid!\n");

return EXIT_SUCCESS;

}


Related Solutions

designing a multithreaded application in C that determines whether the solution to a Sudoku puzzle is...
designing a multithreaded application in C that determines whether the solution to a Sudoku puzzle is valid A Sudoku puzzle uses a 9×9 grid in which each column and row, as well as each of the nine 3×3 subgrids, must contain all of the digits 1 to 9. main.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <pthread.h> int puzzle[PUZZLE_SIZE+1][PUZZLE_SIZE+1]; int status_map[NUMBER_OF_THREADS];    parameters* worker_params[NUMBER_OF_THREADS]; pthread_t workers[NUMBER_OF_THREADS]; int main(int argc, char** argv) {    //Read the sudoku solution from  the file specified...
• This lab, you will write a Java program to determine if a given Sudoku puzzle...
• This lab, you will write a Java program to determine if a given Sudoku puzzle is valid or not. • You determine if the puzzle is complete and valid, incomplete, or is invalid. • A puzzle is a 2-dimensional array 9x9 array. Each element contains the numbers 1 – 9. A space may also contain a 0 (zero), which means the spot is blank. • If you don’t know how a Sudoku Puzzle works, do some research, or download...
Write Prolog code which can solve any given 9x9 Sudoku puzzle. Test your implementation with at...
Write Prolog code which can solve any given 9x9 Sudoku puzzle. Test your implementation with at least 2 querries and show the results in README. Writing README carries 1 point.
on C++ language please and if you can also put note on it to better undertand...
on C++ language please and if you can also put note on it to better undertand it. Write a program that reads data from a data file, the value of which is provided at the end of the problem. Your program is to incorporate the following requirements: Data to the program is input from a file of an unspecified length; that is, the program does not know in advance how many numbers are in the file. Save the output of...
this is data structures with C++ language, please do "#1 & a" separately and please send...
this is data structures with C++ language, please do "#1 & a" separately and please send me copyable file 1. Write a program that allows the user to enter the last names of the candidates in a local election and the votes received by each candidate. The program should then output each candidate's name, votes received by that candidate, and the percentage of the total votes received by the candidate. Assume a user enters a candidate's name only once and...
Done in C language using mobaxterm if you can but use basic C This program is...
Done in C language using mobaxterm if you can but use basic C This program is broken up into three different functions of insert, delete, and main. This program implements a queue of individual characters in a circular list using only a single pointer to the circular list; separate pointers to the front and rear elements of the queue are not used. The linked list must be circular.      The insert and remove operations must both be O(1)    You...
Original C code please. Part 1: You can do A, B, and C in one program...
Original C code please. Part 1: You can do A, B, and C in one program with multiple loops (not nested) or each one in a small program, it doesn’t matter. A. Create a loop that will output all the positive multiples of 9 that are less than 99. 9 18 27 36 45        …. B. Create a loop that will output all the positive numbers less than 200 that are evenly divisible by both 2 and 7. 14        28       ...
Can you please do this in C asap. Promise to leave a awesome rating! Thank you...
Can you please do this in C asap. Promise to leave a awesome rating! Thank you in advance. Question and template below Instructions- LINKED LIST In C 'objects' => structs (struct - collection of data, not methods) Linked List Collection of objects which are all connected to each other Each Object 'points' to the next item in the list Node (struct) ' O ' - data - nextNode Our linked list will store data(structs containing integers) in order from smallest...
IN C++ LANGUAGE PLEASE:::: Is there a Prius version? Did you know that the average Boeing...
IN C++ LANGUAGE PLEASE:::: Is there a Prius version? Did you know that the average Boeing 747 airplane uses approximately 1 gallon of fuel per second?  Given the speed of the airplane, that means it gets 5 gallons to the mile. No, not 5 miles to the gallon, 5 gallons to the mile.   You may be questioning why such a horribly inefficient machine is allowed to exist, but you’ll be happy to find out that, because this airplane hold 568 people, it...
Please use C language and use link list to do this program. This program should ask...
Please use C language and use link list to do this program. This program should ask user to enter two fraction polynomials. Then user chocie if he want add it or multiple it. I need you please to test it to see if it work with these two fraction polynomials 1-  Left Poly Pointer: 1/1x2 + 3/4x + 5/12 2-Right Poly Pointer: 1/1x4 – 3/7x2 + 4/9x + 2/11 AND AFTER ADDING 3- Resulting Poly Pointer: 1/1x4 + 4/7x2 + 43/36x...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT