I. Introduction

The Sudoku puzzle was created in the late $19$th century and popularized in Japan in the $1980$s before

gaining international fame. A Sudoku puzzle features a $99$ grid, where each column, row, and each of

the nine $33$ sub grids must contain all digits from $1$ to $9.$ Some digits are pre$-$filled to set the stage for the

puzzle. Below is an example of a valid Sudoku puzzle setup. Sudoku puzzles require logical reasoning for

their solution. Each puzzle is designed to have a unique solution.

II$.$ Requirement

This project focuses on verifying the validity of a given Sudoku puzzle solution using C$++$ and

multithreaded programming. The verification process involves creating threads with specific tasks. For

example, we can create one thread to verify each column containing all digits $1$ through $9,$ one other

thread to verify each row containing all the digits $1$ through $9,$ and nine threads to verify each of nine $33$

sub grid containing all the digits $1$ through $9.$ This approach totals eleven separate threads. However,

students are encouraged to explore and implement alternative multithreading strategies.

III. Code Samples and Strategy

Data structure considerations

Threads are created by the parent thread, with each worker thread receiving parameters indicating the

specific location in the Sudoku grid it needs to check. This is facilitated by defining a structure for

parameter passing. Below is an image of a sample code segment.

$/*$ Structure for passing data to threads $*/$

typedef struct $\{$

int row;

int column;

$\}$ parameters;

$/*$ Optionally, include a thread number $*/$

typedef struct $\{$

int thread$\_$number;

int row;

int column;

$\}$ parameters;

$/*$ Example of creating a thread and passing data $*/$

parameters ${?}^{**}$ data parameters $\{$:${?}^{**})$ malloc $($sizeof parameters $\{$:$)$;

data$->$row $=0$; $//$ Starting at first row

data$->$column $=0$; $//$ Starting at first column

The data pointer is then passed to the pthread$\_$create$()$ function, which, in turn, passes it as a

parameter to the function that runs as a separate thread.

Verification of valid digits

One approach to verify if a digit is present in a block $($row$,$ column, or $33$ grid$)$ is to use an existence

array initially set to $0.$ Mark it as $1$ if the digit is found, $a(i)=1$ where the $i$ is both the index and the

digit.

Returning Results to the Parent Thread

Worker threads are tasked with determining the validity of specific regions of the Sudoku puzzle. To

communicate their findings to the parent thread, create an array of integer values accessible to all

threads. Each index in this array corresponds to a worker thread. A value of $1$ indicates the region is

valid, while $0$ indicates invalidity. The parent thread reviews these results to ascertain the puzzle's

overall validity.

Testing

Students shall make several text files. Each of them is a solution that includes $9$ lines with each line

having $9$ digits separated by a comma. Some of the solutions are valid while others are not. For

example, a comma separated file. Your code shall be able to read the text file for testing.