N皇后问题

public static int num1(int n) {
    if (n < 1) {
        return 0;
    }
    //record[i]的值表示第i 行的皇后放在第?列
    int[] record = new int[n];
    return process1(0, record, n);
}

/*
i:目前来到第i行
recortd:record[0 ... i-1]表示之前放好的皇后，例如record[0] = 7，代表0行皇后在7列位置
n:一共有多少行
返回值是一共有多少摆法
**/
public static int process1(int i, int[] record, int n) {
    if (i == n) { //来到终止行位置,前面n-1行位置确定后，最后一行一定只有一种
        return 1;
    }
    int res = 0;
    for (int j = 0; j < n; j++) {//j代表列，当前行在i行，尝试i行所有列
        //去试i行的每一列（j），有效就将j赋值给record[i]
        if (isValid(record, i, j)) {
		    record[i] = j;
        	res += process1(i+1, record, n);
        }
    }
    return res;
}


//和前 i-1 行皇后判断，本行皇后放在 i行 j列，是否有效
public static boolean isValid(int[] record, int i, int j) {
    for (int k = 0; k < i; k++) {//之前的某个皇后
        //j == record[k]判断共列
        //Math.abs(record[k] - j) == Math.abs(i - k)判断共斜线，行之差等于列之差
        if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k) ) {
            return false;
        }
    }
    return true;
}

public static int num2(int n) {
    if (n < 1 || n > 32) {
        return 0;
    }
    //获取一个二进制数，后n位是1
    int limit  = n == 32 ? -1 : (1 << n) - 1;
    return process2(limit, 0, 0, 0);
}


//colLim列的限制
//leftDiaLim 左斜线的限制
//rightDiaLim 右斜线的限制
public static int process2(int limit,
       int colLim,
       int leftDiaLim,
       int rightDiaLim) {
    
    if (colLim == limit) {//base case：列限制等于limit,皇后全部填入，找到了一种合理的
        return 1;
    }
    int mostRightOne = 0;
    //pos代表总限制，列限制，左限制，右限制先或，然后取反和limit与
    int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
    int res = 0;
    while (pos != 0) {
        //提取pos最右侧的1
        mostRightOne = pos & (~pos + 1);
        //除去最右侧的1
        pos = pos - mostRightOne;
        res += process2(limit, 
                   colLin | mostRightOne, 
                  (leftDiaLim | mostRightOne) << 1,
                  (rightDiaLim | mostRightOne) >> 1 );
    }
    return res;

}