回溯之n皇后二进制

左程云n皇后

package com.zhang.reflection.面试.算法模版.回溯模版.棋盘;
import java.util.Scanner;
public class 状态N皇后 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(Num(n));
    }

    private static int Num(int n) {
        if(n<1||n>32){
            return 0;
        }
        //整个的限制
        int limit=n==32?-1:(1<<n)-1;
        return process(limit,0,0,0);
    }
    //limit：整个的限制
    //collim：列的限制
    //leftDiaLim：左斜线的限制
    //rightDiaLim：右斜线的限制
    private static int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if(colLim==limit){
            return 1;
        }
        int pos=limit & (~(colLim|leftDiaLim|rightDiaLim));
        int mostRightOne=0;
        int res=0;
        while(pos!=0){
            //取pos最右边的1 也可以写成pos&(-pos);
            mostRightOne=pos&(~pos+1);
            pos=pos-mostRightOne;
            res+=process(limit,colLim|mostRightOne,(leftDiaLim|mostRightOne)<<1,(rightDiaLim|mostRightOne)>>>1);
        }
        return res;
    }
}