<> Problem description and requirements

According to the rules of chess , A queen can attack any other piece on the same row, column or slash . be n The requirements of the Queen's question are , In a n×n On the chessboard n A queen , So that no two Queens can be placed on the same row or column or on the same slash .

<> Principle of backtracking

The backtracking method can systematically search all or any solutions of a problem . It is in the solution space tree containing all problems , According to the depth first strategy , Searching solution space tree from root node . When the algorithm searches to any node of the solution space tree , Always judge whether the node does not contain the solution of the problem . If definitely not , The system search of the subtree with the node as the root is skipped , Go back to their ancestors layer by layer ; otherwise , Enter the subtree , Continue to search by depth first strategy .
When backtracking is used to find all solutions of a problem , Go back to the root , And all the subtrees of the root node have been searched ; When it is used to find any solution of the problem , As long as you find a solution to the problem, you can finish it .

<>n Queen problem solving process

Start with an empty chessboard , Put in the first place 1 Go to No m The rows have been placed correctly m A queen , Again in the second place m+1 Find the right place on the line to place the second one m+1 A queen , Until the third day n Line found the right place to place the second line n A queen , A solution is found . Change the second n The location of the line queen , Hope to get the next solution .
【 The solution of the problem is obtained by backtracking , So not according to the normal thinking, starting from the first queen to find a second solution 】

<> code implementation
/** Judge whether the queen can be placed in the leading position , That is, there is no conflict with the queen that has been placed */ int Place(int* Column,int index) { int i;
for(i=1;i<index;i++) { int Column_differ=abs(Column[index]-Column[i]);
// Gets the difference in the number of columns between the queen that has been placed before and the queen that will be placed int Row_differ=abs(index-i); // Gets the difference in the number of rows between the queen that has been placed before and the queen that will be placed
/* There are queens in the same column or slash as the queens to be placed , Then return 0, Indicates that it cannot be placed */ if(Column[i]==Column[index]||Column_differ
==Row_differ) { return 0; } } return 1; // No queen is in the same column or slash as the queen to be placed , Then return 1, Indicates that it can be placed }
void N_Queue(int n) { int Column_Num[n+1]; // The array element is the column of a queen int index=1;
// Queen's index , from 1 reach n int i; int answer_num=0; //n The number of solutions to Queen's problem /* Initialize array */ for(i=1;i<=n;i++) {
Column_Num[i]=0; } while(index>0) { Column_Num[index]++;// Place the queen
/* If the place to be placed is not suitable , Move the current queen to the next location , Until you find the right place */ while(Column_Num[index]<=n&&!Place(
Column_Num,index)) { Column_Num[index]++; } if(Column_Num[index]<=n) { if(index
==n) // When the last queen is placed successfully { answer_num++; // The solution of this problem +1 /* Remove the last queen from the chessboard
Make it unsatisfied in the next cycle Column_Num[index]<=n This condition , in order to index--, That is, back to the last queen To find the next solution */ for(i=1;i<=n;
i++) { Column_Num[index]++; } } else // If it hasn't been put to the last queen , Then continue to look for the position of the next queen { index++;
Column_Num[index]=0; } } else { index--; // The current queen cannot be placed , It goes back to the last queen } } }
remarks ：
1. The principle and code of backtracking method in this article refer to 《 Software designer course 》
2. This code does not output the number of solutions or solutions , You can join by yourself

Technology
Daily Recommendation