I. Problem description

The eight Queens problem, an ancient and famous problem, is a typical case of backtracking algorithm. The question was put forward by the international chess player Max Bethel in 1848: how many positions can there be when eight queens are placed on an 8×8 square of chess so that they cannot attack each other? That is, no two queens can be in the same row, column or slash (92).

2. How to solve the problem

  1. The first queen puts the first row, first column
  2. The second queen starts from the first column of the second row to determine whether it is feasible to put it in the second column, the third column and so on……
  3. The third queen, the first, the second… Until the eighth queen can also be placed in a position that does not conflict, you have found the correct solution
  4. And when you get a correct solution, when you get back on the previous stack, you start backtracking, so that all of the correct solutions that you put the first queen in the first column, you get all of them
  5. Then go back to the first queen and put the second column, and continue the cycle of steps 1, 2, 3, and 4

Third, the idea of implementation

  • I’m going to create a value for how many queens there are; Define an array array to store where the queen is stored. (Instead of using a two-dimensional array, use a one-dimensional array and place the queen of row I in which column)
  • Write a method to display the position of the queen
  • Write a method to determine if the NTH queen is in a valid position (same row, same column, same slash) by determining if the slope is 1
  • Write a way to put queens, starting from the 0th queen, starting from column 1, drop one if there is a conflict, drop another if there is no conflict, and so on recursively.

Four, code,

public class Queens {
    int max = 8; // Total 8 queens, define the initial value
    int[] array = new int[max];
    static int count=0;
    public static void main(String[] args) {
        Queens queens = new Queens();
        queens.put(0);
        System.out.println(count);
    }

    // Result output method
    private void print(a) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
        System.out.println();
    }

    // Check if the NTH queen conflicts with the previous queen
    private boolean check(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[i] - array[n])) {
                return false; }}return true;
    }

    // Place the NTH queen
    private void put(int n){
        if (n == max){ // Since the subscript starts at 0, so when n=8, it means that we have already put 8 queens. Print the result directly.
            count++;
            print();
            return;
        }
        for (int i=0; i<max; i++){ array[n] = i;// Put the queen first in the row
            if (check(n)){// Check whether there is a conflict when placing the NTH queen, if not, continue to place the NTH +1 queen.
                put(n+1); }}Array [n] = I = array[n] = I = array[n] = I = array[n] = I}}Copy the code