/* gcc -O3 -Wl,"-static" nq-full.c -o nq */
/* 
 * Non-deterministic N-Queens solver by Joel Martin
 */

/* N must be at least 4 */
#define N 30
#define START_ATTACKS (N*(N-1))/2
#define OUT_SZ (N*2+2)*(N+2)+1

 /* Don't bother computing b,x or y the first time since they're known */
int a,b=START_ATTACKS,i,j,x=0,y=1,z;

/* output string */
char m[OUT_SZ];

/* Game board */
char l[N];

/* Swap rows l[x] and l[y] */
#define Swap z=l[y],l[y]=l[x],l[x]=z

/* 
 * Do the queens in rows l[i] and l[j] attack each other?
 * The variable s is "+" or "-" depending on which diagonal we want to test.
 */
#define Test(s) (l[i]==(l[j]s(i-j)))

main () {
  /* 
   * Fill our compute array with queens from upper left to lower right This
   * starting position has the property that queens do not share any rows or
   * columns with other queens. By swapping rows, this property is maintained.
   */
  for (i=0; i<N; i++) {
    l[i] = i+1;
  }

  /* Repeat until number of attacks (b) is 0 */
  for (;b;) {
    /* 
     * Swap two random rows, except the first time when we just swap the
     * pre-loaded x and y  (0 and 1) 
     */
    Swap;
    a=0;
    /* Calculate number of attacks (a) */
    for (i=0; i<N-1; i++) {
      for (j=i+1; j<N; j++) {
        if (Test(+)||Test(-)) {
          a++;
        }
      }
    }
    /* If worse layout, swap back, otherwise save count for next time */
    if (b<a) {
      Swap;
    } else {
      b=a;
    }
    /* 
     * Use (a) as a temporary and get two random rows using one rand() call.
     * I don't bother seeding the generator since it defaults to 0
     */
    a=rand();
    x=a%N;
    y=a%(N-1);
  }
  /* Generate the output string */
  for (i=0; i<N+2; i++) {
    for (j=0; j<N+1; j++) {
      if (i%(N+1)) {
        m[i*(N*2+2)+j*2] = '|';
      } else {
        m[i*(N*2+2)+j*2] = '+';
      }
      m[i*(N*2+2)+j*2+1]= '-';
    }
    m[i*(N*2+2)+(N*2+1)]= '\n';
    if (i%(N+1)) {
      m[i*(N*2+2)+l[i-1]*2-1]='Q';
    }
  }
  /* Print the output string */
  puts(m);
}