#define _GNU_SOURCE
#include <stdio.h>
#include <sys/time.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <sched.h>
#include <assert.h>

#define MAX_SIZE         32
#define MAX_PROC         128

/* n女王問題アルゴリズム */
typedef int (*nq_func) (int P, int myid, int n, int sym, int d);

/* 構造体 */

/* アルゴリズム */
struct nq_algorithm{
  int id;
  nq_func func;
  nq_func func2;
  char *desc;
};

/* workerに渡すデータ */
struct warg {
  int myid;
  int n;
  int sym;
  int d;
  int P;
  nq_func fw;
};

/* プロトタイプ宣言 */
int systhr_create(void * (*start_func)(void *), void *arg);
void assign_cpu(int cpu);
int p_helper(nq_func f, nq_func fw, int n, int P, int sym, int d);
void set_result(int r);
void *fworker_assign_cpu(void *arg);
double elapsed_time(struct timeval tp[2]);
static inline int sym_check(int n, int k, char *a, char *col);
int distinct_solutions(int n, char *pos, int d);
void output_solution(int n, char *pos);
void usage(char *filename);

/* 逐次実装 */
int nqueens_a(int P, int myid, int n, int sym, int d);

/* 並列実装（関数対）*/
int worker(int P, int myid, int n, int sym, int d);
int master(int P, int myid, int n, int sym, int d);


/* アルゴリズムリスト */
struct nq_algorithm algorithm[] =
{
  {1, nqueens_a,   NULL,      "n-queens based on arrays"},
  /* 並列実装は、master 用と worker 用の2つの関数を登録 */
  {101, master, worker,    "Please implement it"}, 
};


/* main */
int main(int argc, char *argv[])
{
  struct timeval tp[2];
  double elapsed;
  struct nq_algorithm *nq;
  int p = 0, n = -1, al = 0, debug = 0, sym = 0, silent = 0;
  int s;
  int i;

  
  /* コマンドライン引数の解釈 */
  for(i = 1; i < argc; i++){
    if(strcmp(argv[i], "-d") == 0){
      /* 解を表示する */
      debug = 1;
    }else if(strcmp(argv[i], "-a") == 0){
      /* 探索アルゴリズムが指定される */
      i++;
      if(i == argc){
        printf("Specify the algorithm to use: %s\n", argv[i - 1]);
        return 0;
      }
      sscanf(argv[i], "%d", &al);
    }else if(strcmp(argv[i], "-p") == 0){
      /* ワーカスレッド数が指定される */
      i++;
      if(i == argc){
        printf("Specify the number of worker threads to use: %s\n", argv[i - 1]);
        return 0;
      }
      sscanf(argv[i], "%d", &p);
      /* スレッド数が不正ならば適当な値に変更して続ける */
      if(p < 1){
        printf("The number of threads must be 1 - %d: regarded as 1\n", MAX_PROC);
        p = 1;
      }else if(p > MAX_PROC){
        printf("The number of threads must be 1 - %d: regarded as %d\n", MAX_PROC, MAX_PROC);
        p = MAX_PROC;
      }
    }else if(argv[i][0] >= '0' && argv[i][0] <= '9'){
      /* サイズが指定される */
      sscanf(argv[i], "%d", &n);
      if(n < 1 || n > MAX_SIZE){
        printf("The size must be 1 - %d\n", MAX_SIZE);
        return 0;
      }
    }else if(strcmp(argv[i], "-h") == 0){
      /* ヘルプ */
      usage(argv[0]);
      return 0;
    }else if(strcmp(argv[i], "-t") == 0){
      /* 経過時間のみ表示する */
      silent = 1;
    }else if(strcmp(argv[i], "-s") == 0){
      /* 対称解を含めない */
      sym = 1;
    }else{
      /* 不明なパラメータ */
      printf("Invalid Parameter: %s\n", argv[i]);
      return 0;
    }
  }

  if (n == -1) {
    printf("Number of queens required\n");
    return 1;
  }

  /* 既定のプロセッサ数とアルゴリズム */
  if(al == 0){
    /* アルゴリズム未指定 */
    if(p <= 1){
      /* 逐次版の中で速いものを選んでおく */
      al = 1;
    }else{
      /* 並列版の中で速いものを選んでおく */
      al = 101;
    }
  }else{
    /* アルゴリズム指定済み */
    if(p == 0){
      /* スレッド数未指定 */
      if(al >= 101){
        /* 並列版アルゴリズム指定済み */
        /* デフォルトは P = 2 */
        p = 2;
      }
    }
  }

  /* アルゴリズムを指定する */
  nq = NULL;
  for(i = 0; i < sizeof(algorithm) / sizeof(struct nq_algorithm); i++){
    if(algorithm[i].id == al){
      nq = &algorithm[i];
      if(!silent) printf("*** %s ***\n", nq->desc);
      break;
    }
  }
  /* 該当するアルゴリズムなし */
  if(nq == NULL){
    printf("Invalid Parameter: -a %d\n", al);
    return 0;
  }

  if(!silent) printf("running queens %d\n", n);
     
  /* 時間測定開始 */
  gettimeofday(tp, 0);

  /* 計算開始 */
  if(al < 101){
    /* 逐次 */
    s = ((nq_func)nq->func)(0, 0, n, sym, debug);
  }else{
    /* 並列 */
    s = p_helper(nq->func, nq->func2, n, p, sym, debug);
  }

  /* 時間測定終了, 結果表示 */
  gettimeofday(tp+1, 0);
  elapsed = elapsed_time(tp);

  if(!silent){
    printf("%d answers\n", s);
    printf("Elapsed Time: %f sec.\n", elapsed);
  }else{
    printf("%f\n", elapsed);
  }
     
  return 0;
}

