// Author: Manfred Scheucher
// Date  : 12.06.2015

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

#define MAXN 16
#define ATTACKS 1

int queenx[MAXN]; // x coordinate
int queeny[MAXN]; // y coordinate
int queena[MAXN][MAXN]; //  after i iterations queen j is attacked by queena[i][j] queens

char field[MAXN][MAXN];
char field1[MAXN][MAXN];
char field2[MAXN][MAXN];
  
long ct = 0;
int n,N;

inline int to_field()
{
  int x,y;
  
  for(y=0;y<n;y++)
  {
    for(x=0;x<n;x++)
    {
      field[x][y]='.';
    }
  }
  
  for(x=0;x<N;x++)
  {
    field[queenx[x]][queeny[x]]='X';
  }
}

inline int print()
{
  int x,y;
  
  to_field();
  
  for(y=0;y<n;y++)
  {
    for(x=0;x<n;x++)
    {
      printf("%c ",field[x][y]);
    }
    printf("\n");
  }
  printf("\n");
}

inline int flip()
{
  int x,y;
  for(y=0;y<n;y++)
  {
    for(x=0;x<n;x++)
    {
      field2[y][x] = field1[x][y];
    }
  }
}

inline int rot()
{
  int x,y;
  for(y=0;y<n;y++)
  {
    for(x=0;x<n;x++)
    {
      field2[n-1-y][x] = field1[x][y];
    }
  }
}

inline int cmp()
{
  int x,y;
  for(y=0;y<n;y++)
  {
    for(x=0;x<n;x++)
    {
      if(field[x][y] < field1[x][y]) return 1;
      if(field[x][y] > field1[x][y]) return 0;
    }
  }
  return 0;
}

inline int islexmin()
{
  to_field();
  memcpy(field1,field,MAXN*MAXN*sizeof(char));
  
  // rot 90
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // rot 180
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // rot 270
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // mirrored 0
  memcpy(field1,field,MAXN*MAXN*sizeof(char));
  flip();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // mirrored 90
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // mirrored 180
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  // mirrored 270
  rot();
  memcpy(field1,field2,MAXN*MAXN*sizeof(char));
  if(cmp()) return 0;
  
  return 1;
}

inline int valid(int k)
{
  int i, prev, dx, dy;

  queena[k][k] = 0;
  
  for(i=0;i<k;i++)
  {
    queena[k][i] = queena[k-1][i];
    
    dx = queenx[i]-queenx[k];
    dy = queeny[i]-queeny[k];
    if( dx == 0 || dy == 0 || dx == dy || dx == -dy)
    {
      queena[k][i]++;
      queena[k][k]++;
      if(queena[k][i]>ATTACKS || queena[k][k]>ATTACKS) return 0;
    }
    if(k==N-1 && queena[k][i]!=ATTACKS) return 0;
  }
  
  if(k==N-1 && queena[k][k]!=ATTACKS) return 0;
  
  return 1;
}

int place(int k)
{
  int x,y;
  if(k==N && islexmin())
  {
    ct++;
    print();
  }
  else
  {
    for(y=0;y<n;y++)
    {
      for(x=0;x<n;x++)
      {
        if(k>0 && (y<queeny[k-1] || (y==queeny[k-1] && x<=queenx[k-1]))) continue;
        
        queenx[k]=x;
        queeny[k]=y;
        if(!valid(k)) continue;
        place(k+1);
      }
    }
  }
}

int main(int argc,char** argv)
{
  n = atoi(argv[1]);
  N = 2*((2*n)/3);
  assert(n<MAXN);
  assert(N<MAXN);
  
  place(0);
  
  printf("%dx%d grid, %d queens, %ld solutions\n",n,n,N,ct);
  return 42;
}