# Validate Empty Sudoku: Multi-Threaded Solution

The problem is that we have an unsolved sudoku board, and we want to validate it, we need to check each column, row and sub-square.

Here we represent a empty cell with -1.

My idea was to create a multi-threaded solution to this problem, where we deal with each case.

I didn't know how to pool threads before this problem, so it's probably not 100% ...

In "check task", we have type 0: columns, type 1: rows and type 2: squares.

The rest of the solution is basically just messing around with the pthread library, and it seems to work.

Could it be better in any way?

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

#define squareUnit 2
#define square 4
int** input;

int isValid = 1;

//
//
int** input;
int type;
int index;
int subX;
int subY;

int** input = task -> input;
int available[] = {0,0,0,0,0,0,0,0,0,0};
int type = task -> type;
if(type == 0){
int index = task -> index;
for(int i = 0; i < square; i++){
if(input[i][index] == -1){
continue;
}
else{
available[input[i][index]]++;
if(available[input[i][index]] > 1){
isValid = 0;
printf("col index: %d fails\n", index);
return;
}
}
}
printf("col index: %d passes\n", index);
}
if(type == 1){
int index = task -> index;
for(int i = 0; i < square; i++){
if(input[index][i] == -1){
continue;
}
else{
available[input[index][i]]++;
if(available[input[index][i]] > 1){
isValid = 0;
printf("row index: %d fails\n", index);
return;
}
}
}
printf("row index: %d passes\n", index);
}
if(type == 2){
int subX = task -> subX;
int subY = task -> subY;
for(int i = subX; i < subX + squareUnit; i++){
for(int j = subY; j < subY + squareUnit; j++){
if(input[i][j] == -1){
continue;
}
else{
available[input[i][j]]++;
if(available[input[i][j]] > 1){
isValid = 0;
printf("square: %d %d fails\n", subX, subY);
return;
}
}
}
}
printf("square: %d %d passes\n", subX, subY);
}
return;
}

while(1){
int i;
for(i = 0; i < taskCount; i++){
}
break;
}
}
}

}

int main(void){

//
// input example
//
int arrayIn[][square] = {
{1,-1,-1,2},
{2,-1,1,-1},
{0,3,-1,-1},
{1,-1,-1,0}
};

input = malloc(square * sizeof(int*));
for(int i = 0; i < square; i++){
input[i] = malloc(square * sizeof(int));
for(int j = 0; j < square; j++){
input[i][j] = arrayIn[i][j];
}
}

//
//
for(int i = 0; i < threadNum; i++){
}
}

for(int i = 0; i < square; i++){
.input = input,
.type = 0,
.index = i,
.subX = -1,
.subY = -1
};
}

for(int i = 0; i < square; i++){
.input = input,
.type = 1,
.index = i,
.subX = -1,
.subY = -1
};
}

int subX = 0;
int subY = 0;
for(int i = 0; i < squareUnit; i++){
subY = 0;
for(int j = 0; j < squareUnit; j++){
.input = input,
.type = 2,
.index = -1,
.subX = subX,
.subY = subY
};
subY = subY + squareUnit;
}
subX = subX + squareUnit;
}

for(int i = 0; i < threadNum; i++){
}
}

//
// output result
//
switch(isValid){
case 0:
printf("does not pass\n");
break;
case 1:
printf("passes\n");
break;
}

free(input);
return 1;
}

• I'm not really clear what validating an empty sudoku would entail. I can understand validating a proposed solution, but not an empty board. arrayIn is a 4x4 matrix with negative numbers that appears to have no relation to sudoku. Maybe I'm missing something obvious. Aug 15 at 1:59
• It is explained much better here. '-1' is code here for "empty" position.
– AKRA
Aug 15 at 9:19
• Thanks for the link. That looks like a normal 9x9 board only, although I understand what you mean by validating a partial board. This is a subprocedure of solving Sudoku with backtracking where you ensure a move made is legal before continuing to child positions. Does the code here solve this LC problem? Did you benchmark it against single-threaded to ensure you're actually getting a speedup? Aug 15 at 14:22
• Yep it is correct, haven't tried benchmarking it yet though ...
– AKRA
Aug 15 at 17:42

I usually like to rewrite symbols like

#define threadNum 4
#define squareUnit 2
#define square 4


as static const ints, since that makes the type easier to see.

Since this is a single-translation-unit program, all of your functions other than main can also be static.

You should be using C99 or later, in which case

int i;
for(i = 0; i < taskCount; i++){


would be

for (int i = 0; i < taskCount; i++) {


This declaration:

int arrayIn[][square] = {


seems a little risky. If you need for your array to be square, then I would expect no implicit dimensions and instead

int arrayIn[square][square] = {


which would catch any accidents around the size of the outer dimension.

Rather than a switch here:

  switch(isValid){
case 0:
printf("does not pass\n");
break;
case 1:
printf("passes\n");
break;
}


I would expect a simple

puts(isValid ? "passes" : "does not pass");


You have a large block of nearly-duplicated code between types 0 and 1. The common element on the inside can be factored out into a function that accepts i, j, available, and the row/column title string.