p52

 

public class  {
    	

	public int totalNQueens(int n) {
		List<List<String>> ansArrayList = new ArrayList<List<String>>();

		if (n == 0)
			return 0;
		List<String> ways = new ArrayList<String>();
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			s.append('.');
		}
		for (int i = 0; i < n; i++) {
			ways.add(s.toString());
		}

		dfs(n, ansArrayList, ways, 0);
		return ansArrayList.size();
	}

	public void dfs(int n, List<List<String>> ansArrayList,
			List<String> ways, int row) {
		

		if (row == n) {
			List<String> aList = new ArrayList<String>();
			for (int i = 0; i < ways.size(); i++) {
				// System.out.println(ways.get(i));
				aList.add(ways.get(i));
			}

			ansArrayList.add(aList);

			return;
		}

		for (int j = 0; j < n; j++) {
			if (check(n, ways, row, j)) {
				StringBuilder s = new StringBuilder(ways.get(row));
				s.setCharAt(j, 'Q');
				ways.set(row, s.toString());
				dfs(n, ansArrayList, ways, row + 1);
				s.setCharAt(j, '.');
				ways.set(row, s.toString());
			}
		}
	}

	public boolean check(int n, List<String> ways, int r, int l) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < n; j++) {
				if (ways.get(i).charAt(j) == 'Q'
						&& (j == l || Math.abs(r - i) == Math.abs(l - j))) {
					return false;
				}
			}
		}
		return true;

	}
}