Violent recursion - detailed explanation of Queen n & how to optimize with bit operation

N Queen

N The Queen's question refers to N*N On my chessboard N A queen , Ask any two queens to be different 、 Different columns , It's not on the same slash . Given an integer n, return n How many kinds of postures does the queen have .n=1, return 1.n=2 or 3,2 The queen and 3 The Queen's problem can't be put in any way , return 0.n=8, return 92

N Queen game principles ：

• Can't be in the same line
• Can't be in the same column
• Cannot be on the same slash （ Neither left nor right slashes ）

Now let's analyze the problem ：

Put only one queen in a row at a time , Swing from left to right , Every line is like this . And write down the position of the queen . The following row count pendulum only avoids the problems of common columns and common slashes . If you find a violation of the rules in a certain line , Then go back to the previous line and put it again , Move the queen one position to the right , The number of subsequent lines is followed by recursion .

How to record the Queen's position , That is to record the coordinates of the queen （x,y）, Just use an array . such as recored[7]=13, On behalf of the 7 The queen of the line is in the 13 Column ;record[0]=3 On behalf of the 0 The queen of the line is in the 3 Column .

How to detect whether the queen conflicts , There is no need to consider the problem of sharing , Because at the beginning, we stipulated that only one should be placed in each line . Suppose there are two queens whose positions are as follows ：

(a,b) and (c,d)

Not listed together ：b != d

No common slash ：|a-c| != |b-d|

If i Come to the n That's ok , That means it's out of bounds , And the implicit condition is that the placement before it is effective , So you can return a placement result .

If you don't come to the first n That's ok , Explain that the queen can be placed in the current line , Then try all the columns on this row , See if it's related to 0~i-1 The queen of the line conflict . If there is no conflict , Just record the position of the queen in this line and recurse to the next line ; If there is a conflict, skip to the next column .

//  Try i All the columns on the row （0~n-1 Column ）
		//  If at present i Yes queen , Put it in the j Column ,
		//  Will not go with it （0~i-1 That's ok ） Queen conflict （ Do not share && Not listed together && Unfair slash ）
		//  Then put it in the first place j Columns can , Consider effective , Then go i+1 Row recursion 
		//  otherwise , Invalid , Put down a column 
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record The record is 0~i-1 The position of the row queen 
				record[i]=j;//  The first i The queen of the line is in the j Column 
				ans+=process1(i+1, record, n);
				//  Because the number of columns to be placed in each row is directly changed , So there is no need to restore the scene 
			}
		}

Complete code ：

package com.harrison.class12;

public class Code08_NQueens {
    
	// 0~i-1 The queen of the line is placed , Don't think about , And meet the requirements ： Do not share 、 Not listed together 、 No common slash 
	// i  It means that we have arrived at i Row queen 
	// record[0~i-1]  Store the arranged records 
	// record[0]=3 ->  The first 0 The queen of the line is placed in the first 3 Column 
	// n  How many lines are there in total （0~n-1 That's ok ）, If you come to n OK, it's out of bounds 
	//  stay [0~i-1] When the queen of the line is all set ,
	//  return i And how many effective ways to place the number of rows behind it （ The whole chessboard is set ）
	public static int process1(int i,int[] record,int n) {
    
		//  If i Come to the termination line , It indicates that the previous row number placement is effective ,
		//  Return to a reasonable arrangement 
		if(i==n) {
    
			return 1;
		}
		//  If i There is no end line , Then the current line can be placed 
		int ans=0;
		//  Try i All the columns on the row （0~n-1 Column ）
		//  If at present i Yes queen , Put it in the j Column ,
		//  Will not go with it （0~i-1 That's ok ） Queen conflict （ Do not share && Not listed together && Unfair slash ）
		//  Then put it in the first place j Columns can , Consider effective , Then go i+1 Row recursion 
		//  otherwise , Invalid , Put down a column 
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record The record is 0~i-1 The position of the row queen 
				record[i]=j;//  The first i The queen of the line is in the j Column 
				ans+=process1(i+1, record, n);
				//  Because the number of columns to be placed in each row is directly changed , So there is no need to restore the scene 
			}
		}
		return ans;
	}
	
	// record[0~i-1] The queen of needs to see , The first i The queen of the line doesn't need 
	//  Back to page i OK, the queen put it in the first j Whether the column is valid 
	public static boolean isValid(int[] record,int i,int j) {
    
		for(int k=0; k<i; k++) {
    // 0~i-1 The queen of a certain line , Suppose it's the k Yes queen 
			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 Yes queen   In which column 
		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");
	}
}

The above method is useful for solving N The queen problem is already the best in how to try , If we don't engage in scholarship , For work, try here , however ！！！ I wonder if you know that bit operation is much faster than ordinary operation ？ So we can also optimize the constant term , But notice ： The time complexity after optimization with bit operation is the same as before , It is only optimized in terms of constant terms , But such an optimization is still much faster , Please keep looking down .

We put N The column in the queen problem is imagined as a binary bit of a positive integer . What do you mean , such as ,8 The queen problem only uses the last eight bits ;9 The queen problem only uses the last nine bits ,,, By analogy . If there is a queen in which column , Set the binary bit to 1（ At first it was all 0）. in other words ,1 On behalf of the queen ,0 The representative didn't put .

such as 8 Queen , The queen is placed in the second column of the first row ,
So that is 01000000

Of course , stay Java Inside ,int It only accounts for 4 Byte integer , So there is only 32 Binary bits , therefore , In this way , No more than 32 A queen , Because I can't put it .

Be careful ： The following text descriptions are based on 8 The queen gives an example ！！！

that , How does the current bank know where to put the queen ？ Two main points , First of all , Is the current row listed with the queen of the line , second , The position where the left and right slashes of the queen running ahead , The current line cannot be placed .

