the analysis is here http://jznest.wordpress.com/2014/05/10/n-queens/

NQueens.java

import java.util.ArrayList;

public class NQueens {
	public ArrayList<String[]> solveNQueens(int n) {
		ArrayList<String[]> result = new ArrayList<String[]>();
		String[][] board = new String[n][n];
		int[][] boardStatus = new int[n][n];
		solveNQueens(result, board, boardStatus, 0, n);
		return result;
	}

	private void solveNQueens(ArrayList<String[]> result, String[][] board,
			int[][] boardStatus, int level, int n) {
		if (level == n) {
			result.add(getBoardString(board, n));
			return;
		}

		for (int i = 0; i < n; i++) {
			if (boardStatus[level][i] == 0) {
				board[level][i] = "Q";
				updateBoardStatus(level, i, boardStatus, n, false); // be sure to update the cell (level, i) correctly
				solveNQueens(result, board, boardStatus, level + 1, n);
				// undo
				board[level][i] = null;
				updateBoardStatus(level, i, boardStatus, n, true);
			}
		}
	}

	private void updateBoardStatus(int level, int i, int[][] boardStatus, int n, boolean isUndo) {
		int change = isUndo ? -1 : 1;
		int j = 0;
		while (j < n) {
			boardStatus[level][j] += change;
			boardStatus[j++][i] += change; // j++ on this row only!!! I made a mistake using j++ on both rows, stuipd me.
		}
		boardStatus[level][i] -= change; // we updated twice to this cell in the loop above so we need to correct it

		// update the cross
		int k = level;
		int m = i;
		while (--k >= 0 && --m >= 0) boardStatus[k][m] += change;

		k = level;
		m = i;
		while (++k < n && ++m < n) boardStatus[k][m] += change;

		k = level;
		m = i;
		while (++k < n && --m >= 0) boardStatus[k][m] += change;

		k = level;
		m = i;
		while (--k >= 0 && ++m < n) boardStatus[k][m] += change;
	}

	private String[] getBoardString(String[][] board, int n) {
		String[] boardStr = new String[n];
		for (int i = 0; i < n; i++) {
			StringBuilder builder = new StringBuilder();
			for (int j = 0; j < n; j++) {
				if (board[i][j] != null)
					builder.append("Q");
				else
					builder.append(".");
			}
			boardStr[i] = builder.toString();
		}
		return boardStr;
	}
}