This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Greedy thinking solves the Queen problem (Conflict detection)

solution

(1) First determine the position of each queen and then calculate the initial number of conflicts (e.g., 3, 3, 3)

(2) Select the line with the largest number of conflicts to adjust the position of the queen

(3) Calculate the number of conflicts that the queen moves to each row

(4) Move the queen to the least conflict position and recalculate the number of conflicts

(5) Repeat the above four operations to find the number of conflicts for each queen is 0

code

package demo1;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/** * Greedy thoughts to solve the queen problem (conflict detection) */
@SuppressWarnings({"all"})
public class Queen {

    private  static int [] flag  = new int[1001]; // Create an array to determine the location
    private static int [] sum = new int[100]; // Create an array to record collisions

    public static void init(int[] flag, int num){

        for (int i = 1; i <= num ; i++) {
            long l = System.currentTimeMillis();
            int tmp = (int)( l % ( num - 1)) +1; // The random number ranges from 1 to numflag[i] = tmp ; }}private static void sumConflict(int[] flag, int[] sum, int num) {
        for (int i = 0; i < num + 1; i++) {
            sum[i] = 0;
        }
        for (int j = 1; j <= num ; j++) {
            for (int k = 1; k <= num ; k++) {
                if( j ! = k && ( flag[j] == flag[k] || flag[j] - flag[k] == j - k || flag[j] - flag[k] == k - j)){ sum[j]++; }}}}private static void sumConflict(int [] flag, int[] sum, int num, int max) {
        for (int i = 0; i < num + 1; i++) {
            sum[i] = 0;
        }
            for (int j = 1; j <= num ; j++) {
                flag[max] = j ;
                for (int k = 1; k <= num ; k++) {
                    if( max ! = k && (j == flag[k] || k - max == flag[k] - j || max - k == flag[k] - j ) ){ sum[j]++; }}}}private static void getTrueQueen(int[] flag, int[] sum, int i) {
        while (flagOK(sum,i)){
           inttmp = sumMax(sum,i); sumConflict(flag,sum,i,tmp); flag[tmp] = sumMin(sum,i); sumConflict(flag,sum,i); }}private static int sumMax(int[] sum,int num) {
        int max = 1;
        for (int i = 1; i <= num; i++) {
            if(sum[i] > sum[max]){ max = i; }}return max;
    }
    private static int sumMin(int[] sum,int num) {
        int min = 1;
        for (int i = 1; i <= num; i++) {
            if(sum[i] < sum[min]){ min = i; }}return min;
    }

    private static boolean flagOK(int sum[],int num) {
        for (int i = 1; i <= num; i++) {
            if(sum[i] ! =0) {return true; }}return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        // Initialize the queen position. It is recommended to use a random number for assignment
        init(flag,i);
        // Count the number of collisions
        sumConflict(flag,sum,i);
        getTrueQueen(flag,sum,i);

        for (int j = 1; j <= i ; j++) { System.out.println(flag[j]); }}}Copy the code