题解 | #N皇后问题#

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int sum = 0;
    // int vnum = 0;
    public int Nqueen (int n) {
        // write code here
        int[][] visit = new int[n][n];
        Stack<int []> stack = new Stack();
        dfs(n, stack, 0, 0, 0, 0);
        return sum;
    }
    public void dfs(int n, Stack<int []> stack, int num, int vnum, int x0, int y) {
        if (num == n) {
            sum ++;
            return ;
        }
        if (stack.size() < x0) {//一行必须至少放一个皇后，最后的皇后数量才能到n
        //无法放置n个满足条件的皇后
            return;//在到达边界前提前回归，可以节省时间
        }
        int x = 0;
        for (int i = x0; i < n; i++)//承接上一行，一行行的遍历
            for (int j = 0; j < n; j++) { //按列方向放置皇后，可能可以有多个不同的列选择，按列方向进行递归
                {
                    x = i;
                    y = j;
                    if (x < n && y < n  && x >= 0 && y >= 0) {
                        if (canPut(stack, x, y)) {
                            num ++;//计数
                            int[] pos = {x, y};
                            stack.push(pos);
                            dfs(n, stack, num, vnum,  x + 1, 0);
                            stack.pop();
                            num --;
                            // System.out.println("x2:" + x + "y2:" + y + "num" + num);
                        }
                    }
                }

            }
        //用for左右斜线无法回溯因为是过程性的,for可在终点回溯比如num=0,或在刚开始的转折的重赋值，但对转折点和终点的路径不好记录，路径中许多参数值都会有变化，到终点后也无法返回（沿路径）所以无法回溯。使用for和visit 0值矩阵一次置许多已访问值（1），可能会重复，递增访问总数边界不好确定，回溯也不好定位。
    }
    public Boolean canPut(Stack<int[]> stack, int x, int y) {
        boolean canPut = true;
        for (int i = 0; i < stack.size(); i++) {
            int[] pos = stack.get(i);
            //同行同列斜线有放皇后
            if (pos[0] == x || pos[1] == y || pos[0] - x == pos[1] - y ||
                    pos[0] - x == -1 * (pos[1] - y)) {
                canPut = false;
                break;
            }
        }
        return canPut;
    }
}