题目
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

image

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:

<pre style="box-sizing: border-box; overflow: auto; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; display: block; padding: 9.5px; margin: 0px 0px 10px; line-height: 1.42857; color: rgb(51, 51, 51); word-break: break-all; overflow-wrap: break-word; background-color: rgb(245, 245, 245); border: 1px solid rgb(204, 204, 204); border-radius: 4px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">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.</pre>

答案

public class Solution {
    public static List<String[]> solveNQueens(int n) {
        int[] place = new int[n];
        List<String[]> list= new ArrayList<String[]>();
        NQueens(list, place, 0, n);
        return list;
    }
    // k is for which row, the for loop below is for selecting a column
    public static void NQueens(List<String[]> list, int[] place, int k, int n) {
        for(int i = 0; i < n; i++) {
            // Can we place a queen on kth row???
            if(isValidPlacement(place, k, i)) {
                // Yes please do so
                place[k] = i;
                
                // k is the last row, add the chessboard
                if(k == n - 1) {
                    // convert place to String[]
                    list.add(array2ChessBoard(place));
                }
                else {
                    // not yet, keep trying
                    NQueens(list, place, k + 1, n);
                }
            }
        }
        
    }
    public static boolean isValidPlacement(int[] place, int k, int i) {
        for(int j = 0; j < k; j++) {
            // look at previous k rows, do they have the same column as i?
            if(place[j] == i)
                return false;
            // if not the same column, could it be on the same diagonal(row diff == col diff)
            if(Math.abs(j - k) == Math.abs(place[j] - i))
                return false;
        }
        return true;
    }
    public static String[] array2ChessBoard(int[] place) {
        int n = place.length;
        String[] board = new String[n];
        for(int i = 0; i < n; i++) {
            board[i] = "";
            for(int j = 0; j < n; j++) {
                char c = (place[i] == j)? 'Q':'.';
                board[i] = board[i] + c;
            }
        }
        return board;
    }
}