The problem

Eight queens problem refers to the 8 * 8 on the chessboard of put in eight queen, and ensure that in each row, every column, and diagonal will appear at the same time two queen (inside of the rules of chess, the queen’s attack range is in its place the relation of two lines and two diagonals), so how to put the eight queens? How many ways are there?

Train of thought

The first way to think about it is, there are 64 squares on an 8 by 8 board, and now we’re going to put 8 queens into those 64 squares, which is the number of combinations in math, and then from these combinations to choose the right way to put. It’s the right thing to do, butThe calculation result of this combination number is too large, there are a total of 4426165368 combinations, the calculation amount is too large.

Second, since each queen can’t be in the same row or column, we can randomly select a row when we add the first queen. We have 8 choices. When we put in the second emperor, we definitely can’t put it in the same row and column as the first queen, so we only have 7 choices; And then we put in the third queen, and again, there are only six choices; And by the time we add the eighth queen, there’s only one choice. So this way of thinking, we have 8 factorial choices, 40,320 choices, and from those 40,000 choices we can choose which way to put it, so it looks like 40,000 is a lot smaller than 4.4 billion, which is a pretty good solution.

Idea 3: on the basis of the second thought, we at the time of queen in the second, only consider the different columns, and the first empress not counterparts, without considering the diagonal, so think when put into the third queen seven selected, that if we put the diagonal problem into consideration, the second the queen’s choice is a bit less. Similarly, when put the third queen, we put the front two queen diagonally into consideration, the queen’s choice to have a third, and so on, to put a queen, 8 choice would be much less, even in the fifth, sixth, came without any choice can choose, is dead. On the whole, the number of combinations must be far less than the 40,000 combinations of the second way of thinking.

On the third line of thought, what if we hit a dead end? If we put the fifth queen, no matter how to put the fifth queen, will not meet the requirements, this time shows that there is a problem with the placement of the first four queens. So what? We can go back to step 4, change the placement of the fourth queen, and then continue to try to place the fifth queen. If the fifth queen still cannot be placed, go back to step 4 and change the position of the fourth queen. If the fourth queen can place all tried, the fifth queen still has no place to put, that time indicates that the position of the third queen is out of question, so go back to the third step, if there is still a dead end, then back in turn, until you find the right way to place.

Familiar with data structure and algorithm of the classmates will think of this time, this line of thinking is back in the mind, begin with a road, a road to black, come to a dead end, go back to the previous intersection (back), starting from another direction again, and come to a dead end, back again he had just been crossing, until all the fork traveled in the intersection, If it still doesn’t work, keep going backwards, back to the previous intersection, until you find your way out.

The idea of backtracking is simple, but how does the code implement it? The most common way to achieve backtracking is to use recursion. The following uses the backtracking idea and uses recursive code to achieve the placement of the above 8 queens.

Backtracking code implementation

First we define an array of length 8: int[] result, where each queen is placed. The subscript of the array indicates the row in which the queen is placed, and the value of the element indicates the row in which the queen is placed. For example, result[0] = 4 indicates that the queen in row 0 is placed in column 4.

PutQueen (row); putQueen(row); putQueen(row); putQueen(row); putQueen(row);

// Use an array to store the position of the queen in each row. The subscript of the array indicates the row, and the value of the element indicates the position of the queen in the row

public int[] result = new int[8];



/ * *

* Put the queen in the first row, which starts at 0

 * @paramWhich row row

* /

public void putQueen(int row) {

    if (row == 8) {   // If it equals 8, it means that all the 8 queens have been placed

        printQueen();   / / print

        return;

    }

    for (int column = 0; column < 8; column++) {    // Try placing queens in columns 0-7, respectively

        if (isAccessible(row, column)) {   // Before placing the queen on the board, determine whether the queen can be placed there

            result[row] = column;   // Add queen

            putQueen(row + 1);    // Put the queen in the next line

        }

    }

}

Copy the code

Before placing a queen in a column of a row, we need to determine whether the row or column is within the range of the preceding queens (row, column, diagonal). So we define a method isAccessible(row, column), and that method is to determine whether that row or column can fit into a queen. What is the logic of judgment? To determine whether the attack range of the queen of the previous several lines will cover the first column of the first row, the code is as follows:

/ * *

* Determine whether the first row and column can contain the queen

 * @return

* /

private boolean isAccessible(int row, int column) {

    int left = column - 1;  // Upper left of the diagonal

    int right = column + 1; // Diagonal up to the right

    // Start at the top of the current line and work your way up.

    for (int i = row - 1; i >= 0; i--) {

        if (result[i] == column) return false;   // There can be no queens on the current column

        if (left >= 0 && result[i] == left) return false;  // No queens on the upper left diagonal

        if (right < 8 && result[i] == right) return false; // No queens on the upper right diagonal

        left--;

        right++;

    }

    return true;

}

Copy the code

Finally, in order to display the position of the queen, I wrote a way to print the 8*8 checkerboard.

private void printQueen(a) {

    for (int row = 0; row < 8; row++) {

        for (int column = 0; column < 8; column++) {

            if (result[row] == column) System.out.print("Q ");

            else System.out.print("*");

        }

        System.out.println();

    }

    System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = =");

}

Copy the code

There are 92 placement methods in the final operation results.

conclusion

The idea of backtracking is very simple. It is to choose a path at the fork and go on. When you fail, you go back to the previous step and continue until you have tried all the options. Although the idea is simple, but the code to achieve the backtracking method is relatively not so easy to write, often appear at a glance, some of the wrong, the author as a rookie is such, often write wrong, especially the boundary value of the place, so I also suggest you to personally knock on the code.

other

  • Redo log — How MySQL data does not lose when it is down
  • Index Data Structure of B-tree and B+Tree
  • Index Data Structure of B-Tree and B+Tree