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.

Have you met this question in a real interview? 

Yes

Example

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

[

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

     "...Q",

     "Q...",

     "..Q."],

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

     "Q...",

     "...Q",

     ".Q.."]

]

Challenge

Can you do it without recursion?

class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    ArrayList<ArrayList<String>> solveNQueens(int n) {
        // write your code here
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        dfs(n, 0, new int[n], res);
        return res;
    }
   
   
    private void dfs(int n, int start, int[] row, ArrayList<ArrayList<String>> res){
        if(n == start){
            res.add(generating(row, n));
            return;
        }
        for(int i = 0; i < n; i++){
            row[start] = i;
            boolean isValid = true;
            for(int j = 0; j < start; j++){
                if(row[j] == i || Math.abs(row[j] - row[start]) == start - j){
                    isValid = false;
                    break;
                }
             
            }
           
            if(isValid == true)
                dfs(n, start+1, row, res);
           
        }
    }
   
    private ArrayList<String> generating(int[] row, int n){
        ArrayList<String> res = new ArrayList<String>();
        for(int i = 0; i < n; i++){
            StringBuffer buffer = new StringBuffer();
            for(int j = 0; j < n; j++){
               
                if(row[i] == j){
                    buffer.append("Q");
                } else {
                    buffer.append(".");
                }
               
            }
            res.add(buffer.toString());
        }
        return res;
    }
       
       
};