I have written a code to verify if a sudoku puzzle is valid or not by using thre
ID: 3711705 • Letter: I
Question
I have written a code to verify if a sudoku puzzle is valid or not by using threads. It should be 9 threads for each row, 9 for each column, and 9 for each subsection of the puzzle. There must be 27 threads in total. The user is to input the filename in the command prompt when the program runs. However, I have coded the program for pthreads that only run on a POSIX system. I am needing this code modified for Windows. Also if there is a way to make the code more efficient (such as me hard coding the threads to check each of the 9 rows and 9 columns as well as the 9 subsections) please show how to do this. Code is below.
#include <stdio.h>
#include<windows.h> //originally input as <pthreads.h>, not compatible with windows os
#include<stdlib.h>
#include <string.h>
#define THREAD_NUMBER 27
#define PUZZLE_DIMENSIONS 9
//global
char * fileName;
//int sudokuPuzzle [PUZZLE_DIMENSIONS][PUZZLE_DIMENSIONS] = {0}; //2d array for storing sudoku puzzle
int threadResult[THREAD_NUMBER] = {0}; // stores results of each thread
//struct holding thread data required
typedef struct
{
int row;
int column;
//int idThread;
}parameters;
void fileRead();
void displayPuzzle();
parameters * threadParameters(int row, int column, int id);
void * checkColumns( void * param);
void * checkRows( void * param);
void * checkSubSection(void * param);
void checkNumrefresh (int *array, int size);
int main (int argc, char * argv[])
{
int b;
int threadsuccess = 0;
pthread_t threads[THREAD_NUMBER];
fileName = argv[1];
fileRead();
displayPuzzle();
//starting threads
//pthread_t threads[THREAD_NUMBER];
//check columns
pthread_create(&threads[0], NULL, checkColumns, threadParameters(0,0,0));
pthread_create(&threads[1], NULL, checkColumns, threadParameters(0,1,1));
pthread_create(&threads[2], NULL, checkColumns, threadParameters(0,2,2));
pthread_create(&threads[3], NULL, checkColumns, threadParameters(0,3,3));
pthread_create(&threads[4], NULL, checkColumns, threadParameters(0,4,4));
pthread_create(&threads[5], NULL, checkColumns, threadParameters(0,5,5));
pthread_create(&threads[6], NULL, checkColumns, threadParameters(0,6,6));
pthread_create(&threads[7], NULL, checkColumns, threadParameters(0,7,7));
pthread_create(&threads[8], NULL, checkColumns, threadParameters(0,8,8));
//check rows
pthread_create(&threads[9], NULL, checkRows, threadParameters(0,0,9));
pthread_create(&threads[10], NULL, checkRows, threadParameters(1,0,10));
pthread_create(&threads[11], NULL, checkRows, threadParameters(2,0,11));
pthread_create(&threads[12], NULL, checkRows, threadParameters(3,0,12));
pthread_create(&threads[13], NULL, checkRows, threadParameters(4,0,13));
pthread_create(&threads[14], NULL, checkRows, threadParameters(5,0,14));
pthread_create(&threads[15], NULL, checkRows, threadParameters(6,0,15));
pthread_create(&threads[16], NULL, checkRows, threadParameters(7,0,16));
pthread_create(&threads[17], NULL, checkRows, threadParameters(8,0,17));
//check subsection
pthread_create(&threads[18], NULL, checkSubSection, threadParameters(0,0,18));
pthread_create(&threads[19], NULL, checkSubSection, threadParameters(0,3,19));
pthread_create(&threads[20], NULL, checkSubSection, threadParameters(0,6,20));
pthread_create(&threads[21], NULL, checkSubSection, threadParameters(3,0,21));
pthread_create(&threads[22], NULL, checkSubSection, threadParameters(3,3,22));
pthread_create(&threads[23], NULL, checkSubSection, threadParameters(3,6,23));
pthread_create(&threads[24], NULL, checkSubSection, threadParameters(6,0,24));
pthread_create(&threads[25], NULL, checkSubSection, threadParameters(6,3,25));
pthread_create(&threads[26], NULL, checkSubSection, threadParameters(6,6,26));
//waiting for threads to be done
for(b=0; b < THREAD_NUMBER; b++)
{
pthread_join(threads[b], NULL);
}
//check results for all threads to make sure their puzzle area is valid
for(b=0; b< THREAD_NUMBER; b++)
{
if(threadResult[b]==1)
{
threadsuccess++;
}
}
//Results
if(threadsuccess == THREAD_NUMBER)
printf("Yes, the puzzle you input is valid. ");
else
printf("No, the puzzle you input is not valid. ");
}
void fileRead()
{
int i, j;
FILE * file = fopen(fileName, "r");
//error if the file failed to open
if(file==NULL)
{
fprintf(stderr, "File failed to open. Check file location and/or your file name. ");
exit(1);
}
//store values into the 2d array
for(i=0; i<PUZZLE_DIMENSIONS; i++)
{
for(j=0; j<PUZZLE_DIMENSIONS; i++)
{
fscanf(file, "%d", &sudokuPuzzle[i][j]);
if (sudokuPuzzle[i][j] > 9 || sudokuPuzzle[i][j]<9)
{
fprintf(stderr, "This file doesn't contain valid sudoku formatting. ");
exit(1);
}
}
}
fclose(file);
}
void displayPuzzle()
{
int i, j;
for (i=0; i<PUZZLE_DIMENSIONS; i++)
{
for (j=0;j<PUZZLE_DIMENSIONS; j++)
{
printf("%d", sudokuPuzzle[i][j]);
}
printf(" ");
}
}
//creates data pointer for worker threads
parameters * threadParameters(int row, int column, int id)
{
parameters *data = (parameters *) malloc(sizeof(parameters));
//assigning the rows, colums and ids to worker threads
data->row = row;
data->column = column;
data->idThread = id;
//returns data pointer
return data;
}
//checking the columns of the sudoku puzzle
void * checkColumns(void * param)
{
//array for the threads to insure numbers 1-9 are present
int checkNumbers[PUZZLE_DIMENSIONS] = {0};
parameters * columnData = (parameters *) param;
int i, j, k, value;
int validColumnNumber = 0;
//looping the columns
for(i = columnData->column; i < PUZZLE_DIMENSIONS; i++)
{
int num = 0;
//refresh the temp array
checkNumrefresh(checkNumbers, PUZZLE_DIMENSIONS);
//looping the rows
for(j = columnData->row; j< PUZZLE_DIMENSIONS; j++)
{
value = sudokuPuzzle[j][i];
if(value >=1 || value<=9)
{
checkNumbers[value-1]++;
}
}
//check column with all values between 1-9
for(k=0; k<PUZZLE_DIMENSIONS; k++)
{
if(checkNumbers[k] == 1)
{
num++;
}
}
//incremeting number of valid columns if column is valid
if(num == PUZZLE_DIMENSIONS)
{
validColumnNumber++;
}
}
//if all columns contain 1-9, the thread's status is updated
if(validColumnNumber == PUZZLE_DIMENSIONS)
{
threadResult[columnData->idThread] = 1;
}
}
void * checkRows(void * param)
{
//array for the threads to insure numbers 1-9 are present
int checkNumbers[PUZZLE_DIMENSIONS] = {0};
parameters * rowData = (parameters *) param;
int i, j, k, value;
int validRowNumber = 0;
//looping the rows
for(i = rowData->column; i < PUZZLE_DIMENSIONS; i++)
{
int num = 0;
//refresh the temp array
checkNumrefresh(checkNumbers, PUZZLE_DIMENSIONS);
//looping the rows
for(j = rowData->row; j< PUZZLE_DIMENSIONS; j++)
{
value = sudokuPuzzle[j][i];
if(value >=1 || value<=9)
{
checkNumbers[value-1]++;
}
}
//check row with all values between 1-9
for(k=0; k<PUZZLE_DIMENSIONS; k++)
{
if(checkNumbers[k] == 1)
{
num++;
}
}
//incremeting number of valid rows if row is valid
if(num == PUZZLE_DIMENSIONS)
{
validRowNumber++;
}
}
//if all rows contain 1-9, the thread's status is updated
if(validRowNumber == PUZZLE_DIMENSIONS)
{
threadResult[rowData->idThread] = 1;
}
}
//function validate 3x3 subsection of the puzzle
void * checkSubSection(void * param)
{
//array used by threads to ensure 1-9 are in the subsection
int checkNumbers[PUZZLE_DIMENSIONS]={0};
parameters * subSectionData = (parameters *) param;
int i, j, k, value;
int num = 0;
//loop over subsection rows
for(i = subSectionData->row; i < subSectionData->row + 3; i++)
{
//loop over subsection columns
for(j = subSectionData->column; j < subSectionData->column +3; j++)
{
value = sudokuPuzzle[i][j];
if(value >=1 || value <=9)
{
checkNumbers[value-1]++;
}
}
}
//checking if the subsection contains all numbers 1-9
for(k = 0; k < PUZZLE_DIMENSIONS; k++)
{
if(checkNumbers[k] ==1)
{
num++;
}
}
//if the subsection is valid, worker thread is updated
if(num == PUZZLE_DIMENSIONS)
{
threadResult[subSectionData->idThread] = 1;
}
}
void checkNumrefresh (int *array, int size)
{
memset(array,0,size * sizeof(array));
}
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
void error(char *s,int i,int j)
{
printf(" The sudoku is not valid!");
printf(" Found error at %s. Row: %d, Column: %d",s,i+1,j+1);
getch();
exit(0);
}
// sample correct input 123456789759183426648297315374915268896372154512864973931528647265749831487631592
// sample incorrect input 123456789759180426648297315374915268896372154512864973931528647265749831487631592
void main()
{
char fileName[50];
FILE *filePointer;
int i,j,elements[9][9],num;
char c;
int si,sj,flag;
printf(" Enter file name :: ");
gets(fileName);
printf("%s", fileName);
filePointer = fopen(fileName, "r");
//reading input from file
do {
c = getc(filePointer);
} while (c != EOF);
rewind(filePointer);
//Filling the array:
printf(" ");
for(i=0; i < 9;i++){
for(j=0; j <9;j++){
fscanf(filePointer, " %c", &c);
printf("%c ",c);
// converting char to interger and pushing it to int array
elements[i][j] = c - '0';
}
printf(" ");
}
printf(" ");
/*
checking rows
*/
for(i=0;i<9;i++)
{
flag=0;
for(j=0;j<9;j++)
flag|=1<<(elements[i][j]-1);
if(flag!=1)
error("row",i,j-1);
}
/*
checking columns
*/
for(j=0;j<9;j++)
{
flag=0;
for(i=0;i<9;i++)
flag|=1<<(elements[i][j]-1);
if(flag!=1)
error("col",i-1,j);
}
/*++++++++++++++++++
checking 3 X 3 boxes by creating sub matrixes
*/
for(si=0;si<3;si++)
{
for(sj=0;sj<3;sj++)
{
flag=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
flag|=1<<(elements[si*3+i][sj*3+j]-1);
}
if(flag!=1)
error("square",si*3+i-1,sj*3+j-1);
}
}
printf(" The sudoku is correct");
getch();
}
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
void error(char *s,int i,int j)
{
printf(" The sudoku is not valid!");
printf(" Found error at %s. Row: %d, Column: %d",s,i+1,j+1);
getch();
exit(0);
}
// using threads will cost the cpu utilization instead using matrixes for checking sudoku should do the job.
// sample correct input 123456789759183426648297315374915268896372154512864973931528647265749831487631592
// sample incorrect input 123456789759180426648297315374915268896372154512864973931528647265749831487631592
void main()
{
char fileName[50];
FILE *filePointer;
int i,j,elements[9][9],num;
char c;
int si,sj,flag;
printf(" Enter file name :: ");
gets(fileName);
printf("%s", fileName);
filePointer = fopen(fileName, "r");
//reading input from file
do {
c = getc(filePointer);
} while (c != EOF);
rewind(filePointer);
//Filling the array:
printf(" ");
for(i=0; i < 9;i++){
for(j=0; j <9;j++){
fscanf(filePointer, " %c", &c);
printf("%c ",c);
// converting char to interger and pushing it to int array
elements[i][j] = c - '0';
}
printf(" ");
}
printf(" ");
/*
checking rows
*/
for(i=0;i<9;i++)
{
flag=0;
for(j=0;j<9;j++)
flag|=1<<(elements[i][j]-1);
if(flag!=1)
error("row",i,j-1);
}
/*
checking columns
*/
for(j=0;j<9;j++)
{
flag=0;
for(i=0;i<9;i++)
flag|=1<<(elements[i][j]-1);
if(flag!=1)
error("col",i-1,j);
}
/*++++++++++++++++++
checking 3 X 3 boxes by creating sub matrixes
*/
for(si=0;si<3;si++)
{
for(sj=0;sj<3;sj++)
{
flag=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
flag|=1<<(elements[si*3+i][sj*3+j]-1);
}
if(flag!=1)
error("square",si*3+i-1,sj*3+j-1);
}
}
printf(" The sudoku is correct");
getch();
}