sudoku.cpp

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

const int N = 3;
const int M = N * N;
struct Sudoku {
  int data[M * M];
  int current;
  Sudoku() {}
  Sudoku(const char* c, int i = 0) {
    for (int i = 0; i < M * M; i++) {
      data[i] = c[i] - '0';
    }
    current = i;
  }
  bool allowed(int v, int i) {
    int x = i % M;
    int y = i / M;
    int bx = x / N * N;
    int by = y / N * N;
    for (int j = 0; j < M; j++) {
      int ox = j % N;
      int oy = j / N;
      if (x != j && v == data[y * M + j]) return false;
      if (y != j && v == data[j * M + x]) return false;
      if (i != (by + oy) * M + bx + ox && v == data[(by + oy) * M + bx + ox]) return false;
    }
    return true;
  }
  bool solved() {
    for (int i = 0; i < M * M; i++) {
      if (!data[i]) return false;
      if (!allowed(data[i], i)) return false;
    }
    return true;
  }
  bool backtrack(Sudoku* w, int* n);
  void print() {
    for (int i = 0; i < M * M; i++) {
      printf("%d", data[i]);
      /* if (i % N == N - 1) printf(" "); */
      /* if (i % M == M - 1) printf("\n"); */
      /* if (i % (N * M) == N * M - 1) printf("\n"); */
    }
    printf("\n");
  }
};

Sudoku stack[10000];
int curr = 0;
int waiting = 0;
const int T = 4;
const int W = 1;
int pushes = 0;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t wait = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t d = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
pthread_cond_t done = PTHREAD_COND_INITIALIZER;

void pop(Sudoku* w, int* n) {
  pthread_mutex_lock(&mutex);
  while(curr < 0) {
    pthread_mutex_lock(&wait);
    waiting++;
    if (waiting >= T) {
      pthread_cond_signal(&done);
    }
    pthread_mutex_unlock(&wait);
    pthread_cond_wait(&cond, &mutex);
    pthread_mutex_lock(&wait);
    waiting--;
    pthread_mutex_unlock(&wait);
  }
  int i = 0;
  while (i < W && curr >= 0) {
    w[i++] = stack[curr--];
  }
  *n = i;
  pthread_mutex_unlock(&mutex);
}

void push(Sudoku* w, int n) {
  pthread_mutex_lock(&mutex);
  for (int i = 0; i < n; i++) {
    stack[++curr] = w[i];
    pushes++;
  }
  pthread_cond_signal(&cond);
  pthread_mutex_unlock(&mutex);
}

bool Sudoku::backtrack(Sudoku* w, int* n) {
  int i = 0;
  while (current < M * M && data[current]) current++;
  if (current >= M * M) return true;
  for (int j = 1; j <= M; j++) {
    if (!allowed(j, current)) continue;
    Sudoku tmp = *this;
    tmp.data[current] = j;
    tmp.current++;
    w[i++] = tmp;
  }
  *n = i;
  return false;
}

pthread_mutex_t p = PTHREAD_MUTEX_INITIALIZER;

void* worker(void* data) {
  int id = *(int*)data;
  Sudoku w[W];
  Sudoku w_n[W * M];
  for (;;) {
    int n = 0;
    pop(w, &n);
    /* pthread_mutex_lock(&p); */
    /* printf("worker %d solving ", id); */
    /* s.print(); */
    /* pthread_mutex_unlock(&p); */
    /* usleep(1000 * 500); */
    int j = 0;
    int k;
    for (int i = 0; i < n; i++) {
      if (w[i].backtrack(&w_n[j], &k)) {
        printf("worker %d found solution: ", id);
        w[i].print();
      }
      j += k;
    }
    push(w_n, j);
  }
}

int main() {
  stack[0] = Sudoku("000801000000000043500000000000070800020030000000000100600000075003400000000200600");
  stack[0].print();
  int ids[T];
  pthread_t threads[T];
  for (int i = 0; i < T; i++) {
    ids[i] = i;
    int s = pthread_create(&threads[i], NULL, worker, (void*)&ids[i]);
  }

  pthread_mutex_lock(&d);
  pthread_cond_wait(&done, &d);
  printf("%d items pushed to stack\n", pushes);
  printf("No more solutions\n");

  return 0;
}