Problem description: Place eight queens on the chessboard. No two queens can attack each other (that is, no two queens are in the same row, column or diagonal) as shown in the picture.
In this article, slightly different solutions are used for the two problems, but both use one-dimensional arrays. In 6.20, it is required to find an effective layout. I created a one-bit array with eight elements. By randomly shuffling the values of the array, and comparing the value with the subscript, I finally get an effective layout; in 6.22, it is required Find all Effective layout, here I use octal numbers, traverse all the numbers from 001234567-076543210, convert them into octal strings, compare each bit with its subscript, and output the layout that meets the conditions. The implementation principles and methods will be introduced in detail below.
Part 1 How to judge whether it is a valid layout
We treat the chessboard as an 8*8 matrix, ranging from 0-7. Observing the picture on the left, you can find that its layout can be represented by a set of number pairs (from top to bottom), namely (0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2). Represented by an array, that is, int []list = {0, 6, 3, 5, 7, 1, 4, 2};
Clearly, this is a valid layout. Next we have to consider a question: In an effective layout, is there any relationship between the subscript and its corresponding value in the array, that is, i and list[i]?
Here we set list[i] = k; list[j] = q; (i > j), which satisfy the following two conditions (it is easier to understand when drawn on paper):
1. k != q;
2. i - j == k - q or i - j == q -k (obtained from the question)
In order to ensure that k != q, the array list is declared and initialized here such that list[i] = i. Then randomly shuffle the array, and then check whether condition 2 is met
Copy the code code as follows:
// Create and initialize the array
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
list[i] = i;
// Randomly shuffle the array
public static void randomizeArray(int [] list){
int arrSize = list.length;
int ranIndex;
for(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
if(ranIndex != i){
int temp = list[i];
list[i] = list[ranIndex];
list[ranIndex] = temp;
}
}
}
The code body of 6.20 is as follows
Copy the code code as follows:
// 6.20 Game: Eight Queens
public void solveEightQueens(){
int arrSize = 8;
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
list[i] = i;
int count = 0;
boolean notValid = true;
while(notValid){
count++;
notValid = false;
randomizeArray(list);
for(int i = 0; i < arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Check whether the condition is met
notValid = true;
break;
}
}
if(notValid) break;
} // end of outer for loop
} // end of while
// print the result
int i;
System.out.println("O(∩_∩)Ohaha~, I have tried " + count + " times, and eventually succeed.");
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
Part 2 Find all valid layouts
Since 6.22 requires finding all valid eight-queen layouts, the method of randomly shuffling the array is no longer applicable, so we have to find a method that can traverse all possible arrays. One of the most direct methods is to use an eight-layer for loop, but the amount of code is too large and the head is easy to faint, so this method is not used.
Carefully observing the values of the array in Part 1, you can find that they are all between 0-7, so traversing using octal int numbers can ensure that every permutation is included. Since the eight-digit numbers are different, there are 8! = 40320 possible permutations, and the total number of octal numbers is 8^8 = 16777216, so the possible ratio accounts for 40320/16777216 = 1/416, resulting in these 40320 permutations There are also checks to filter out the final valid layout. This method is still a bit inefficient, but I haven't figured out a more efficient one yet.
Copy the code code as follows:
// 6.22 Game: Various solutions to the eight queens problem (incrementing the int value, then converting it to an octal string, and then checking)
public static void solveEightQueensMethod(){
int start = 001234567; // Octal
int end = 076543210; // octal
int count = 0; // Calculate the number of valid layouts
for(int i = start; i < end; i++){
boolean isValid = isValid(i);
if(isValid){
if(++count % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Output the number of valid layouts
}
// Check if number is a valid layout
public static boolean isValid(int number){
String numOct = Integer.toOctalString(number);
int arrSize = numOct.length();
if(arrSize==7) { // If the first digit of number is 0, the generated string has only seven characters
numOct = '0' + numOct;
arrSize++;
}
for(int i = 1; i < arrSize; i ++){
for(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false; // same column
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false; //Same diagonal
}
}
return true;
}
Part 3 Extension: The problem of generating combinations
There was such a question in a written test last year. Given a sequence, output all combinations. for example,
Output of "123": 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Output of "abcd": a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., abcd, ...
In 6.22, the method used to find all the eight-queen layouts is to increment the int type number and then check one by one. The above problem can be solved in a similar way. However, the efficiency is a bit low. If there is a more efficient way, please ask an expert for guidance.