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

解题思路：

1.与N-Queens 2的思路一致，不过此题需要额外多的变量来记录所有的解。 

Java Code:

 public List solveNQueens(int n) {
        List res = new ArrayList();
        int[] solution = new int[n];
    
        String[] curr = new String[n];
        Nqueen1(1, solution, curr, res);
        return res;
    }
    
    public void Nqueen1(int level, int[] solution, String[] curr, List res){
        
        if(level == solution.length + 1){
            res.add(Arrays.copyOf(curr, level-1));
            return;
        }
        
        for(int i = 1; i <= solution.length; i++){
            int slop0 = Math.abs(i - level);
            
                int j = 0; 
                while(j < level && solution[j] != i && Math.abs(j + 1- level) != Math.abs(solution[j] - i)){
                    j++;
                }
                
                if(j == level){
                    String tmp = "";
                    
                    for(int t = 1; t <= solution.length; t++){
                        if(t==i) tmp += "Q";
                        else tmp += ".";
                    }
                    
                   
                    solution[level-1] = i;
                    curr[level-1] = tmp;
                    Nqueen1(level + 1, solution, curr, res);
                    solution[level - 1] = 0;
                    curr[level - 1] = ""; 
                }
         }
    }