Java implementation eight queens problem sample sharing

Problem description: with eight queens on a chessboard, no two queens can attack each other (i.e. no two queens are on the same row, column, or diagonal) as shown in the figure

< img border = 0 id = theimg onclick = window. The open this. (SRC) SRC = "/ / files.jb51.net/file_images/article/201403/20140310164003.jpg? 2014210164152 ">  

In this article, we take a slightly different approach to both problems, but both use one-dimensional arrays. In 6.20, to find an effective layout, I set up a one-digit array with eight elements. By randomly scrambling the values of the array, and comparing the values with the subscripts, I got an effective layout. In 6.22, which requires all valid layouts, I used an octal number here, traversing  ; All the Numbers from 001234567-076543210, by converting them to an octal string, and comparing each with its index, output the layout that satisfies the condition. The implementation principle and method will be described in detail below.

Part 1 how do I determine if the layout is valid

We think of the checkerboard as an 8 by 8 matrix, ranging from 0 to 7. Observe the figure on the left, can be found that its layout can be represented with a set number of (from top to bottom), the (0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2). Int []list = {0, 6, 3, 5, 7, 1, 4, 2};

Obviously, this is a valid layout. Now we have to consider the following question: in an effective layout, does the index have anything to do with its corresponding value in the array, i.e., I, and list[I]?

Here we call that & cake;   The list [I] = k; The list [j] = q;     (I > J), they satisfy the following two conditions (which are easier to understand if drawn on paper) :

1, k! = q;

2, i-j == k-q      Or   I - j == q-k  (from the passage)

Just to be sure, k! = q, which declares and initializes the list of the array, making & PI;   The list [I] = I. Then you randomly shuffle the array, and then you check  ; Does that satisfy condition two

//Creates and initializes the array & NBSP;    
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
    list[i] = i;
//Randomly shuffled 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 for 6.20 is 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])){  //So let's see if we're satisfied
                        notValid = true; 
                        break;
                    }
                }
                if(notValid) break;
            }   // end of outer for loop
        }   // end of while

        // print the result
        int i;
        System.out.println("O( studying _ studying )O Ha ha ~, 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 finds all the valid layouts
Since 6.22 requires that all valid eight-queen layouts be found, the method of randomly shuffling the array is no longer applicable, so we have to find a method that can traverse all possible layouts. One of the most straightforward ways to do this is to use an eight-layer for loop, but this is not an option because of the amount of code and the tendency to get dizzy.

A closer look at the values of the array in Part 1 reveals that they are all between 0 and 7, so the octal int traversal ensures that each permutation is included. Since the eight digits vary, there are eight possible permutations! = 40,320, and the total number of octal is   8^8 = 16777216, therefore   Possible proportions   40320/16777216 = 1/416, the resulting 40320 permutations need to be checked before the final valid layout can be screened. It's still a little inefficient, but I haven't come up with anything more efficient yet.

//6.22 games: multiple solutions to the eight queens problem (increments the value of int, then converts it to an octal string, then checks)
    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);  //Outputs the number of valid layouts
    }
//Check that 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 number begins with 0, the resulting 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;   //The 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

In a written test last year, there was this question. Given a sequence, output all combinations. For instance,

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... , the abcd,...

In 6.22, all eight queen layouts are found by incrementing an int and checking one by one. The above problem can be solved in a similar way. But the efficiency is a bit low, if there is a more efficient way, for the master to give directions