import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

public class Queens implements Runnable {
	private static final int defaultN = 5;
	private static volatile int n;
	private static AtomicLong count = new AtomicLong(0);

	public class Generator implements Runnable {
		private char[] x;

		public Generator(char k) {
			x = new char[n];
			x[0] = k;
		}

		void generate(int k) {
			for (char y = 1; y <= n; y++) {
				char q = 0;
				while (q < k && y != x[q] && Math.abs(k - q) != Math.abs(y - x[q]))
					q++;
				if (q == k) {
					x[k] = y;
					if (k == n - 1) {
						/*StringBuilder arr = new StringBuilder("");
						for (char i = 0; i < n; i++)
							arr.append((int) x[i] + " ");
						System.out.println(arr.toString());*/
						synchronized (count) {
							count.getAndIncrement();
						}
					} else
						generate(k + 1);
				}
			}
		}

		public void run() {
			generate(1);
		}
	}

	public static void main(String[] args) {
		try {
			n = Integer.parseInt(args[0]);
			if (args.length != 1 || n > 20 || n < 0)
				throw new Exception();
		} catch (Exception e) {
			System.err.println("Usage: Queens n");
			System.err.println("Default value of n(" + defaultN + ") used");
			n = defaultN;
		} finally {
			new Thread(new Queens()).start();
		}
	}

	public long solve(int newN) throws InterruptedException {
		n = newN;
		int processors = Runtime.getRuntime().availableProcessors();
		ExecutorService pool = Executors.newFixedThreadPool(processors);
		for (char i = 1; i <= n; i++) {
			pool.execute(new Generator(i));
		}
		pool.shutdown();
		if(pool.awaitTermination(20, TimeUnit.MINUTES)) {
			return count.get();
		} else {
			throw new InterruptedException("Time Limit Exceeded");
		}
	}

	public void run() {
		long start = System.currentTimeMillis();
		System.out.println("----------------------------");
		try {
			solve(n);
			System.out.println("----------------------------");
			long stop = System.currentTimeMillis();
			System.out.println("Total number of arrangements: " + count);
			System.out.println("Time elapsed: " + (stop - start)/1000.0 + " sec.");
		} catch (InterruptedException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}