/* スレッド生成 */
int systhr_create(void * (*start_func)(void *), void *arg){
  int status = 0;
  pthread_t tid;
  pthread_attr_t attr;
  pthread_attr_init(&attr);
  status = pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
  if(status == 0) status = pthread_create(&tid, &attr, start_func, arg);
  if(status != 0) status = pthread_create(&tid, 0,     start_func, arg);
  return status;
}

/* 使用するCPUを指定する */
void assign_cpu(int cpu){
  /* Linuxワークステーション用の処理 */
  cpu_set_t cpu_set;
  /* 指定したCPUのみを集合に加える */
  CPU_ZERO(&cpu_set);
  CPU_SET(cpu, &cpu_set);
  /* 割り当て */
  sched_setaffinity(0, sizeof(cpu_set_t), &cpu_set);
}


/* 使用するCPUを指定 & start a worker thread */
void *fworker_assign_cpu(void *arg)
{
  struct warg *w = arg;
  assign_cpu(w->myid);
  w->fw(w->P,w->myid,w->n,w->sym,w->d);
  return NULL;
}

/* 並列処理の補助用 */
int p_helper(nq_func f, nq_func fworker, int n, int P, int sym, int d){
  int i, r;
  struct warg w[MAX_PROC];
  
  for(i=0;i<P;i++){  /* P 個の woker を起動し、ここのコアに貼り付ける */
    w[i].myid = i;
    w[i].n = n;
    w[i].sym = sym;
    w[i].d = d;
    w[i].P = P;
    w[i].fw = fworker;
    systhr_create(fworker_assign_cpu, w+i);
  }

  /* start the master thread */
  r = f(P, P, n, sym, d);

  return r;
}

/* 経過時間の計算 */
double elapsed_time(struct timeval tp[2])
{
  return tp[1].tv_sec-tp[0].tv_sec+1e-6*(tp[1].tv_usec-tp[0].tv_usec);
}


void usage(char *filename){
  int i;

  printf("Usage: %s [size] [options...]\n", filename);
  puts("Options:");
  puts("  -a <number>: choose the algorithm to use");
  for(i = 0; i < sizeof(algorithm) / sizeof(struct nq_algorithm); i++){
    printf("     %3d: %s\n", algorithm[i].id, algorithm[i].desc);
  }
  puts("  -d: list all solutions");
  puts("  -h: show this help");
  puts("  -s: exclude symmetric solutions (search unique solutions)");
  puts("  -t: only show elapsed time (if no error occured)");
  puts("  -p <number>: the number of worker threads to use");
}


/*------------ 以下、アルゴリズム実装 -------------------------*/

/*------------ 逐次版 --------------------------------------*/

