public ArrayList<String[]> solveNQueensNew(int n) {
		// Start typing your Java solution below
		// DO NOT write main() function
		int[] res = new int[n];
		ArrayList<String[]> resArr = new ArrayList<String[]>();
		Arrays.fill(res, -1);
		int i = 0, j = 0;
		while (i >= 0) { // the ith row
			for (j = res[i] + 1; j < n; j++) { // the jth column
				if (valid(res, i, j)) {
					res[i] = j;
					break;
				}
			}
			if (j == n)
				res[i--] = -1; // fail, back trace
			else {
				if (i == n - 1) {
					resArr.add(print(res));
					res[i--] = -1;
				} else {
					i++;
				}
			}
		}
		return resArr;
	}