N-Queens

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

Given an integer n, 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.

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

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

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

Solution: Typical DFS question. We can maintain an array, whose index donates row number, and value donates column. It automatically gets rid of row duplicates. And then use DFS to try all possible solutions.

public class Solution {
    public ArrayList solveNQueens(int n) {
        ArrayList result = new ArrayList();
        if(n == 0) return result;
        
        int[] A = new int[n];
        dfs(A, 0, n, result);
        return result;
    }
    public void dfs(int[] A, int cur, int n, ArrayList result){
        if(cur == n){
            String[] strs = new String[n];
            for(int i = 0; i < n; i++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < n; j++){
                    if(j == A[i]){ sb.append('Q'); }
                    else sb.append('.');
                }
                strs[i] = sb.toString();
            }
            result.add(strs);
            return;
        }
        for(int i = 0; i < n; i++){
            A[cur] = i;
            if(isValid(A, cur)){
                dfs(A, cur+1, n, result);
            }
        }
    }
    public boolean isValid(int[] A, int cur){
        for(int i = 0; i < cur; i++){
            if(A[i] == A[cur]) return false;
            if(cur - i == Math.abs(A[cur] - A[i])) return false;
        }
        return true;
    }
}