暴力递归——N皇后详解 ＆＆ 如何用位运算进行优化

N皇后

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1。n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。n=8，返回92

N皇后游戏原则：

• 不能在同一行
• 不能在同一列
• 不能在同一条斜线上（左右斜线都不行）

现在我们来分析题目：

在一行上每次只摆一个皇后，从左往右开始摆，每一行都如此。并且记下这个皇后的位置。后续行数摆的时候只用避免共列和共斜线的问题。如果到某一行发现违反规则，那就退回上一行重新摆，将皇后右移一个位置，后续行数再接着递归。

如何记录皇后的位置，也就是记录皇后的坐标（x,y），只需要用一个数组既可。比如recored[7]=13，代表第7行的皇后在第13列；record[0]=3代表第0行的皇后在第3列。

如何检测皇后是否冲突，共行问题不用考虑，因为一开始我们就规定每一行都是只摆放一个。假设有两个皇后的位置如下：

(a,b) 和 (c,d)

不共列：b != d

不共斜线：|a-c| != |b-d|

如果i来到了第n行，那就说明越界了，并且隐含的条件是之前行的摆放都有效，所以可以返回一种摆放结果。

如果没有来到第n行，说明当前行可以摆放皇后，那么就尝试这一行上所有的列，看是否与0~i-1行的皇后冲突。 如果不冲突，就记录好这一行皇后的位置并且去下一行递归；如果冲突就跳到下一列。

// 尝试i行上所有的列（0~n-1列）
		// 如果当前i行的皇后，放在第j列，
		// 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线）
		// 那放第j列可以，认为有效，接着去i+1行递归
		// 否则，无效，放下一列
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record记录的是0~i-1行皇后的位置
				record[i]=j;// 第i行的皇后在第j列
				ans+=process1(i+1, record, n);
				// 因为在每一行都是直接改要放的列数，所以无需恢复现场
			}
		}

完整代码：

package com.harrison.class12;

public class Code08_NQueens {
    
	// 0~i-1行的皇后位置都摆放好了，不用再考虑，并且符合要求：不共行、不共列、不共斜线
	// i 表示当前来到第i行摆皇后
	// record[0~i-1] 存放摆好的记录
	// record[0]=3 -> 第0行皇后摆在第3列
	// n 表示一共有多少行（0~n-1行），如果来到n行就越界了
	// 在[0~i-1]行皇后都摆好的情况下，
	// 返回i及其后面行数摆放有效的方式有多少种（整个棋盘都摆好）
	public static int process1(int i,int[] record,int n) {
    
		// 如果i来到终止行，说明之前行数的摆放都有效，
		// 返回一种合理的摆放方式
		if(i==n) {
    
			return 1;
		}
		// 如果i没有到终止行，那么当前行可以摆
		int ans=0;
		// 尝试i行上所有的列（0~n-1列）
		// 如果当前i行的皇后，放在第j列，
		// 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线）
		// 那放第j列可以，认为有效，接着去i+1行递归
		// 否则，无效，放下一列
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record记录的是0~i-1行皇后的位置
				record[i]=j;// 第i行的皇后在第j列
				ans+=process1(i+1, record, n);
				// 因为在每一行都是直接改要放的列数，所以无需恢复现场
			}
		}
		return ans;
	}
	
	// record[0~i-1]的皇后需要看，第i行的皇后不需要
	// 返回第i行皇后放在了第j列是否有效
	public static boolean isValid(int[] record,int i,int j) {
    
		for(int k=0; k<i; k++) {
    // 0~i-1行的某一行的皇后，假设是第k行的皇后
			if(record[k]==j || (Math.abs(record[k]-j)==Math.abs(i-k))) {
    
				return false;
			}
		}
		return true;
	}
	
	public static int nums1(int n) {
    
		if(n<1) {
    
			return 0;
		}
		int[] record=new int[n];// record[i] i行的皇后 放在了第几列
		return process1(0, record, n);
	}
	
	public static void main(String[] args) {
    
		int n=8;
		long start=System.currentTimeMillis();
		System.out.println(nums1(n));
		long end=System.currentTimeMillis();
		System.out.println("cost time："+(end-start)+"ms");
	}
}

上面这种方法对于解决N皇后问题在如何尝试的方式上已经是最优的了，如果我们不去搞学术的话，对于工作尝试到这里就可以了，但是！！！不知道大家知不知道位运算是比普通运算快很多的呢？所以我们还可以在常数项方面优化一下，但是注意：用位运算优化后的时间复杂度还是跟原来一样，只是在常数项方面进行了优化，但这么一优化还是快了很多的，请接着往下看。

我们把N皇后问题中的列想象成一个正整数的二进制位。什么意思，比如，8皇后问题就只用最后面的八个二进制位；9皇后问题就只用最后面九个二进制位，，，依次类推。如果在哪一列放了皇后，就将该二进制位设为1（一开始全部为0）。也就是说，1代表放了皇后，0代表没有放。

比如8皇后，在第一行的第二列摆了皇后，
那么就是 01000000

当然，在Java里面，int是只占4个字节的整型，所以最多也只有32个二进制位，所以，用这种方式的话，不能超过32个皇后，因为摆不下。

注意：以下文字描述都是以8皇后举例子！！！

那么，当前行如何知道在哪该放皇后呢？主要看两点，第一，当前行是不是跟之前行的皇后共列，第二，之前行的皇后的左右斜线贯穿的位置，当前行不能放。

所以，接下来准备三个变量，列限制columnLimit，左斜线限制leftLimit，右斜线限制rightLimit。

columnLimit：00000000
leftLimit：00000000
rightLimit：00000000

在第一行的时候，是没有任何限制的，那就可以随便放。

假如放在第4列（下标从0开始算），那么上述三个变量就会变成：

