N-Queens

The n-queens puzzle is the problem of placing n queens on ann×nchessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[
  // Solution 1
  [".Q..",
   "...Q",
   "Q...",
   "..Q."
  ],
  // Solution 2
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."
  ]
]

Solution: Backtracking.

public ArrayList<ArrayList<String>> solveNQueens(int n) {
    ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
    if(n <= 0) {
        return res;
    }
    int[] cols = new int[n];
    dfs(n, res, cols, 0);
    return res;
}
public void dfs(int n, ArrayList<ArrayList<String>> res, int[] col, int row) {
    if(row == n) {
        ArrayList<String> item = getResult(n, col);
        res.add(item);
        return ;
    }
    for(int i = 0; i < n; i++) {
        col[row] = i;
        if(isValid(col, row)) {
            dfs(n, res, col, row + 1);
        }
    }
}
public boolean isValid(int[] col, int row) {
    for(int i = 0; i < row; i++) {
        if(col[row] == col[i] || Math.abs(row - i) == Math.abs(col[row] - col[i])) {
            return false;
        }
    }
    return true;
}
public ArrayList<String> getResult(int n, int[] col) {
    ArrayList<String> res = new ArrayList<String>();
    for(int row = 0; row < n; row++) {
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < n; j++) {
            if(row == col[j]) {
                sb.append("Q");
            }
            else {
                sb.append(".");
            }
        }
        res.add(sb.toString());
    }
    return res;
}

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution: Declare a variable store the result.

public int totalNQueens(int n) {
    if(n <= 0) {
        return 0;
    }
    int[] cols = new int[n];
    int[] res = new int[1];
    dfs(n, res, cols, 0);
    return res[0];
}
public void dfs(int n, int[] res, int[] col, int row) {
    if(row == n) {
        res[0]++;
        return ;
    }
    for(int i = 0; i < n; i++) {
        col[row] = i;
        if(isValid(col, row)) {
            dfs(n, res, col, row + 1);
        }
    }
}
public boolean isValid(int[] col, int row) {
    for(int i = 0; i < row; i++) {
        if(i == row || col[row] == col[i] || Math.abs(row - i) == Math.abs(col[row] - col[i])) {
            return false;
        }
    }
    return true;
}