#include <stdio.h>
#include <time.h>

int shift[8]={10,17,15,6,10,17,15,6};
int path[16];
long long count;
int best, best_count;
unsigned long long mask[8]={
  0xfcfcfcfcfcfcfc00,
  0xFEFEFEFEFEFE0000,
  0x7F7F7F7F7F7F0000,
  0x3F3F3F3F3F3F3F00,
  0x003F3F3F3F3F3F3F,
  0x00007F7F7F7F7F7F,
  0x0000FEFEFEFEFEFE,
  0x00FCFCFCFCFCFCFC
};
void recur(int depth, unsigned long long board);
void show_path();
int main()
{
  unsigned long long board, move;
  int i;
  board=-1;
  board&=~mask[0];
  board|=mask[0]>>shift[0];
  best=13;
  for(i=0;i<8;++i){
    if(i==4)++i;
    path[1]=i;
    move = board & ~mask[i];
    if(i<4)move |= (board & mask[i]) >> shift[i];
    else move |= (board & mask[i]) << shift[i];
    recur(2,move);
    if(best_count)break;
  }
  printf("%lld\t%d\n",count,(int)clock());
  printf("%d\t%d\n",best,best_count);
  return 0;
}
void recur(int depth, unsigned long long board){
  unsigned long long move;
  int i,j;
  if(depth>=best){
    ++count;
    return;
  }
  for(i=0;i<8;++i){
    path[depth]=i;
    move = board & ~mask[i];
    if(i<4)move |= (board & mask[i]) >> shift[i];
    else move |= (board & mask[i]) << shift[i];
    if(move&(move-1)==0){
      ++best_count;
      for(j=0;j<best;++j)printf("%d ",path[j]);
      printf("%4d\n",best_count);
      // uncomment to show all steps
      //show_path();
    }else recur(depth+1,move);
    // uncomment to stop after first solution
    //if(best_count)break;
  }
}

void show_path(){
  unsigned long long board, move, x;
  int i,j;
  board=-1;
  for(i=0;i<best;++i){
    move = board & ~mask[path[i]];
    if(path[i]<4)move |= (board & mask[path[i]]) >> shift[path[i]];
    else move |= (board & mask[path[i]]) << shift[path[i]];
    board=move;
    x=1;
    x<<=63;
    printf("Step %d:\n",i+1);
    for(j=0;x;x>>=1){
      if(board&x)printf(" N");
      else printf(" .");
      if(++j%8==0)printf("\n");
    }
    printf("\n");
  }
}