columnLimit：00001000
leftLimit：00010000（columnLimit往左移一位）
rightLimit：00000100（columnLimit往右移一位）

ok，第i行上的皇后放好了，那么如何知道第i+1行上哪些列可以放皇后呢？

上述三个变量一起做或运算的结果就是总的限制：假设第i行第4列放了皇后（下标从0开始算），columnLimit | leftLimit |rightLimit 结果就是：00011100，代表第i+1行上第3、4、5列都不可以再放了。

00001000
00010000
00000100
00011100

好的，那么当前情况就是00011100， 0的位置还可以放皇后，所以每个位置都会去尝试一遍。

假设又在第1列放了个皇后(01000000)，那么对于i+1行来说，此时的列限制 columnLimit 就是 01001000（之前是00001000），左斜线限制就是 10100000，右斜线限制就是 00100010。不仅受上一行列限制的影响，而且受之前所有行延申的左右斜线的影响。

给大家画个图加深理解：

那接下来对于i+1行的下一行的限制就是 上面三个变量一起做或运算后的答案——11101010，只能在剩下的三个零上放皇后。

01001000
10100000
00100010
11101010

处理完三个变量后，继续往下这么玩。。。

补充知识：如何提取二进制数中最右侧的1， => int Ans=N&((~N)+1)，请参考这篇文章——利用异或运算的性质进行骚操作。

两种方法的完整代码：

package com.harrison.class12;

public class Code08_NQueens {
    
	// 0~i-1行的皇后位置都摆放好了，不用再考虑，并且符合要求：不共行、不共列、不共斜线
	// i 表示当前来到第i行摆皇后
	// record[0~i-1] 存放摆好的记录
	// record[0]=3 -> 第0行皇后摆在第3列
	// n 表示一共有多少行（0~n-1行），如果来到n行就越界了
	// 在[0~i-1]行皇后都摆好的情况下，
	// 返回i及其后面行数摆放有效的方式有多少种（整个棋盘都摆好）
	public static int process1(int i,int[] record,int n) {
    
		// 如果i来到终止行，说明之前行数的摆放都有效，
		// 返回一种合理的摆放方式
		if(i==n) {
    
			return 1;
		}
		// 如果i没有到终止行，那么当前行可以摆
		int ans=0;
		// 尝试i行上所有的列（0~n-1列）
		// 如果当前i行的皇后，放在第j列，
		// 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线）
		// 那放第j列可以，认为有效，接着去i+1行递归
		// 否则，无效，放下一列
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record记录的是0~i-1行皇后的位置
				record[i]=j;// 第i行的皇后在第j列
				ans+=process1(i+1, record, n);
				// 因为在每一行都是直接改要放的列数，所以无需恢复现场
			}
		}
		return ans;
	}
	
	// record[0~i-1]的皇后需要看，第i行的皇后不需要
	// 返回第i行皇后放在了第j列是否有效
	public static boolean isValid(int[] record,int i,int j) {
    
		for(int k=0; k<i; k++) {
    // 0~i-1行的某一行的皇后，假设是第k行的皇后
			if(record[k]==j || (Math.abs(record[k]-j)==Math.abs(i-k))) {
    
				return false;
			}
		}
		return true;
	}
	
	public static int nums1(int n) {
    
		if(n<1) {
    
			return 0;
		}
		int[] record=new int[n];// record[i] i行的皇后 放在了第几列
		return process1(0, record, n);
	}
	
	public static int nums2(int n) {
    
		if(n<1 || n>32) {
    
			return 0;
		}
		// n==8 limit最右边8个1，其余全是0
		// n==9 limit最右边9个1，其余全是0
		// n==32 最右边32位全是1 -> 十进制-1
		// n!=32 1左移n位再减一
		// 比如n==8 limit=100000000-00000001 -> 11111111
		int limit=n==32?-1:((1<<n)-1);
		// 一开始第0行的时候，没有任何限制
		return process2(limit, 0, 0, 0);
	}
	
	// limit 划定了问题的规模，是固定不变的参数
	public static int process2(int limit,int columnLimit,int leftLimit,int rightLimit) {
    
		if(columnLimit==limit) {
    // base case
			return 1;
		}
		// pos 当前行可以放皇后的位置 1：不能放 0：可以放
		// (columnLimit | leftLimit | rightLimit ) 总限制
		// 为什么要 & limit
		// 1）~(columnLimit | leftLimit | rightLimit ) 左侧的一坨0取反后变成1会干扰
		// 2）左斜线限制会越界，右斜线不会
		int pos=limit&(~(columnLimit | leftLimit | rightLimit ));
		int ans=0;
		int mostRightOne=0;
		// 尝试pos上的每一个1
		while(pos!=0) {
    
			mostRightOne=pos & ((~pos)+1);
			pos=pos-mostRightOne;
			ans+=process2(limit, 
						  columnLimit | mostRightOne,
						  (leftLimit | mostRightOne)<<1, 
						  (rightLimit | mostRightOne)>>>1);
		}
		return ans;
	}
	
	public static void main(String[] args) {
    
		int n=13;
		long start=System.currentTimeMillis();
		System.out.println(nums1(n));
		long end=System.currentTimeMillis();
		System.out.println("cost time："+(end-start)+"ms");
		
		start=System.currentTimeMillis();
		System.out.println(nums2(n));
		end=System.currentTimeMillis();
		System.out.println("cost time："+(end-start)+"ms");
	}
}

两种方法的时间复杂度都是O(N^N)。
但是用位运算优化后，还是肉眼可见的快。

以下是13皇后的测试结果，

N皇后问题比较难，尤其是用位运算优化比较难理解，博主费心写下这篇文章做个记录，因为有的面试官可能会问到这些经典的问题。

感谢您的三连或点赞评论支持‍‍‍