[leedcode 51] 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.."]
]

public class Solution {
    List<List<String>> res;
    int A[];
    public List<List<String>> solveNQueens(int n) {
        //经典的DFS，
        //解题思想：借助一个数组储存当前的状态A[i]=j表示第i行，第j列有一个皇后"Q"
        //函数nqueens(int cur,int n),代表cur行之前的已经满足规则，需要从cur到n进行深搜
        //递归过程中，需要验证第cur行是否满足要求，满足要求的规则通过isvalid给出，必须保证前cur行的A[i]!=A[cur],并且不在一个对角线上
        //即，Math.abs(A[i]-A[cur])!=cur-i
        //递归的终止条件是cur==n,此时需要保存中间结果
        //Start: placeQueen(0,n)
        //if current ==n then print result
        //else
        //    for each place less than n,
        //place queen
        //if current state is valid, then place next queen place Queen(cur+1,n)
        //   end for
        //end else
        res=new ArrayList<List<String>>();
        A=new int[n];
        nqueens(0,n);
        return res;
    }
    public void nqueens(int cur,int n){
        if(cur==n) printQ(n);
        else{
            for(int i=0;i<n;i++){
                A[cur]=i;//注意，不需要删除，下次重新赋值
                if(isValid(cur))
                    nqueens(cur+1,n);
            }
        }
    }
    public  void printQ(int n){
        List<String>  ress=new ArrayList<String>();
        for(int i=0;i<n;i++){
            
            StringBuilder seq=new StringBuilder();
            for(int j=0;j<n;j++){
                if(A[i]==j)seq.append("Q");
                else seq.append(".");
            }
            ress.add(seq.toString());
        }
        res.add(ress);
    }
    public boolean isValid(int cur){
        for(int i=0;i<cur;i++){//注意i的范围！
            if(A[i]==A[cur]||Math.abs(A[i]-A[cur])==cur-i)
                    return false;
        }
        return true;
        
        
    }
}