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

void output_phase(int *d, int n, int **work) {
  int x, y;
  for (x = 0; x < n; x++)
    for (y = 0; y < n; y++)
      work[y][x] = 0;
  for (x = 0; x < n; x++)
    work[d[x]][x] = 1;
  for (y = 0; y < n; y++) {
    for (x = 0; x < n; x++)
      if (work[y][x])
        putchar('Q');
      else
        putchar('.');
    putchar('\n');
  }
  putchar('\n');
}

int noqueen(int *c, int x, int y, int n, int **work) { /* set y-pos for given x-pos */
  int i, tx, ty;
  if (x == 0)
    return 1;
  for (tx = 0; tx < n; tx++) /* clear work */
    for (ty = 0; ty < n; ty++)
      work[ty][tx] = 0;
  for (i = 0; i < x; i++)
    work[c[i]][i] = 1;  /* set y-pos for given x-pos */
  /* left-upper */
  tx = x; ty = y;
  while (tx >= 0 && ty >= 0) { tx--; ty--; }
  tx++; ty++;
  while (tx < x && ty < y) {
    if (work[ty][tx])
      return 0;
    tx++; ty++;
  }
  /* left-downer */
  tx = x; ty = y;
  while (tx >= 0 && ty < n) { tx--; ty++; }
  tx++; ty--;
  while (tx < x && ty > y) {
    if (work[ty][tx])
      return 0;
    tx++; ty--;
  }
  return 1;
}

void f(int p, int *a, int n, int **work) {
  static int counter = 0;
  int i;
  if (n == p) {
    printf("%d-%d\n", n, ++counter);
    output_phase(a + n, n, work);
  } else {
    int *b;
    if ((b = malloc(sizeof(int) * n * 2)) != 0) {
      for (i = 0; i < n; i++)
        if (a[i] < 0) {
          if (noqueen(a + n, p, i, n, work)) {
            memcpy(b, a, sizeof(int) * n * 2);
            b[i] = p;
            b[n + p] = i;
            f(p + 1, b, n, work);
          }
        }
      free(b);
    }
  }
}

int main(int argc, char *argv[]) {
  int *a, n, i, k;
  int **work;
  if (argc != 2) {
    printf("usage: %s <num>\n", argv[0]);
    return 1;
  }
  n = atoi(argv[1]);

  /* allocate work area */
  if ((work = malloc(sizeof(int *) * n)) != 0) {
    int k, r, ret;
    for (k = 0; k < n; k++) work[k] = 0;
    for (k = 0; k < n; k++)
      if ((work[k] = malloc(sizeof(int) * n)) == 0)
        break;
    if (k == n) {
/*----------*/
      /* start actual calcaulationg */
      if ((a = malloc(sizeof(int) * n * 2)) != 0) {
        for (i = 0; i < n; i++)
          a[i] = -1;
        f(0, a, n, work);
        free(a);
      }
/*----------*/
    }
    /* release work area */
    for (k = 0; k < n; k++)
      free(work[k]);
    free(work);
  }
  return 0;
}
/* end */

usage: /t <num>