Get all valid ways of putting N Queens on an N * N chessboard so that no two Queens threaten each other.

Assumptions

• N > 0

Return

• A list of ways of putting the N Queens
• Each way is represented by a list of the Queen's y index for x indices of 0 to (N - 1)

Example

N = 4, there are two ways of putting 4 queens:

[1, 3, 0, 2] --> the Queen on the first row is at y index 1, the Queen on the second row is at y index 3, the Queen on the third row is at y index 0 and the Queen on the fourth row is at y index 2.

[2, 0, 3, 1] --> the Queen on the first row is at y index 2, the Queen on the second row is at y index 0, the Queen on the third row is at y index 3 and the Queen on the fourth row is at y index 1.

Solution 1: 当前层放的queen与之前放的不在90°，45°，135°时，可以放在该位置

  public List<List<Integer>> nqueens(int n) {
    List<List<Integer>> ans = new ArrayList<>();
    helper(new ArrayList<Integer>(), ans, n);
    return ans;
  }
  private void helper(List<Integer> path, List<List<Integer>> ans, int n) {
    if (path.size() == n) {
      ans.add(new ArrayList(path));
    }
    //每一层都检查所有位置
    for (int i = 0; i < n; i++) {
      if (isValid(path, i)) {
        path.add(i);
        helper(path, ans, n);
        path.remove(path.size() - 1);
      }
    }
  }
  private boolean isValid(List<Integer> path, int column) {
  //column:该层要放的位置， row:已经放了的层数，path.get(i):之前层放的位置
    int row = path.size();
    for (int i = 0; i < row; i++) {
                 //90°              //45或135， x轴                   y轴              
      if (path.get(i) == column || Math.abs(path.get(i) - column) == row - i) {
        return false;
      }
    }
    return true;
  }

Solution 2: 用3个hashmap分别记录90°，45°，135°已放的queen，这样可以用O(1)的时间检查有效位置