N-Queens

Source

• 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.

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

[
  // Solution 1
  [".Q..",
   "...Q",
   "Q...",
   "..Q."
  ],
  // Solution 2
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."
  ]
]
Challenge
Can you do it without recursion?

Java

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<List<String>>();
        int[] cols = new int[n];
        dfs(n, 0, cols, result);
        return result;
    }

    public void dfs(int n, int row, int[] cols, List<List<String>>result){
        if(row==n){
            List<String> res = printResult(cols);
            result.add(res);
            return;
        }
        for(int col=0; col<n; col++){
            if(isValid(cols, row, col)){
                cols[row]=col;
                dfs(n, row+1, cols, result);
            }
        }
    }

    public boolean isValid(int[] cols, int row1, int col1){
        for(int row2=0; row2<row1; row2++){
            int col2=cols[row2];
            if(col2==col1 || Math.abs(col1-col2)==row1-row2){
                return false;
            }
        }
        return true;
    }

    public List<String> printResult(int[] cols){
        List<String> res = new ArrayList<String>();
        for(int row=0; row<cols.length; row++){
           StringBuilder sb = new StringBuilder();
           for(int col=0; col<cols.length-1; col++){
           //leave one space to insert later
               sb.append(".");
           }
           int index = cols[row];
           sb.insert(index, "Q");
           res.add(sb.toString());
        }
        return res;
    }
}