题解 | #N皇后问题#

容易看懂的解法：要把所有的皇后都摆满，就要从上到下一个个把皇后填入棋盘。那么我们直接开辟一个boolean[][] board数组来模拟皇后所存放的位置，每一个格子都尝试放置皇后即可。在放皇后之后，需要注意的是，皇后所在的行，列，撇，捺4个方向都不能放置新的皇后。那么看起来就要使用某个机制来记住这四个方向。可以考虑把棋盘当成朝下的直角坐标系（x,y)，撇方向由一次函数y=-x+b决定，那么在某个点已经放置了皇后的情况下，移项就有y+x=b,则撇方向直接可以由y+x确定。同理，捺方向可以由y=x+c决定，因此撇捺两个方向可以由两个整数，y+x,y-x记录。用set存放即可。此外，由于每一行放置了皇后就直接跳入下一层，因此可以不用记录行。每一层遍历之后，需要清除摆放皇后的限制(清除4个方向）。

public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int n;
    int count;
    Set<Integer> col = new HashSet<>();
    Set<Integer> mainDiagonal = new HashSet<>();
    Set<Integer> subDiagonal = new HashSet<>();
    public int Nqueen (int n) {
        // write code here
        this.n = n;
        boolean board[][] = new boolean[n][n];
        func(0,board);
        return count;
    }
    public void func(int index,boolean[][]board){
        if(index==n){
            count++;
            return;
        }
        for(int i=0;i<n;++i){
            if(col.contains(i)||mainDiagonal.contains(index+i)||subDiagonal.contains(index-i))continue;
            col.add(i);
            mainDiagonal.add(index+i);
            subDiagonal.add(index-i);
            board[index][i] = true;
            func(index+1,board);
            board[index][i] = false;
            col.remove(i);
            mainDiagonal.remove(index+i);
            subDiagonal.remove(index-i);
        }
    }
}