NQueen.java

package com.letsdecode.problems.recursion;

import java.util.ArrayList;
import java.util.List;

public class NQueeen {
	int n;
	boolean[][] a;
	boolean truth[];
	List<List<String>> list = new ArrayList<>();

	public NQueeen(int n) {
		this.n = n;
		a = new boolean[n][n];
		truth = new boolean[n];
	}

	public void call() {
		generate();
	}

	public List<List<String>> getResult() {
		return list;
	}

	private void generate() {
		for (int j = 0; j < n; j++) {
			truth[j] = true;
			a[0][j] = true;
			subGenerate(a, 1, j);
			a[0][j] = false;
			truth[j] = false;
		}
	}

	private void subGenerate(boolean[][] a, int i, int j) {
		if (i >= n) {
			// found
			print(a);
			return;
		}

		for (int k = 0; k < j - 1; k++) {
			if (truth[k] == false) {
				truth[k] = true;
				a[i][k] = true;
				subGenerate(a, i + 1, k);
				a[i][k] = false;
				truth[k] = false;
			}
		}

		for (int k = j + 2; k < n; k++) {
			if (truth[k] == false) {
				truth[k] = true;
				a[i][k] = true;
				subGenerate(a, i + 1, k);
				a[i][k] = false;
				truth[k] = false;
			}
		}
	}

	private void print(boolean[][] a) {
		ArrayList<String> l = new ArrayList<>();

		for (int i = 0; i < a.length; i++) {
			StringBuilder sb = new StringBuilder();
			for (int j = 0; j < a.length; j++) {
				if (a[i][j]) {
					sb.append("Q");
				} else {
					sb.append(".");
				}

			}
			l.add(sb.toString());
		}
		list.add(l);
	}

}


===============================
NQueenTest.java

public class NQueeenTest {
	@Test
	public void test() {
		long cu = System.currentTimeMillis();
		System.out.println(cu);
		NQueeen nQueeen = new NQueeen(6);
		nQueeen.call();
		System.out.println(System.currentTimeMillis() - cu);
	}
}