C++にN-Queensを移植

してみた。

昨日のErlang版をほぼストレートに移植。リストは最初STLを使おうとしたけど、再帰と相性が悪いので、自前で定義。リストのdeleteはさぼり。
実行時間を計測してみると、サイズが13で６秒弱くらい。

• KLIC速す！（ほぼ同じ速度）

再帰が原因かと思い、いくつかループに書き換えてみたりしたが、実行速度はあまり変わらず。リストセルのnewに時間がかかってるんだろうなぁ。
PARDSで並列化しようと思って、とりあえずnewを共有メモリ上に取るよう再定義したら激遅に。 orz
PARDSでの並列化はすぐにはできなさそう。

まぁ、本来C/C++でやるのなら、リストを使わず別のデータ構造でやるんだろうけど。

ソースは以下：

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

template <class T> class List{
public:
  T value;
  List<T>* next;
};

List<int>* generate(int n){
  if(n > 0) {
    List<int>* c = new List<int>;
    c->value = n; c->next = generate(n-1);
    return c;
  } else {
    return 0;
  }
}

template <class T> List<T>* append(List<T>* a, List<T>* b){
  if(a != 0){
    T h = a->value;
    List<T>* t = a->next;
    List<T>* res = new List<T>;
    res->value = h;
    res->next = append(t,b);
    return res;
  } else {
    return b;
  }
}

List<List<int>*>* qu(List<int>* plu, List<int>* ls, List<int>* lp){
  if(plu == 0) {
    if(ls == 0) {
      List<List<int>*>* res = new List<List<int>*>;
      res->value = lp;
      res->next = 0;
      return res;
    } else {
      return 0;
    }
  } else {
    List<List<int>*>* check(int, int, List<int>*, List<int>*, List<int>*);

    List<int>*  lu = plu->next;
    int p = plu->value;
    List<int>* lr = append<int>(lu, ls);
    List<List<int>*>* ans1 = check(p, 1, lr, lp, lp);
    List<int>* nls = new List<int>;
    nls->value = p;
    nls->next = ls;
    List<List<int>*>* ans2 = qu(lu, nls, lp);
    return append<List<int>*>(ans1, ans2);
  }
}

List<List<int>*>* check(int p, int d, List<int>* l,
			List<int>* qlp0, List<int>* lp){
  if(qlp0 == 0) {
    List<int>* plp = new List<int>;
    plp->value = p;
    plp->next = lp;
    return qu(l,0,plp);
  } else {
    int q = qlp0->value;
    if(q + d == p || q - d == p)
      return 0;
    else{
      List<int>* lp0 = qlp0->next;
      return check(p,d+1,l,lp0,lp);
    }
  }
}

int main(int argc, char* argv[])
{
  if(argc < 2) {
    printf("qu NUM\n");
    exit(0);
  }

  int num = atoi(argv[1]);

  List<int>* gen = generate(num);
  List<List<int>*>* res = qu(gen,0,0);

  int i = 0;
  for(; res != 0; res = res->next, i++){
    /*    List<int>* a = res->value;
      for(; a != 0; a = a->next)
      printf("%d ",a->value);
      printf("\n"); */
  }
  printf("num = %d\n",i);
}