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