ぶどうの房パズル。 改良版のつもりがかえって遅くなってしまった。

grape.c

#ifndef L
#define L 5  /* 段数を指定する。 */
#endif
#define N ((L+1)*L/2)

static inline int pop_count(int x) {
  static const int const table[] =
    {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  int result=0;

  for(int i=0; i<((L>>3)+1);i++, x>>=8)
    result+=table[x&255];

  return result;
}

static inline _Bool is_valid_pattern(int x) {
  int result=0;
  for(int mask=(1<<L)-1; mask;  mask>>=1, x=(x^(x>>1))&mask)
    result += pop_count(x);

  return result==(N>>1)+(N&1);
}

int answ[N+1], line[N+1];
_Bool used[N+1];

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

struct pair;

struct pair terminate;

struct pair {
  struct pair* even;
  struct pair* odd;
} *root=NULL;

static inline struct pair* make_pair(void) {
  struct pair* newpair=malloc(sizeof(struct pair));
  newpair->even=NULL;
  newpair->odd=NULL;
  return newpair;
}

void candidate_register(int x) {
  struct pair** p=&root;
  for(int mask=1<<(L-1); mask; mask>>=1) {
    if(*p==NULL) *p=make_pair();
    p = mask&x ? &((*p)->odd): &((*p)->even);
  }
  *p=&terminate;
}

void printansw(void) {
  for(int i=1, s=1; s<=N; s+=i, i++)
    printf("%3d ",answ[s]);
  printf("\n");
}

void trie(int depth, struct pair* cand) {
  if(depth>N) printansw();
  else if(line[depth]!=line[depth-1]) {
    if(cand->even != NULL)
      for(int i=2; i<=N; i+=2)
        if(!used[i]) {
          answ[depth]=i;
          used[i]=1;
          trie(depth+1, cand->even);
          used[i]=0;
        }
    if(cand->odd != NULL)
      for(int i=1; i<=N; i+=2)
        if(!used[i]) {
          answ[depth]=i;
          used[i]=1;
          trie(depth+1, cand->odd);
          used[i]=0;
        }
  }
  else {
    int i=abs(answ[depth-1]-answ[depth-line[depth]]);
    if(!used[i]) {
      answ[depth]=i;
      used[i]=1;
      trie(depth+1, cand);
      used[i]=0;
    }
  }
}

void init(void) {
  line[0]=0;
  for(int i=1; i<=N; i++)
    used[i]=0;
  for(int p=1, i=1; i<=L; i++)
    for(int j=0; j<i; j++, p++)
      line[p]=i;

  for(int i=0; i<(1<<L); i++)
    if(is_valid_pattern(i))
      candidate_register(i);
}

int main(void) {
  init();
  trie(1, root);
  return 0;
}