therefore , Next, prepare three variables , Column restrictions columnLimit, Left slash limit leftLimit, Right slash limit rightLimit.

columnLimit：00000000
leftLimit：00000000
rightLimit：00000000

On the first line , There is no limit , Then you can put it anywhere .

If you put it on the 4 Column （ Subscript from 0 Start counting ）, Then the above three variables will become ：

columnLimit：00001000
leftLimit：00010000（columnLimit Move one bit to the left ）
rightLimit：00000100（columnLimit Move one to the right ）

ok, The first i The queen of the line is put away , So how do you know i+1 Which columns on the row can put queens ？

The result of the above three variables or operations together is the total limit ： Hypothesis number 1 i Xing di 4 Set the queen free （ Subscript from 0 Start counting ）,columnLimit | leftLimit |rightLimit The result is ：00011100, On behalf of the i+1 Line up 3、4、5 No more columns .

00001000
00010000
00000100
00011100

well , Then the current situation is 00011100, 0 The queen can also be placed in the position , So every position will try again .

Suppose again in the 1 A queen is listed (01000000), So for i+1 All right , The column limit at this time columnLimit Namely 01001000（ It used to be 00001000）, The left slash limit is 10100000, The right slash limit is 00100010. It is not only affected by the restrictions of the previous row , And affected by the left and right slashes of all previous lines .

Draw a picture for you to deepen your understanding ：

Then for i+1 The limit of the next line is The answer after the above three variables are done or calculated together ——11101010, Only the queen can be placed on the remaining three zeros .

01001000
10100000
00100010
11101010

After processing the three variables , Continue to play like this ...

Supplementary knowledge ： How to extract the rightmost of binary numbers 1, => int Ans=N&((~N)+1), Please refer to this article —— Use the properties of XOR operation to perform operations .

The complete code of the two methods ：

package com.harrison.class12;

public class Code08_NQueens {
    
	// 0~i-1 The queen of the line is placed , Don't think about , And meet the requirements ： Do not share 、 Not listed together 、 No common slash 
	// i  It means that we have arrived at i Row queen 
	// record[0~i-1]  Store the arranged records 
	// record[0]=3 ->  The first 0 The queen of the line is placed in the first 3 Column 
	// n  How many lines are there in total （0~n-1 That's ok ）, If you come to n OK, it's out of bounds 
	//  stay [0~i-1] When the queen of the line is all set ,
	//  return i And how many effective ways to place the number of rows behind it （ The whole chessboard is set ）
	public static int process1(int i,int[] record,int n) {
    
		//  If i Come to the termination line , It indicates that the previous row number placement is effective ,
		//  Return to a reasonable arrangement 
		if(i==n) {
    
			return 1;
		}
		//  If i There is no end line , Then the current line can be placed 
		int ans=0;
		//  Try i All the columns on the row （0~n-1 Column ）
		//  If at present i Yes queen , Put it in the j Column ,
		//  Will not go with it （0~i-1 That's ok ） Queen conflict （ Do not share && Not listed together && Unfair slash ）
		//  Then put it in the first place j Columns can , Consider effective , Then go i+1 Row recursion 
		//  otherwise , Invalid , Put down a column 
		for(int j=0; j<n; j++) {
    
			if(isValid(record, i, j)) {
    // record The record is 0~i-1 The position of the row queen 
				record[i]=j;//  The first i The queen of the line is in the j Column 
				ans+=process1(i+1, record, n);
				//  Because the number of columns to be placed in each row is directly changed , So there is no need to restore the scene 
			}
		}
		return ans;
	}
	
	// record[0~i-1] The queen of needs to see , The first i The queen of the line doesn't need 
	//  Back to page i OK, the queen put it in the first j Whether the column is valid 
	public static boolean isValid(int[] record,int i,int j) {
    
		for(int k=0; k<i; k++) {
    // 0~i-1 The queen of a certain line , Suppose it's the k Yes queen 
			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 Yes queen   In which column 
		return process1(0, record, n);
	}
	
	public static int nums2(int n) {
    
		if(n<1 || n>32) {
    
			return 0;
		}
		// n==8 limit Far right 8 individual 1, The rest are all 0
		// n==9 limit Far right 9 individual 1, The rest are all 0
		// n==32  Far right 32 All of them 1 ->  Decimal system -1
		// n!=32 1 Move left n Subtract one more digit 
		//  such as n==8 limit=100000000-00000001 -> 11111111
		int limit=n==32?-1:((1<<n)-1);
		//  At first 0 when , No restrictions 
		return process2(limit, 0, 0, 0);
	}
	
	// limit  Delimited the scale of the problem , Is a fixed parameter 
	public static int process2(int limit,int columnLimit,int leftLimit,int rightLimit) {
    
		if(columnLimit==limit) {
    // base case
			return 1;
		}
		// pos  The current line can be placed in the position of the queen  1： Can't put  0： It can be released 
		// (columnLimit | leftLimit | rightLimit )  General restrictions 
		//  Why  & limit
		// 1）~(columnLimit | leftLimit | rightLimit )  A lump on the left 0 It turns into 1 Will interfere with 
		// 2） The left slash limit will be out of bounds , The right slash will not 
		int pos=limit&(~(columnLimit | leftLimit | rightLimit ));
		int ans=0;
		int mostRightOne=0;
		//  Try pos Every one of them 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");
	}
}

The time complexity of both methods is O(N^N).
But after optimization with bit operation , Or is it visible to the naked eye .

Here are 13 Queen's test results ,

N The Queen's problem is more difficult , In particular, it is difficult to understand optimization with bit operations , Bloggers took pains to write this article and make a record , Because some interviewers may ask these classic questions .

Thank you for your support of three consecutive comments or likes ‍‍‍