public class NQ {
	boolean[][] bd; 
	int	size;
	String	head;
	int	totalCount;
	static	long st, et;

	NQ(int n) {
		size = n;
		bd = new boolean[n][n];
		head = "";
		totalCount = 0;

		for (int i = 0; i < n; i++) {
			head += "--";
		}
	}

	public void dump() {
		System.out.println("Count: " + totalCount);
		System.out.println(head);
		for (int i = 0; i < size ; i++) {
			String l = "";
			for (int j = 0; j < size; j++) {
				if ( bd[i][j]) {
					l += " O";
				} else {
					l += " -";
				}
			}
			System.out.println(l);
		}
	}

	private boolean isValidPos(int x,  int y) {
		int i, j0, j1, c;
		totalCount++;
		for (i = x-1, c = 1; i >= 0; i--, c++) {
			// hrizontal line check
			if (bd[i][y]){
				return false;
			}

			// diagonal1 check 
			j0 = y - c;
			if (j0 >= 0 && bd[i][j0]){
				return false;
			}

			// diagonal2 check
			j1 = y + c;
			if (j1 < size && bd[i][j1]){
				return false;
			}
		}
		return true;
	}

	private boolean checkPos(int x, int y) {
		int j;
		for ( j = y; j < size ; j++) {
			if (isValidPos(x, j)) {
				bd[x][j] = true;

				if (x + 1 >= size ) {
					dump();
					bd[x][j] = false;

					// if this returns true, it continues searching...
					return false;
				}

				if (!checkPos(x+1, 0)) {
					return false;
				}
				bd[x][j] = false;
			} 
		}
		return true;
	}

	public static void main(String[] argv) {
		int a = 8; // default

		for ( int i = 0; i < argv.length; i++) {
			if (argv[i].equals("-s")) {
				try {
					a = Integer.parseInt(argv[i+1]);
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}

		NQ eq = new NQ(a);
		System.out.println("Board Size = " + eq.bd.length);

		st = System.currentTimeMillis();
		eq.checkPos(0, 0);
		et = System.currentTimeMillis();
		String ept = Long.toString(et - st);
		System.out.println("Elapsed time (msec): " + ept);
	}
}