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

// 2018. Giovanni Resta
// Computes A(171760) for N = 1..11 and shows a possible
// configuration. Running time for each case under one minute
// on a modern PC.

// To be compiled with gcc or another compiler
// capable of 128-bit integers. Tested only under linux.

// a board NxN with N<=11 is stored in 128-bit integer
// using a bit for each square.

// two queen configurations are then compatible if and only if
// the binary AND of the corresponding integers is zero.

// size of the board
#define N (9)

// QLong is how I call the 128-bit type
typedef __uint128_t QLong;

#if N>11 || N<1
#error  Error: N out of range (1..11)
#endif

// number of possible configurations for N queens, N <= 11
const int nConf[12]={0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680};

// for printing boards
const char S[12]={'.','1','2','3','4','5','6','7','8','9','A','B'};

// array of configurations
QLong *C;

// best result so far
int best = 0;

#define One ((QLong)1)

// stores the configurations in the current solution
QLong Qs[N];

// generates all the configurations of N queens and stores
// them in array C.

void GenConf()
{
  int a[N];
  int nC=0;
  
  void OutConf()
  {
    QLong t=0;
    for (int i=0; i<N; i++) t |= One << (i*N+a[i]);
    C[nC++]=t;
  }

  int Ok(int i)
  {
    for (int j=0; j<i && j<N; j++)
      if (a[i]==a[j] || abs(a[i]-a[j])==(i-j)) return 0;
    return 1;
  }
  
  void nxt(int k)
  {
    for (a[k]=0; a[k]<N; a[k]++)
      if (Ok(k)) { if (k==N-1) OutConf(); else nxt(k+1); }
  }

  // where the configurations are stored
  C = calloc(nConf[N],sizeof(QLong));
  // finds configuration recursively
  nxt(0);
  printf("nConf = %d\n",nC);
  if (nC != nConf[N]) exit(printf("Error %d != %d\n",nC,nConf[N]));
}

// prints the best solution so far from Qs[]
void PrQs()
{
  int A[N][N];
  for (int i=0; i<2*N; i++) printf("-");
  printf("\n");
  
  for (int i=0; i<N; i++)
    for (int j=0; j<N; j++) A[i][j]=0;

  for (int k=0; k<best; k++)
    for (int i=0; i<N; i++)
      for (int j=0; j<N; j++)
	A[i][j] |= (Qs[k] & (One<<(N*i+j)) ? k+1 : 0);
    
  for (int i=0; i<N; i++)
    {
      for (int j=0; j<N; j++)
	printf("%c ",S[A[i][j]]);
      printf("\n");
    }
}

// build a solution recursively.
// it tries to add a further configuration to the current set.
// if best so far, it prints it
// M contains the binary OR of all the configurations contained
// in the current set
int ric(QLong M, int p, int q)
{
  if (q>best) {best=q; PrQs(); if (q==N) return 1;}
  
  for (int i=p; i<nConf[N]; i++)
    if ((M & C[i])==0)
      {
	Qs[q]=C[i];
        if (ric(M|C[i],i+1,q+1)) return 1;
      }
  return 0;
}

int main()
{
  // creates the N-queen configurations  
  GenConf();

  // find solution
  ric(0,0,0);
  
  printf("\na(%d) = %d\n",N,best);
  return 0;

}