leetcode52. N皇后 II 最强解法直接秒杀100%

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

思路：详见：皇后问题详细解释。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
	public int totalNQueens(int n) {
     
    
   

    

     

    
    

     
		// 因为本方法中位运算的载体是int型变量，所以该方法只能算1~32皇后问题
     
    
   

    

     

    
    

     
		// 如果想计算更多的皇后问题，需使用包含更多位的变量
     
    
   

    

     

    
    

     
		if (n < 1 || n > 32) {
     
    
   

    

     

    
    

     
			return 0;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int upperLim = n == 32 ? -1 : (1 << n) - 1;
     
    
   

    

     

    
    

     
 //upperLim的作用为棋盘大小，比如8皇后为00000000 00000000 00000000 11111111
     
    
   

    

     

    
    

     
 //32皇后为11111111 11111111 11111111 11111111
     
    
   

    

     

    
    

     
		return process2(upperLim, 0, 0, 0);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	public int process2(int upperLim, int colLim, int leftDiaLim,
     
    
   

    

     

    
    

     
			int rightDiaLim) {
     
    
   

    

     

    
    

     
		if (colLim == upperLim) {
     
    
   

    

     

    
    

     
			return 1;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int pos = 0; //pos：所有的合法位置
     
    
   

    

     

    
    

     
		int mostRightOne = 0;   //所有合法位置的最右位置
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //所有记录按位或之后取反，并与全1按位与，得出所有合法位置
     
    
   

    

     

    
    

     

      		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
     
    
   

    

     

    
    

     
		int res = 0;//计数
     
    
   

    

     

    
    

     
		while (pos != 0) {
     
    
   

    

     

    
    

     

      			mostRightOne = pos & (~pos + 1);//取最右的合法位置
     
    
   

    

     

    
    

     

      			pos = pos - mostRightOne; //去掉本位置并尝试
     
    
   

    

     

    
    

     

      			res += process2(
     
    
   

    

     

    
    

     

       upperLim, //全局
     
    
   

    

     

    
    

     

       colLim | mostRightOne, //列记录
     
    
   

    

     

    
    

     
 //之前列+本位置
     
    
   

    

     

    
    

     

       (leftDiaLim | mostRightOne) << 1, //左斜线记录
     
    
   

    

     

    
    

     
 //（左斜线变量+本位置）左移 
     
    
   

    

     

    
    

     

       (rightDiaLim | mostRightOne) >>> 1);   //右斜线记录
     
    
   

    

     

    
    

     
 //（右斜线变量+本位置）右移（高位补零）
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return res;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104126778