5.1 N queens

Assumptions: n > 0

Input: int n queens to be located

Output: List<List<integer>> ways of putting the n queens

Data structure: Use 1D array to present 2D array by using an int[] to present the list, where it's index = row # (w/in [0,n-1]), [index] = col #

Solution:

1. Restriction: cannot place 2 queens on the same col/row/diagonal → 1 queen each row

2. n levels in the recursion tree, each level consider placing one queen at current row

3. states: n at most

TC: Each level has one less position to consider n*(n-1)*(n-2)*...*1 = O(n!)

SC: n levels + array.length == n = O(n)

public List<List<Integer>> nQueens(int n) {
  List<List<Integer>> res = new ArrayList<>();
  List<Integer> cur = new ArrayList<>();
  helper(n, cur, res);
  return res;
}

private void helper(int n, List<Integer> cur, List<List<Integer>> {
  //base case
  if (cur.size() == n) {
    res.add(new ArrayList<>(cur));
    return;
  }

  for (int i = 0; i < n; i++) {
    if (valid(cur, i)) {
      cur.add(i);
      helper(n, cur, res);
      cur.remove(cur.size() - 1);
    }
  }
}

private boolean valid(List<Integer> cur, int col) {
  int row = cur.size();
  for (int i = 0; i < row; i++) {
    if (cur.get(i) == col || Math.abs(cur.get(i) - col) == row - i) {
      return false;
    }
  }
  return true;
}