One , Eight queens problem

Eight queens problem , An old and famous problem , It is a classic case of backtracking algorithm . The problem was solved by international chess player max · Bessel in 1848 Proposed in : stay 8*8 There are eight queens on the chessboard , So that they can't attack each other , That is, no two Queens can be in the same row , On the same column or slash , How many kinds of pendulum are there .

Two , Basic ideas

1, The first queen, first row, first column ;

2, The second cucumber is placed in the second row and column , Then judge whether or not OK, If not OK, Keep it in the second column , Third column , Put all the columns in turn , Find a suitable one ;

3, Continue with the third queen , Or the first column , Second column ..... Until the eighth queen can also be placed in a non conflict position , Even if a correct solution is found ;

4, When a correct solution is obtained , When the stack goes back to the previous stack , We'll start looking back , Soon to be the first queen , Put all the correct solutions in the first column , Get it all ;

5, Then go back and put the first queen in the second column , Continue the loop later 1,2,3,4 Steps for ;

Three , Code instance
package dataStructure.recursion; public class Queen8 { // Define a max How many queens are there int
max = 8; // Define array array, Save the result of the Queen's placement , such as arr = {0 , 4, 7, 5, 2, 6, 1, 3} int[]
array = new int[max]; static int count = 0; static int judgeCount = 0; public
static void main(String[] args) { // Test it , 8 Is the queen right Queen8 queen8 = new
Queen8(); queen8.check(0); System.out.printf(" All in all %d solution ", count);
System.out.printf(" Total number of conflicts %d second ", judgeCount); // 1.5w } // Write a method , Place the second n A queen
// Particular attention : check yes Every recursion , Enter into check All of them for(int i = 0; i < max; i++), So there will be backtracking private
void check(int n){ if(n == max) { //n = 8 , actually 8 The queen is put away print(); return; }
// Put in the queen in turn , And judge whether there is a conflict for (int i = 0; i < max; i++) { // Let's start with the current queen n , Put it at the end of the line 1 column
array[n] = i; // Judge when to place the second n Here comes the queen i Column time , Conflict if(judge(n)){ // Go on n+1 A queen , Start recursion check(n+1);
} // In case of conflict , We'll continue array[n] = i; It's going to be the third n A queen , Placed on the bank A position moved back } } // See when we place the second n A queen ,
Check whether the queen conflicts with the queen placed in front /** * * @param n Denotes the second n A queen * @return */ private boolean
judge(int n) { judgeCount++; for (int i = 0; i < n; i++) { // explain //1. array[i]
== array[n] Express judgment The first n Is the queen the same as the one in front n-1 The two queens are in the same column //2. Math.abs(n-i) == Math.abs(array[n]
- array[i]) To judge the second n Is the queen and the second i Is the queen on the same slash // n = 1 Place the second 2 column 1 n = 1 array[1] = 1 //
Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 //3.
Judge whether it is on the same line , No need ,n It's increasing every time if(array[i] == array[n] || Math.abs(n-i) ==
Math.abs(array[n] - array[i]) ) { return false; } } return true; }
// Write a method , The position of the queen can be output private void print() { count++; for (int i = 0; i <
array.length; i++) { System.out.print(array[i] + " "); } System.out.println();
} }
Four , console output

Verify it :

 

 

 

Technology
©2019-2020 Toolsou All rights reserved,
Bitcoin in ten years ,VDS Opportunity or fraud Don't annoy the panda with any cat !「 Kung Fu Panda 」20 It's the year of man 4 blood sort ( one ) bubble sort Random forest R Language implementation java Realize the function of grabbing red packets Python Basic knowledge and notes python To solve the problem of dictionary writing list in CSS architecture design Vue Common features ( one )2021 year 2 Monthly programmer salary statistics , average 15144 element