Determine number of peg solitaire board positions that can be reached from start position, which allow to reach target position

sol.dfs.c

/* gcc -O6 -Wall -pedantic -Wextra cnt.dfs.c -std=c99 -o cnt.dfs */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <inttypes.h>
#include <unistd.h>

inline uint64_t pow2(unsigned exp)  { return UINT64_C(1) << exp; }

char B[3][9][9]={
{
".........",  /* English */
"...ooo...",
"...ooo...",
".ooooooo.",
".oooxooo.",
".ooooooo.",
"...ooo...",
"...ooo...",
"........."
},{
".........",  /* French */
"...ooo...",
"..ooooo..",
".oooxooo.",
".ooooooo.",
".ooooooo.",
"..ooooo..",
"...ooo...",
"........."
},{
"...ooo...",  /* 3-3-2-2 */
"...ooo...",
"...ooo...",
".oooooooo",
".oooxoooo",
".oooooooo",
"...ooo...",
"...ooo...",
"........."
}
};

int N[9][9];

int m,cnt;
uint64_t M[7*9*2*2];
uint64_t D[7*9*2*2];

uint64_t dfs(uint64_t u, uint8_t *A)
{
  uint64_t cnt=1;

  assert(A[u>>3] & 1<<(u%8));
  A[u>>3] ^= 1<<(u%8);

  for(int d=0; d<m; ++d)
  {
    if (!(u & M[d]) && ((u & D[d]) == D[d]))
    {
      uint64_t n = u^(M[d]|D[d]);
      if (A[n>>3] & 1<<(n%8))
        cnt += dfs(n, A);
    }
  }

  return cnt;
}

int main(int argc, char *argv[])
{
  uint64_t u;
  uint8_t *A, brd;
  FILE *src;

  assert(argc==3);
  sscanf(argv[2],"%"SCNx64,&u);

       if (strcmp(argv[1],"English")==0) brd=0;
  else if (strcmp(argv[1],"French")==0)  brd=1;
  else if (strcmp(argv[1],"3-3-2-2")==0) brd=2;
  else assert(!"unknown board");

  m=0;
  for(int i=0; i<9; ++i)
  {
    for(int j=0; j<9; ++j)
    {
      N[i][j] = (B[brd][i][j]!='.') ? cnt++ : 255;

      if (i>1)
        if (N[i][j]!=255 && N[i-1][j]!=255 && N[i-2][j]!=255)
        {
          M[m]   = (pow2(N[i-2][j]));
          D[m++] = (pow2(N[i][j])) | (pow2(N[i-1][j]));
          M[m]   = (pow2(N[i][j]));
          D[m++] = (pow2(N[i-1][j])) | (pow2(N[i-2][j ]));
        }  

      if (j>1)
        if (N[i][j]!=255 && N[i][j-1]!=255 && N[i][j-2]!=255)
        {
          M[m]   = (pow2(N[i][j-2]));
          D[m++] = (pow2(N[i][j])) | (pow2(N[i][j-1]));
          M[m]   = (pow2(N[i][j]));
          D[m++] = (pow2(N[i][j-1])) | (pow2(N[i][j-2]));
        }  
    }
  }

  assert( (A = malloc(pow2(cnt-3))) );
  assert( (src=fopen(argv[1],"rb")) );
  assert(1 == fread(A, pow2(cnt-3), 1, src));
  fclose(src);

  printf("%"PRIu64"\n", dfs(u, A));

//  fwrite(A, pow2(cnt-3), 1, stderr);

  free(A);  

  return 0;
}