4. N queen problem

▲ In graph theory , There are two ways to traverse a tree: breadth first and depth first
Breadth first traversal (BFS): Starting from an un traversed node of the graph First traverse the adjacent nodes of this knot Then traverse the adjacent nodes of each adjacent node in turn ( That is, traverse layer by layer )
Such as :

Depth-first traversal (DFS): From an unreachable vertex in the graph V Start Go all the way to the end Then go back from the node at the end of the road to the previous node Start from another road to the end Keep repeating the process Until all the points are traversed
Such as :

From the root node 1 Start , The adjacent nodes have 2、3、4. Traverse the node first 2, Then traverse down the node 5 and 9((1) The process ). The current node 9 No child node . At this point, start from the node 9 Back to the previous node 5, Judge node 5 Is there anything else besides 9 Other nodes , Didn't go back to 2,2 It's not except 5 Other nodes , Back to 1,1 Division 2 Other nodes 3, So from the node 3 Start depth first traversal ( Start (2) The process ). And so on , Until the end of the traversal .
Usually, non recursive method is used DFS: With the help of stack structure , Put the root node on the stack , The right node of its child node is put on the stack , Then the left node of the root node is put on the stack .
Such as : First traverse the depth of the following binary tree

Root node A Push ,A Out of the stack ,C、B Push ,B Out of the stack ,E、D Push 、D Out of the stack ,E Out of the stack ,C Out of the stack ,G、F Push ,F Out of the stack ,G Out of the stack .(A B D E C F G)

Serial number	Stack	result
1	A
2		A
3	C B	A
4		A B
5	C E D	A B
6	C	A B D E
7		A B D E C
8	G F	A B D E C
9		A B D E C F G

▲ Space state tree : Describe the tree structure of the solution space
Each node in the tree is called a Problem status
The path from the root to a state in the tree represents a tuple as a candidate solution, which is called the tuple of the state Solution state
The path from the root to a solution state is Feasible solution The tuple of is called the solution state is Answer status
▲ Of the pruning function depth The solution method of the nodes in the state space tree generated first is called backtracking method . In layman's terms , Backtracking is the process of traversal ," feel " When the original choice is not excellent or the goal cannot be reached " come back " Go to the previous step and reselect
Breadth Nodes generated first The method of using pruning function is called branch and bound method
*n queens problem :n×n On the chessboard n A queen , Make it Any two are not in the same row, the same column and the same slash
analysis : Because every queen should not be on the same line , Without losing generality , Suppose that i The queen is in the second place i That's ok (0≤i<n), set up queen[i] For the first time i The number of columns in which the row queen is located . It is easy to know that the implicit constraint condition is ∀i,j∈[0,n),i≠j( Different lines ),queen[i]≠queen[j]( Different columns ),|i-j|≠|queen[i]-queen[j]|( Different slashes )

#include <iostream>
#include <cmath>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
const int maxn=16;// ceiling ( You can change it yourself )
int queen[maxn],sum=0;
// Define global variables sum Table number of feasible solutions  queen[i] Number of feasible columns in the table  
void display(int* queen,int n){
    
	for(int i=0;i<n;i++){
    
		cout<<"("<<i<<" "<<queen[i]<<")";
	}
	cout<<endl;
	sum++;
}
bool check(int cur){
    
	for(int i=0;i<cur;i++){
    // From 0 Line starts down   Therefore, the constraints of different lines are not required  
		if(queen[i]==queen[cur]||abs(i-cur)==abs(queen[i]-queen[cur]))// constraint condition : Different columns have different slashes  
			return false;
	}
	return true;
}
void dfs(int cur,int n){
    //cur Is the current number of traversal layers ( Row number ) 
	if(n<=0||n>maxn){
    // Illegal or cross-border situations  
		return;
	}
	if(cur==n){
    // Traverse to the last layer   Direct output  
		display(queen,n);
	}
	else{
    
		for(int i=0;i<n;i++){
    
			queen[cur]=i;
			if(check(cur))// If the constraints are met   Continue to the next level  
				dfs(cur+1,n);
		}
	}
}
int main(int argc, char** argv) {
    
	int n;
	cin>>n;
	dfs(0,n);
	cout<<"The total of "<<n<<" Queen's solutions:"<<sum;
	return 0;
}

When n=8 The result is :

repair :《 Algorithm design and analysis 》 Chenhuinan Edition n Queen problem code :

#include <iostream>
#include <cmath>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
#define N 4 //4 Queen problem code ( Changeable ) 
int x[N];
bool Place(int k,int i,int* x){
    // Determine whether two queens are in the same column or on the same slash 
	for(int j=0;j<k;j++){
    
		if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))// constraint condition : Different columns have different slashes  
			return false;
	}
	return true;
}
void NQueens(int k,int* x){
    // Recursive function solving n queens problem 
	for(int i=0;i<N;i++){
    // Try the number of all optional Columns  
		if(Place(k,i,x)){
    // Meet the constraints  
			x[k]=i;
			if(k==N-1){
    // The last line succeeded   Output column  
				for(int j=0;j<N;j++)
					cout<<x[j]<<" ";
				cout<<endl; 
			}
			else// Continue to traverse downward without traversing to the last line  
				NQueens(k+1,x);
		}
	}
}
int main(int argc, char** argv) {
    
	NQueens(0,x);
	return 0;
}