Optimierung des Rätsels mit N Königinnen

Question

Ich versuche, das Problem der Positionierung von N Damen auf einem NxN Brett ohne Zeilen-, Spalten- und Diagonalkonflikte zu lösen. Ich verwende einen Algorithmus, der die Konflikte minimiert. Zunächst wird auf jeder Spalte zufällig eine Dame platziert. Danach wird von allen Konflikt-Damen eine zufällig ausgewählt und für ihre Spalte werden die Konflikte jeder möglichen Position berechnet. Dann zieht die Königin in die beste Position mit der geringsten Anzahl von Konflikten. Es funktioniert, aber es läuft extrem langsam. Mein Ziel ist es, es für 10000 Königinnen schnell laufen zu lassen. Würden Sie mir bitte einige Verbesserungen vorschlagen oder vielleicht einige Fehler in meiner Logik bemerken?

Hier ist mein Code:

public class Queen {

int column;
int row;
int d1;
int d2;

public Queen(int column, int row, int d1, int d2) {
    super();
    this.column = column;
    this.row = row;
    this.d1 = d1;
    this.d2 = d2;
}

@Override
public String toString() {
    return "Queen [column=" + column + ", row=" + row + ", d1=" + d1
            + ", d2=" + d2 + "]";
}

@Override
public boolean equals(Object obj) {
    return ((Queen)obj).column == this.column && ((Queen)obj).row == this.row;
}   

}

Und:

import java.util.HashSet;
import java.util.Random;

public class SolveQueens {
public static boolean printBoard = false;
public static int N = 100;
public static int maxSteps = 2000000;
public static int[] queens = new int[N];
public static Random random = new Random();

public static HashSet<Queen> q = new HashSet<Queen>();

public static HashSet rowConfl[] = new HashSet[N];
public static HashSet d1Confl[] = new HashSet[2*N - 1];
public static HashSet d2Confl[] = new HashSet[2*N -  1];

public static void init () {
    int r;
    rowConfl = new HashSet[N];
    d1Confl = new HashSet[2*N - 1];
    d2Confl = new HashSet[2*N - 1];
    for (int i = 0; i < N; i++) {
        r = random.nextInt(N);
        queens[i] = r;
        Queen k = new Queen(i, r, i + r, N - 1 +  i - r);
        q.add(k);
        if (rowConfl[k.row] == null) {
            rowConfl[k.row] = new HashSet<Queen>();
        }
        if (d1Confl[k.d1] == null) {
            d1Confl[k.d1] = new HashSet<Queen>();
        }
        if (d2Confl[k.d2] == null) {
            d2Confl[k.d2] = new HashSet<Queen>();
        }
        ((HashSet<Queen>)rowConfl[k.row]).add(k);
        ((HashSet<Queen>)d1Confl[k.d1]).add(k);
        ((HashSet<Queen>)d2Confl[k.d2]).add(k);
    }
}

public static void print () {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            System.out.print(queens[i] == j ? " " : " ");
        }
        System.out.println();
    }  
    System.out.println();
}

public static boolean checkItLinear() {

    Queen r = choseConflictQueen();

    if (r == null) {
        return true;
    }

    Queen newQ = findNewBestPosition(r);

    q.remove(r);
    q.add(newQ);
    rowConfl[r.row].remove(r);
    d1Confl[r.d1].remove(r);
    d2Confl[r.d2].remove(r);
    if (rowConfl[newQ.row] == null) {
        rowConfl[newQ.row] = new HashSet<Queen>();
    }
    if (d1Confl[newQ.d1] == null) {
        d1Confl[newQ.d1] = new HashSet<Queen>();
    }
    if (d2Confl[newQ.d2] == null) {
        d2Confl[newQ.d2] = new HashSet<Queen>();
    }
    ((HashSet<Queen>)rowConfl[newQ.row]).add(newQ);
    ((HashSet<Queen>)d1Confl[newQ.d1]).add(newQ);
    ((HashSet<Queen>)d2Confl[newQ.d2]).add(newQ);
    queens[r.column] = newQ.row;
    return false;
}

