Thinking back from the eight queens' question

One 、 Eight queens question

Eight queens is a classical backtracking problem , The title is that the eight queens , Put it in 8×8 On a chess board , bring No two Queens can be on the same line 、 On the same column and the same diagonal . The following figure shows the search of four queens .

The eight queens problem can be solved by the method of violence , The code is also very short ：

Code 1

for(solu[1] = 1; solu[1] <= 8; solu[1]++)
	for(solu[2] = 1; solu[2] <= 8; solu[2]++)
		for(solu[3] = 1; solu[3] <= 8; solu[3]++)
			for(solu[4] = 1; solu[4] <= 8; solu[4]++)
				for(solu[5] = 1; solu[5] <= 8; solu[5]++)
					for(solu[6] = 1; solu[6] <= 8; solu[6]++)
						for(solu[7] = 1; solu[7] <= 8; solu[7]++)
							for(solu[8] = 1; solu[8] <= 8; solu[8]++)
								if( No conflict )  output();

The code is easy to understand , But the problem is ：
1） This kind of writing is not desirable in itself , Because if there are many queens , There will be a lot of loop multiplicity here , Even if the number of queens is unknown , The program can't be written .

2） This kind of writing , Time complexity is extremely high （ If the first two queens are placed in the first column , Then the back 6 No matter how the empress is placed, it won't help . Although the backtracking method is still very complex , However, many unnecessary searches can be saved by pruning .

In order to solve the above problems , We propose backtracking , The core idea of backtracking is ：
1） If errors are found, correct them immediately , Like the one above , It is impossible for us to have two queens in the same row , If there is , Then reselect the location .

2） If a queen doesn't have any position in the line to put down （ In any case, it will conflict with the queen in front ）, Then we have reason to think that the queen in front of us put her in an unreasonable position , So go back to the previous queen and reposition , This is a retrospective .

Code 2

const int n = 8;
int solu[n+1];

bool NoConfilict(int k){
    
	for(int i = 1; i < k; i++)
		if(solu[i] == solu[k] || (k-i == abs(solu[i]-solu[k])))
			return false;
	return true;
}

void PlaceQueue(int k){
     // Place the second k A queen , Because it can't be on the same line , So the queen k Put it in the k That's ok 
    if(k == n+1) // If you have reached the n+1 That's ok , A correct solution is obtained 
		Print();
	else for(int i = 1; i <= n; i++){
    
		solu[k] = i;
		if(NoConfilict(k)) // The current queen does not conflict with the previous queen , Put down a queen , If you can't fit in this line , to flash back .
			PlaceQueue(k+1);
	}
}

Two 、 The total permutation problem

With the solution of the eight queens problem , In fact, it is easy to modify the problem into a full permutation , As shown below 1 2 3 A fully arranged chessboard . We can still imagine n×n A chessboard , If you don't consider conflict , The first i Line representation i The number can be 1-n All the numbers between , But because it's a full permutation , therefore i Previously selected number ,i And subsequent numbers cannot be repeated .

The way to define conflict here is different from the eight queens problem , As you can see, the conflict here is that the subsequent figures are different from the previous ones , How different ？ It's easy for you to find out , As long as they are not in the same column , by comparison , The conflict over the eight queens issue is even more severe , Therefore, we only need to delete the second half of the conflict determination method of the eight queens problem .

Code 3

bool NoConfilict(int k){
    
	for(int i = 1; i < k; i++)
		if(solu[i] == solu[k]) // Notice the change here 
			return false;
	return true;
}

However, it only needs a tag array to judge whether it is in the same column , So generally we have a more concise way of writing ：

Code 4

const int n=3;
int solu[n+1], visit[n+1];

void FillGrid(intk){
    
	if(k==n+1)
		Print();
	else for(inti=1;i<=n;i++){
    
		if(!visit[i]){
    
			solu[k]=i;
			visit[i]=1;
			FillGrid(k+1);
			visit[i]=0;
		}
	}
}

There are many solutions for full permutation , For example, lexicographic order 、 There are many methods such as neighborhood exchange , Readers can take part in combinatorics . Here is another common recursive full permutation algorithm , The code is very short , But it is not a well understood way of writing , As shown below ：

Code 5

void solve(int k,int n){
    
	  if(k==n+1)
		print(n);
	  else for(int i=k;i<=n;i++){
    
		swap(a[k],a[i]);
		solve(k+1, n);
		swap(a[k],a[i]);
	  }
}

We noticed the code 3 And code 4 in , We will traverse each line n A place , But in fact, each of our lines is not n You can choose any number , So can we define an interval for the next layer each time ？ If the first 1 The number is, of course n You can choose any number , The first 2 How about the number , Add... To 1 The number is selected as x after , So the first 2 Bits can only be selected 1~n In addition to x Numbers other than , Follow up , And so on . As shown in the figure below ：

The first full permutation ：1 2 3 4 5 5 6 7 8

A full permutation ：3 4 5 6 8 7 1 2
Note the exchange of each line , The first of each line is swapped with the purple box :

In fact, the above code 5 That's the idea , Read the code ：

solve（k,n） ： solve [k,n] The whole arrangement
for(int i=k;i<=n;i++) ： The first k The value range of bit is [k,n] All numbers between
swap(a[k],a[i]) ： The first k Bits are needed in turn [k,n] Number between , Therefore, the number of k Bits and subsequent bits are exchanged
solve(k+1,n)： The first k After the bit is determined , Naturally, we can consider k+1 position
swap(a[k],a[i]) ： We noticed that , There is also an exchange , This exchange is to restore the previously exchanged numbers , Make the next exchange unaffected .

Get one at a time [k,n] Permutation , In fact, it includes from k Position to the first n Bit n-k+1 Secondary exchange , But every time we go back , All previous exchanges have been exchanged back , Guaranteed to go back to k When ,[k,n] All the numbers between are exactly the same as the first sequence , This also makes the next time I use k Bit heel i+1 Bit exchange ,a[i+1] It can be put in correctly a[k] The location of , meanwhile a[k] Placed in a[i+1] The location of .

3、 ... and 、n Take... From each element m A combination of elements

After understanding the eight queens problem , In fact, many problems can be solved . such as Leetcode77 It can be solved through the idea of the eight queens problem . This topic requires 1~n Of n Of the elements , Seeking inclusion m All subsets of elements , The elements of each subset are required to be arranged incrementally .

Here we also think of a chessboard , The first element is the first queen , The number he can take 1~n-m+1, The second is ？2~n-m+2, And so on until we finish m Up to the number . It should be noted that , The first i The value of element should be taken from i-1 The next position of elements starts to take value . Every time a line is taken , The queen is desperate ,OK, Go back to the previous line .