n皇后问题_n 皇后问题(输出皇后列号)

LeetCode链接：https://leetcode.cn/problems/n-queens
解题思路：

• 从上到下一行一行的放置皇后
• setQueen()方法：从第一列开始遍历判断row行i列是否可以放皇后。第row行放置皇后之后在第row+1行放置。当row=n+1时说明n行已经放置了皇后，得到一组解。
• ckecked()方法:只需要判断当前列和对角线，列判断比较简单。左斜线和右斜线的规律是行列的和以及差相同。行不需要判断，因为是一行一行的放，当前行放置皇后之后就会立刻跳转下一行，进行check判断时当前行一定没有放皇后。
• 输出解集：每次生成一组解，都会有一个arr[]数组与之对应；arr[i]=j代表皇后在第i行的第j列，根据arr数组即可生成对应的一组解。

class Solution {
    ArrayList<List<String>> mLists=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        int[] arr=new int[n+1];
        setQueen(1, n, arr);
        return mLists;
    }
    public void setQueen(int row,int n,int[] arr){
        if (row==n+1) {
            mLists.add(generateBoard(arr, n));
            return;
        }
        for (int i = 1; i <=n; i++) {
            if(checked(row,i,arr)){
                arr[row]=i;
                setQueen(row+1, n, arr);
            }
        }
    }
    public boolean checked(int row,int col,int[] arr){
        for (int i = 1; i < row; i++) {
            if (col==arr[i] || arr[i]+i==row+col || i-arr[i]==row-col) {
                return false;
            }
        }
        return true;
    }
    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i+1]-1] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38