51. N-Queens

Then-queens puzzle is the problem of placingnqueens on ann×nchessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-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.."]
]

Analysis:

DFS.

Depth is n. At each level, try possible queen placement, use an array arr[] , arr[i] means at level i, where is the queen.

To verify if a position i at level y is valid to place a queen. Only need to check:

1. vertically if there is one above --> loop through 1 to current level y, arr[index] == i means there is one already.
2. diagonally, if there is one exist --> loop through 1 to current level y, Math.abs(arr[index] - i) == y - index, meaning there is one already. This is to calculate two node at the same line, they have the same 斜度.

Complexity:

Time: O(N^2)

Space:O(N)

Code:

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> returnList = new ArrayList<List<String>>();
        if(n < 4 && n!=1){
            return returnList;
        }
        dfs(0, n, new int[n], returnList);
        return returnList;
    }

    private void dfs(int level, int n, int[] arr, List<List<String>> returnList){
        if(level == n){
            printSolution(arr, returnList);
            return;
        }

        for(int i = 0; i < n; i++){
            if(noConflict(arr, level, i)){
                arr[level] = i;
                dfs(level+1, n, arr, returnList);
                arr[level] = 0;
            }
        }
    }

    private boolean noConflict(int[] arr, int x, int y){
        for(int i = 0; i < x; i++){
            if(arr[i] == y || Math.abs(arr[i]-y) == x-i){
                return false;
            }
        }
        return true;
    }

    private void printSolution(int[] a, List<List<String>> returnList){
        List<String> solution = new ArrayList<String>();
        for(int i = 0; i < a.length; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < a.length; j++){
                sb.append(a[i]==j?'Q':'.');
            }
            solution.add(sb.toString());
        }
        returnList.add(solution);
    }
}