For this project, you will write a multi-threaded application that reads a matrix of 9x9 integers and verifies whether the input is a valid Sudoku or not. Here is an example of a valid Sudoku.

Your solution should use threads to verif if the input is a valid Sudoku or not. Here is an algorithm that you should implement.

  read and store the input in a two dimensional array.
  for each row do:
       create a thread for this row to determine if it contains digits 1 through 9
  for each column do:
       create a thread for this column to determine if it contains digits 1 through 9
  for each grid of 3x3 do:
       create a thread for this grid to determine if it contains digits 1 through 9
  wait on each of the threads:
       if the thread found any missing digit, print an error message.
  if no thread encountered a missing value, print the message "The input is a Sudoku."

You need at least four functions, one to verify if a given row is a valid Sudoku row. Similarly, you need a function to verify whether a given column is vaild or not and one for a grid of 3x3, given the top-left row, column pair of the grid. Finally, you need a function to read the input.

As an example, a thread that checks a grid for valid Sudoku entries (the function is called check3x3Grid) could be called like this.

std::thread(check3x3Grid, sudoku, row, col, &someReturnObject);

sudoku is a two dimensional array that holds the inptu values.

someReturnObject could be a data type that can return True or False depending whether the given grid was a valid Sudoku grid. In addition, you might want this object to hold more values to help with the statements that you need to write in case the function determined that the given grid was not a Sudoku grid — didn't contain each of digits 1 through 9.

The input consists of 9 rows and each row contains 9 integers. Your program should read from the standard input.

The following is a sample input — the spaces are used to make the input easier to read.

7 2 6    3 5 9    4 1 8
4 5 8    1 6 7    2 3 9
9 1 3    8 2 4    7 6 5

1 6 2    9 7 5    3 8 4
3 9 4    2 8 6    1 5 7
8 7 5    4 1 3    9 2 6

5 3 7    6 4 1    8 9 2
6 8 9    7 3 2    5 4 1
2 4 1    5 9 8    6 7 3

The input is a Sudoku.

For the following input, which is not a valid Sudoku (see the digit in red),

7 2 6    3 5 9    4 1 8
4 5 8    1 6 7    2 3 9
9 1 3    8 2 4    7 6 5

1 6 1    9 7 5    3 8 4
3 9 4    2 8 6    1 5 7
8 7 5    4 1 3    9 2 6

5 3 7    6 4 1    8 9 2
6 8 9    7 3 2    5 4 1
2 4 1    5 9 8    6 7 3

your program program should print

Row 4 doesn't have the required values.
Column 3 doesn't have the required values.
Grid (4, 1)  doesn't have the required values.
The input is not a valid Sudoku.

You should turn in one file, called sudoku.cpp includes your solution. I should be able to compile and run your program using the following commands.

g++ -std=c++11 sudoku.cpp -o sudoku.x -lpthread
./sudoku.x < someInputFile