LeetCode52-N皇后 II

public int totalNQueens(int n) {
        if (n < 1) return 1;
        //初始化数组
        queens = new int[n];
        cols = new boolean[n];
        left = new boolean[(n << 1) - 1];
        right = new boolean[left.length];
        place(0);
        return way;
    }

    //定义存储皇后位置的数组 索引为row 列为元素值
    int[] queens;
    //标记某一列是否有皇后
    boolean[] cols;
    //标记左斜线是否有皇后
    boolean[] left;
    //标记右斜线是否有皇后
    boolean[] right;
    int way;

    //在row位置放入皇后
    void place(int row) {
        if (row == queens.length) {
            //到这里说明摆放完成增加次数
            way++;
            return;
        }

        for (int col = 0; col < cols.length; col++) {
            if (cols[col]) continue;
            int leftIndex = row - col + cols.length - 1;
            if (left[leftIndex]) continue;
            int rightIndex = row + col;
            if (right[rightIndex]) continue;

            //说明所处的位置没有皇后
            //标记皇后
            queens[row] = col;

            //并且将当前所在的列 对角线都标记有皇后
            cols[col] = true;
            left[leftIndex] = true;
            right[rightIndex] = true;
            //进入下一行
            place(row + 1);
            //回溯
            cols[col] = false;
            left[leftIndex] = false;
            right[rightIndex] = false;
        }
    }