LeetCode:N-Queens

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 {
    public ArrayList<String[]> solveNQueens(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        assert(n>=0);
        ArrayList<String[]> res = new  ArrayList<String[]>();
        solveNQueues(1, new int[n], res);
        return res;
    }
    
    public void solveNQueues(int k, int[] solu, ArrayList<String[]> res){
        int n= solu.length;
        main:
        for(int i=0;i<n;i++){
            for(int j=0;j<k-1;j++)
                if(solu[j]==i || Math.abs(solu[j]-i)==Math.abs(j-k+1)) continue main;   
            solu[k-1]=i;
            if(k==n){
                String[] temp = new String[n];
                for(int l=0;l<n;l++){
                    temp[l]=generateRow(n,solu[l]+1);
                }
                res.add(temp);
            }else
                solveNQueues(k+1,solu,res);
        }
    }
    
    public String generateRow(int n, int k){
        assert(k>0 && k<=n);
        StringBuilder res = new StringBuilder("");
        for(int i=0;i<k-1;i++){
            res.append(".");
        }
        res.append("Q");
        for(int i=k;i<n;i++){
            res.append(".");
        }
        return res.toString();
    }
}