public static Queen choseConflictQueen () {

    HashSet<Queen> conflictSet = new HashSet<Queen>();
    boolean hasConflicts = false;

    for (int i = 0; i < 2*N - 1; i++) {
        if (i < N && rowConfl[i] != null) {
            hasConflicts = hasConflicts || rowConfl[i].size() > 1;
            conflictSet.addAll(rowConfl[i]);
        }
        if (d1Confl[i] != null) {
            hasConflicts = hasConflicts || d1Confl[i].size() > 1;
            conflictSet.addAll(d1Confl[i]);
        }
        if (d2Confl[i] != null) {
            hasConflicts = hasConflicts || d2Confl[i].size() > 1;
            conflictSet.addAll(d2Confl[i]);
        }
    }
    if (hasConflicts) {
        int c = random.nextInt(conflictSet.size());
        return (Queen) conflictSet.toArray()[c];
    }

    return null;
}

public static Queen findNewBestPosition(Queen old) {        
    int[] row = new int[N];
    int min = Integer.MAX_VALUE;
    int minInd = old.row;

    for (int i = 0; i < N; i++) {
        if (rowConfl[i] != null) {
            row[i] = rowConfl[i].size();
        }
        if (d1Confl[old.column + i] != null) {
            row[i] += d1Confl[old.column + i].size();
        }
        if (d2Confl[N - 1 +  old.column - i] != null) {
            row[i] += d2Confl[N - 1 +  old.column - i].size();
        }
        if (i == old.row) {
            row[i] = row[i] - 3;
        }

        if (row[i] <= min && i != minInd) {
            min = row[i];
            minInd = i;
        }
    }

    return new Queen(old.column, minInd, old.column + minInd, N - 1 +  old.column - minInd);
}

public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        init();
        int steps = 0;
        while(!checkItLinear()) {
            if (++steps > maxSteps) {
                init();
                steps = 0;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Done for " + (endTime - startTime) + "ms\n");

        if(printBoard){
            print(); 
        }

}
}

Bearbeiten:

Hier ist meine etwas optimierte Lösung, bei der ich einige unbenutzte Objekte entfernt und die Damen beim Initialisieren auf diagonale Positionen gesetzt habe.

import java.util.Random;
import java.util.Vector;

public class SolveQueens {
public static boolean PRINT_BOARD = true;
public static int N = 10;
public static int MAX_STEPS = 5000;

public static int[] queens = new int[N];
public static Random random = new Random();

public static int[] rowConfl = new int[N];
public static int[] d1Confl = new int[2*N - 1];
public static int[] d2Confl = new int[2*N - 1];

public static Vector<Integer> conflicts = new Vector<Integer>();

public static void init () {
    random = new Random();
    for (int i = 0; i < N; i++) {
        queens[i] = i;
    }
}

public static int getD1Pos (int col, int row) {
    return col + row;
}

public static int getD2Pos (int col, int row) {
    return N - 1 + col - row;
}

public static void print () {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            System.out.print(queens[i] == j ? "Q " : "* ");
        }
        System.out.println();
    }  
    System.out.println();
}

public static boolean hasConflicts() {

    generateConflicts();

    if (conflicts.isEmpty()) {
        return false;
    }

    int r = random.nextInt(conflicts.size());
    int conflQueenCol = conflicts.get(r);
    int currentRow = queens[conflQueenCol];
    int bestRow = currentRow;
    int minConfl = getConflicts(conflQueenCol, queens[conflQueenCol]) - 3;
    int tempConflCount;

    for (int i = 0; i < N ; i++) {
        tempConflCount = getConflicts(conflQueenCol, i);
        if (i != currentRow && tempConflCount <= minConfl) {
            minConfl = tempConflCount;
            bestRow = i;
        }
    }
    queens[conflQueenCol] = bestRow;
    return true;
}

public static void generateConflicts () {

    conflicts = new Vector<Integer>();

    rowConfl = new int[N];
    d1Confl = new int[2*N - 1];
    d2Confl = new int[2*N -  1];

    for (int i = 0; i < N; i++) {
        int r = queens[i];
        rowConfl[r]++;
        d1Confl[getD1Pos(i, r)]++;
        d2Confl[getD2Pos(i, r)]++;
    }

    for (int i = 0; i < N; i++) {
        int conflictsCount = getConflicts(i, queens[i]) - 3;
        if (conflictsCount > 0) {
            conflicts.add(i);
        }
    }
}

public static int getConflicts(int col, int row) {
    return rowConfl[row] + dConfl[getD1Pos(col, row)] + d2Confl[getD2Pos(col, row)];
}

public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        init();
        int steps = 0;
        while(hasConflicts()) {
            if (++steps > MAX_STEPS) {
                init();
                steps = 0;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Done for " + (endTime - startTime) + "ms\n");

        if(PRINT_BOARD){
            print(); 
        }
}

}