<> 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

- Java407 articles
- Python218 articles
- Linux114 articles
- Vue106 articles
- MySQL91 articles
- SpringBoot70 articles
- javascript70 articles
- Spring63 articles
- more...

Daily Recommendation

©2019-2020 Toolsou All rights reserved,

Hikvision - Embedded software written test questions C Language application 0 The length of array in memory and structure is 0 In depth analysis data structure --- The preorder of binary tree , Middle order , Subsequent traversal How to do it ipad Transfer of medium and super large files to computer elementui Shuttle box el-transfer Display list content text too long 2019 The 10th Blue Bridge Cup C/C++ A Summary after the National Games （ Beijing Tourism summary ）unity Shooting games , Implementation of first person camera python of numpy Module detailed explanation and application case Study notes 【STM32】 Digital steering gear Horizontal and vertical linkage pan tilt Vue Used in Element Open for the first time el-dialog Solution for not getting element