/* 対称解を考慮して探索を打ち切り出来るか調べる */
static inline int sym_check(int n, int k, char *a, char *col){
  int i;

  /* 裏返し */
  for(i = 0; i < k; i++){
    int t = n - 1 - a[i];
    if(t < a[i]){
      /* 別のところで対称解が見つかる */
      return 0;
    }else if(t > a[i]){
      /* OK */
      break;
    }
  }
  
  /* 右90度回転 */
  for(i = 0; i < k; i++){
    if(col[i] == -1){
      /* 判定できないので通す */
      break;
    }else{
      int t = n - 1 - col[i];
      if(t < a[i]){
        /* 別のところで対称解が見つかる */
        return 0;
      }else if(t > a[i]){
        /* OK */
        break;
      }
    }
  }

  /* 右90度回転の左右反転 */
  for(i = 0; i < k; i++){
    int t = col[i];
    if(t == -1){
      /* 判定できないので通す */
      break;
    }else if(t < a[i]){
      /* 別のところで対称解が見つかる */
      return 0;
    }else if(t > a[i]){
      /* OK */
      break;
    }
  }

  /* n != kのときは「大きさ」が不確定なのでチェックしない */
  if(n == k){
    /* 180度回転 */
    for(i = 0; i < n; i++){
      int t = n - 1 - a[n - 1 - i];
      if(t < a[i]){
        /* 別のところで対称解が見つかる */
        return 0;
      }else if(t > a[i]){
        /* OK */
        break;
      }
    }
    
    /* 180度回転の左右反転 */
    for(i = 0; i < n; i++){
      int t = a[n - 1 - i];
      if(t < a[i]){
        /* 別のところで対称解が見つかる */
        return 0;
      }else if(t > a[i]){
        /* OK */
        break;
      }
    }
  }

  /* 左90度回転 */
  for(i = 0; i < k; i++){
    int t = col[n - 1 - i];
    if(t == -1){
      break;
    }else if(t < a[i]){
      /* 別のところで対称解が見つかる */
      return 0;
    }else if(t > a[i]){
      /* OK */
      break;
    }
  }

  /* 左90度回転の裏返し */
  for(i = 0; i < k; i++){
    int t = col[n - 1 - i];
    if(t == -1){
      break;
    }else if(n - 1 - t < a[i]){
      /* 別のところで対称解が見つかる */
      return 0;
    }else if(n - 1 - t > a[i]){
      /* OK */
      break;
    }
  }

  return 1;
}

/* 1つの解から発生する対称解の数を計算する */
int distinct_solutions(int n, char *pos, int d){
  char tmp[MAX_SIZE];
  int ret = 1;
  int i;

  /* まず自分自身を出力する */
  if(d) output_solution(n, pos);

  /* n == 1は特別扱い */
  if(n == 1) return 1;

  /* (n >= 2) 左右反転も表示する */
  if(d){
    for(i = 0; i < n; i++){
      tmp[i] = n - 1 - pos[i];
    }
    output_solution(n, tmp);
  }

  /* 右90度回転して同じ形か */
  for(i = 0; i < n; i++){
    if(pos[(int)pos[i]] != n - 1 - i){
      /* 異なる */
      break;
    }
  }
  if(i < n){
    /* 解を表示する */
    if(d){
      /* 右90度回転を出力する */
      for(i = 0; i < n; i++){
        tmp[(int)pos[i]] = n - 1 - i;
      }
      output_solution(n, tmp);
      /* その左右反転も表示する */
      for(i = 0; i < n; i++){
        tmp[i] = n - 1 - tmp[i];
      }
      output_solution(n, tmp);
    }
    /* 1個カウントする */
    ret++;

    /* 90度回転が異なる形のときのみ, 180度回転して同じ形か調べる */
    for(i = 0; i < n; i++){
      if(pos[i] != n - 1 - pos[n - 1 - i]){
        /* 異なる, 同時に左90度回転も異なる */
        break;
      }
    }
    if(i < n){
      /* 解を表示する */
      if(d){
        /* 180度回転を出力する */
        for(i = 0; i < n; i++){
          tmp[i] = n - 1 - pos[n - 1 - i];
        }
        output_solution(n, tmp);
        /* その左右反転も表示する */
        for(i = 0; i < n; i++){
          tmp[i] = n - 1 - tmp[i];
        }
        output_solution(n, tmp);
        /* 左90度回転を表示する */
        for(i = 0; i < n; i++){
          tmp[n - 1 - pos[i]] = i;
        }
        output_solution(n, tmp);
        /* その左右反転も表示する */
        for(i = 0; i < n; i++){
          tmp[i] = n - 1 - tmp[i];
        }
        output_solution(n, tmp);        
      }
      /* 2個カウントする */
      ret += 2;
    }
  }

  /* 左右反転は常に異なる解を与える */
  ret <<= 1;

  return ret;
}

