L51. N-Queens

recursion divide conquer

Problem:

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.

• 上下左右对角线都没有duplicate

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution:

• time complexty is 2 to n. because we need to traverse n points, and each of point has two choice, put Q or not.

• space complexity is n square.

• put . to all the place in the board;

• use dfs function to put Q; in this function, i represents rowIndex

• is Valid to check all the position is valid to put Q or not;

• convertMatrix to make the board

public List<List<String>> NQueen(int n){
    List<List<String>> res = new ArrayList<>();
    if(n <= 0) return res;
    char[][] board = new char[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            board[i][j] = '.';         
        }
    }
    dfs(res, board, n, 0);
    return res;
}
private void dfs(List<List<String>> res, char[][] board, int n, int colIndex){
    if(colIndex == n){
        res.add(convertMatrix(board));
        return;
    }
    for(int i =0; i < n; i++){
        if(isValid(board, i, colIndex)){
            board[i][colIndex] = 'Q';
            dfs(res, board, n, colIndex+1);
            board[i][colIndex] = '.';
        }
    }
}
private boolean isValid(char[][] board, int x, int y){
    for(int i = 0; i < board.length; i++){
        for(int j = 0; j < y; j++){
            if(board[i][j] == 'Q' && (x == i || Math.abs(x-i) == Math.abs(y-j)))
            return false;
        }
    }
}
private List<String> convertMatrix(char[][] board){
    List<String> list = new ArrayList<>();
    for(int i = 0; i< board.length; i++){
        list.add(new String(board[i]));
    }
    return list;
}