// queens.cpp non-attacking queens

// http://www.cs.wisc.edu/~plakal/javatraces/benchmarks.html

// Run! LIVE! On the Internet

#include <iostream.h>
#include <stdlib.h>

void queens(int);
void print();

int size, size2;
int *up, *down, *rows, *x;

int main(int argc, char* argv[])
{
  int i;
  if (argc < 2) {
    cout << "Enter size of board on command line." << endl;
    exit(1);
  }
  size = atoi(argv[1]);
  size2 = (2*size)-1;
  
  up = new int[size2];
  down = new int[size2];
  rows = new int[size];
  x = new int[size];
  
  for (i = 0; i < size2; i++) {
    up[i] = down[i] = 1;
  }
  for (i = 0; i < size; i++) {
    rows[i] = 1;
  }
  queens(0);
  return 0;
}

void queens(int c)
{
  int r;
  
  for (r = 0; r < size; r++) {
    if (rows[r] && up[r-c+size-1] && down[r+c]) {
      rows[r] = up[r-c+size-1] = down[r+c] = 0;
      x[c] = r;
      if (c == size-1) {
	print();
      } else {
	queens(c + 1);
      }
      rows[r] = up[r-c+size-1] = down[r+c] = 1;
    }
  }
}

void print()
{
  int k;
  for (k = 0; k < size; k++) {
    cout << x[k]+1 << " ";
  }
  cout << endl;
}