/* 出力の排他制御用(正しく解の形状を表示する) */
pthread_mutex_t output_lk = PTHREAD_MUTEX_INITIALIZER;

/* 解の表示 */
void output_solution(int n, char *pos){
  int i, j;

  /* 出力が崩れないよう排他制御を行う */
  pthread_mutex_lock(&output_lk);

  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      if(pos[i] == j) putchar('Q'); else putchar('.');
      putchar(' ');
    }
    putchar('\n');
  }
  putchar('\n');

  /* 排他制御終わり */
  pthread_mutex_unlock(&output_lk);  
}

/* 配列版高速バージョン (-a 1) : 使用可能列配列、斜め利き配列、対称解枝狩り、明示的スタックの使用 */
int nqueens_a(int P, int myid, int n, int sym, int d)
{
  /* これまでに見つかった解の個数 */
  int s = 0;
  /* 現在の配置 */
  char pos[MAX_SIZE];
  char pos_col[MAX_SIZE];
  /* スタック */
  int stack_i[MAX_SIZE];

  /* 左上から右下方向 */
  char used_d1[MAX_SIZE << 1] = {0};
  /* 右上から左下方向 */
  char used_d2[MAX_SIZE << 1] = {0};

  int tmp;
  int i;
  int k = 0;
  
  /* 使用できる列番号リスト */
  for(i = 0; i < n; i++){
    pos[i] = i;
    pos_col[i] = -1;
  }

Ls:
  if (n == k){
    /* n個のqueenが置けた */
    if(sym){
      /* 全解を考えず見つかったものだけ表示する */
      if(d) output_solution(n, pos);
      /* 1個カウントする */
      s++;
    }else{
      /* 全解をカウントし, 必要ならば解を表示する */
      s += distinct_solutions(n, pos, d);
    }
  }else{
    /* try each possible position for queen <k> */
    for (i = k; i < n; i++) {
      if (!used_d1[k + pos[i]] && !used_d2[k + (n - 1 - pos[i])]){
        if(i > k){
          /* リストを入れ替える */
          tmp = pos[k];
          pos[k] = pos[i];
          pos[i] = tmp;
        }
        pos_col[(int)pos[k]] = k;
        if(sym_check(n, k + 1, pos, pos_col)){
          /* 明示的なスタックにより先を探索する */
          used_d1[k + pos[k]] = 1;
          used_d2[k + (n - 1 - pos[k])] = 1;
          /* 退避処理 */
          stack_i[k++] = i;
          goto Ls;
        Lc:
          /* 復元処理 */
          i = stack_i[--k];
          used_d1[k + pos[k]] = 0;
          used_d2[k + (n - 1 - pos[k])] = 0;
        }
        pos_col[(int)pos[k]] = -1;
        if(i > k){
          /* リストを元に戻す */
          tmp = pos[k];
          pos[k] = pos[i];
          pos[i] = tmp;
        }
      }
    }

    /* 現在の呼び出しから脱出する */
    if(k == 0) return s;
  }
  goto Lc;
}

/*---------------------- parallel implementations ----------------------*/

// see http://www.yasugi.ai.kyutech.ac.jp/3p/k6.html#ms
//     http://www.yasugi.ai.kyutech.ac.jp/3p/ms.c

/* worker 用関数。繰り返し仕事をもらい処理する。*/
int worker(int P, int myid, int n, int sym, int d)
{
  return 0;
}

/* master 用関数。仕事を生成する*/
int master(int P, int myid, int n,  int sym, int d)
{
  return 0;
}