1
\$\begingroup\$

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 <pthread.h>
#include <unistd.h>

#define threadNum 4

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

int isValid = 1;

//
// threadpool for col calculations
//
typedef struct Task {
  int** input;
  int type;
  int index;
  int subX;
  int subY;
} Task;

Task taskQueue[3*square];
int taskCount = 0;

pthread_mutex_t mutexQueue;
pthread_cond_t condQueue;

void checkTask(Task* task){
  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;
}

void* startThread(void* args){
  while(1){
    Task task;
    pthread_mutex_lock(&mutexQueue);
    task = taskQueue[0];
    int i;
    for(i = 0; i < taskCount; i++){
      taskQueue[i] = taskQueue[i + 1];
    }
    taskCount--;
    pthread_mutex_unlock(&mutexQueue);
    checkTask(&task);
    if(taskCount == 0){
      break;
    }
  }
}

void submitTask(Task task){
  pthread_mutex_lock(&mutexQueue);
  taskQueue[taskCount] = task;
  taskCount++;
  pthread_mutex_unlock(&mutexQueue);
  pthread_cond_signal(&condQueue);
}

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];
    }
  }

  //
  // execute threadpool
  //
  pthread_t th_col[threadNum];
  pthread_mutex_init(&mutexQueue, NULL);
  pthread_cond_init(&condQueue, NULL);
  for(int i = 0; i < threadNum; i++){
    if(pthread_create(&th_col[i], NULL, &startThread, NULL) != 0){
      printf("failed to create thread\n");
    }
  }

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

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

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

  for(int i = 0; i < threadNum; i++){
    if(pthread_join(th_col[i], NULL) != 0){
      printf("failed to join thread\n");
    }
  }
  pthread_mutex_destroy(&mutexQueue);
  pthread_cond_destroy(&condQueue);

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

  free(input);
  return 1;
}
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – ggorlen
    Aug 15 at 1:59
  • \$\begingroup\$ It is explained much better here. '-1' is code here for "empty" position. \$\endgroup\$
    – AKRA
    Aug 15 at 9:19
  • \$\begingroup\$ 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? \$\endgroup\$
    – ggorlen
    Aug 15 at 14:22
  • 1
    \$\begingroup\$ Yep it is correct, haven't tried benchmarking it yet though ... \$\endgroup\$
    – AKRA
    Aug 15 at 17:42
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.