Question

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 by command line argument
   //Display the solution to the screen.
   //Create and run all the column threads with appropriate thread parameters to verify the columns of the solution.
   //Create and run all the row threads with appropriate thread parameters to verify the rows of the solution.
   //Create and run all the sub grid threads with appropriate thread parameters to verify the sub grids of the solution.
   //Wait for all thread to complete.
   //Check the results from all threads through status map.
   //Display whether the solution is valid or not.

   return 0;
}
  

checker.h

#ifndef __SUDOKU_CHECKER_HEADER__
#define __SUDOKU_CHECKER_HEADER__

#define PUZZLE_SIZE 9
#define NUMBER_OF_THREADS 27   
#define LINE_MAX_LENGTH 100  

/*
* Data structure to pass parameters to each worker thread
*/
typedef struct {
   int thread_no;
   int x;
   int y;
} parameters;

void read_from_file(char* sudoku_file){
// Read the solution of a sudoku puzzle line by line from a given FILE pointer
// Parse individual values (separated by comma) from each line and puts at appropriate position
// in an externally difened two dimensional array (global variable) which represents the solution in memory.
// Report error if reading fails

void show_puzzle();
// Show in memory content of the solution of a sudoku puzzle

void* row_worker(void* param);
// Check whether the row of the sudoku puzzle solution referred by the param contains all the digits from 1 to 9
// Set the appropriate status value in status map. The status map is an externally defined one-dimensional array
// (global variable).

void* col_worker(void* param);
// Check whether the column of the sudoku puzzle solution referred by the param contains all the digits from 1 to 9
// Set the appropriate status value in status map.

void* subgrid_worker(void* param);
// Check whether the subgrid of the sudoku puzzle solution referred by the param contains all the digits from 1 to 9
// Set the appropriate status value in status map.

int check_status_map();
//Loop through the status map, return 1 if all are set, return 0 otherwise.

#endif

Answer 1

Hi There, below is the resolution for asked sudoku program. Please let me know if it worked for you.

Program starts from here ::

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct
{
int row;
int col;
int (* board)[9];
} parameters;

void * walk_rows(void * params);

void * walk_cols(void * params);

void * check_square(void * params);

/***************
* ENTRY POINT
**************/
int main(void)
{

int board[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}
};
  
// ====== Create the parameter for the columns and rows check =======
parameters * param0 = (parameters *) malloc(sizeof(parameters));
param0->row = 0;
param0->col = 0;
param0->board = board;
  
// First 3x3
parameters * param1 = (parameters *) malloc(sizeof(parameters));
param1->row = 0;
param1->col = 0;
param1->board = board;
  
// Second 3x3
parameters * param2 = (parameters *) malloc(sizeof(parameters));
param2->row = 0;
param2->col = 3;
param2->board = board;
  
// Third 3x3
parameters * param3 = (parameters *) malloc(sizeof(parameters));
param3->row = 0;
param3->col = 6;
param3->board = board;
  
// Fourth 3x3
parameters * param4 = (parameters *) malloc(sizeof(parameters));
param4->row = 3;
param4->col = 0;
param4->board = board;
  
// Fifth 3x3
parameters * param5 = (parameters *) malloc(sizeof(parameters));
param5->row = 3;
param5->col = 3;
param5->board = board;
  
// Sixth 3x3
parameters * param6 = (parameters *) malloc(sizeof(parameters));
param6->row = 3;
param6->col = 6;
param6->board = board;
  
// Seventh 3x3
parameters * param7 = (parameters *) malloc(sizeof(parameters));
param7->row = 6;
param7->col = 0;
param7->board = board;
  
// Eighth 3x3
parameters * param8 = (parameters *) malloc(sizeof(parameters));
param8->row = 6;
param8->col = 3;
param8->board = board;
  
// Ninth 3x3
parameters * param9 = (parameters *) malloc(sizeof(parameters));
param9->row = 6;
param9->col = 6;
param9->board = board;
  
  
pthread_t thread_rows, thread_cols, thread1, thread2, thread3, thread4, thread5, thread6, thread7, thread8, thread9;
  

void * all_rows;
void * all_cols;
void * square1;
void * square2;
void * square3;
void * square4;
void * square5;
void * square6;
void * square7;
void * square8;
void * square9;
  
  
pthread_create(&thread_rows, NULL, walk_rows, (void *) param0);
pthread_create(&thread_cols, NULL, walk_cols, (void *) param0);
pthread_create(&thread1, NULL, check_square, (void *) param1);
pthread_create(&thread2, NULL, check_square, (void *) param2);
pthread_create(&thread3, NULL, check_square, (void *) param3);
pthread_create(&thread4, NULL, check_square, (void *) param4);
pthread_create(&thread5, NULL, check_square, (void *) param5);
pthread_create(&thread6, NULL, check_square, (void *) param6);
pthread_create(&thread7, NULL, check_square, (void *) param7);
pthread_create(&thread8, NULL, check_square, (void *) param8);
pthread_create(&thread9, NULL, check_square, (void *) param9);

  
pthread_join(thread_rows, &all_rows);
pthread_join(thread_cols, &all_cols);
pthread_join(thread1, &square1);
pthread_join(thread2, &square2);
pthread_join(thread3, &square3);
pthread_join(thread4, &square4);
pthread_join(thread5, &square5);
pthread_join(thread6, &square6);
pthread_join(thread7, &square7);
pthread_join(thread8, &square8);
pthread_join(thread9, &square9);
  
  
if ( (int) all_rows == 1 &&
(int) all_cols == 1 &&
(int) square1 == 1 &&
(int) square2 == 1 &&
(int) square3 == 1 &&
(int) square4 == 1 &&
(int) square5 == 1 &&
(int) square6 == 1 &&
(int) square7 == 1 &&
(int) square8 == 1 &&
(int) square9 == 1 ) {
printf("The Sudoku Puzzle is solved!\n");
}
else {
printf("The Sudoku Puzzle is NOT solved.\n");
}
  
return 0;
}

void * walk_rows(void * params) {
parameters * data = (parameters *) params;
int startRow = data->row;
int startCol = data->col;
for (int i = startRow; i < 9; ++i) {
int row[10] = {0};
for (int j = startCol; j < 9; ++j) {
int val = data->board[i][j];
if (row[val] != 0) {
return (void *) 0;
}
else{
row[val] = 1;
}
}
}
return (void *) 1;
}

void * walk_cols(void * params) {
parameters * data = (parameters *) params;
int startRow = data->row;
int startCol = data->col;
for (int i = startCol; i < 9; ++i) {
int col[10] = {0};
for (int j = startRow; j < 9; ++j) {
int val = data->board[j][i];
if (col[val] != 0) {
return (void *) 0;
}
else{
col[val] = 1;
}
}
}
return (void *) 1;
}

void * check_square(void * params) {
parameters * data = (parameters *) params;
int startRow = data->row;
int startCol = data->col;
int saved[10] = {0};
for (int i = startRow; i < startRow + 3; ++i) {
for (int j = startCol; j < startCol + 3; ++j) {
int val = data->board[i][j];
if (saved[val] != 0) {
return (void *) 0;
}
else{
saved[val] = 1;
}
}
}
return (void *) 1;
}

Program ends here ::::

Output ::

Output with hardcoded values as it is

output with editing in hardcoded value ::

Please provide your valuable feedback to improve if needed and motivate to do more like this questions to answer.