void solveNQueensDFS(int level, int n, ArrayList<String[]> res) {
		if (level == n) {
			// construct one solution
			String[] strs = new String[n];
			for (int i = 0; i < n; ++i) {
				String str = "";
				for (int j = 0; j < n; ++j) {
					if (board[i][j]) {
						str += "Q";
					} else {
						str += ".";
					}
				}
				strs[i] = str;
			}
			res.add(strs);
			return;
		}
		for (int i = 0; i < n; ++i) {
			if (safe(level, i, n)) {
				board[level][i] = true;
				solveNQueensDFS(level + 1, n, res);
				board[level][i] = false;
			}
		}
	}