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 {
    public List<String[]> solveNQueens(int n) {
        ArrayList<String[]> result=new ArrayList<String[]>();
        Integer []columns=new Integer[n];
        placeQueens(0,n,columns,result);
        return result;
    }
    //dfs
    public void placeQueens(int row,int n,Integer[] columns,ArrayList<String[]> result){
        if(row==n){
            String[] arr=new String[n];
            for(int i=0;i<n;i++){
                StringBuffer sb=new StringBuffer();
                for(int j=0;j<n;j++){
                    if(columns[i]==j) sb.append("Q");
                    else sb.append(".");
                }
                arr[i]=sb.toString();
            }
            result.add(arr);
        } else {
            for(int col=0;col<n;col++){
                if(isValid(columns,row,col)){
                    columns[row]=col;
                    placeQueens(row+1,n,columns,result);
                }
            }
        }
    }
    public boolean isValid(Integer[] columns,int row1,int column1){
        for(int row2=0;row2<row1;row2++){
            int column2=columns[row2];
            //check column
            if(column1==column2) return false;
            //check duijiaoxian
            int colDistance=Math.abs(column1-column2);
            int rowDistance=row1-row2;
            if(colDistance==rowDistance) return false;
        }
        return true;
    }
}