Problembeschreibung: Platzieren Sie acht Damen auf dem Schachbrett, wie im Bild gezeigt.
In diesem Artikel werden für die beiden Probleme leicht unterschiedliche Lösungen verwendet, beide verwenden jedoch eindimensionale Arrays. In 6.20 muss ich ein Ein-Bit-Array mit acht Elementen erstellen und den Wert mit dem Index vergleichen 6.22 ist es erforderlich, alle zu finden Effektives Layout, hier verwende ich Oktalzahlen, durchlaufe alle Zahlen von 001234567-076543210, konvertiere sie in Oktalzeichenfolgen, vergleiche jedes Bit mit seinem Index und gebe das Layout aus, das die Bedingungen erfüllt. Die Implementierungsprinzipien und -methoden werden im Folgenden ausführlich vorgestellt.
Teil 1 Wie man beurteilt, ob es sich um ein gültiges Layout handelt
Wir behandeln das Schachbrett als eine 8*8-Matrix im Bereich von 0-7. Wenn Sie das Bild links betrachten, können Sie feststellen, dass sein Layout durch eine Reihe von Zahlenpaaren (von oben nach unten) dargestellt werden kann, nämlich (0, 0), (1, 6), (2, 3), (3). , 5), (4, 7), (5, 1), (6, 4), (7, 2). Dargestellt durch ein Array, das heißt int []list = {0, 6, 3, 5, 7, 1, 4, 2};
Dies ist eindeutig ein gültiges Layout. Als nächstes müssen wir eine Frage berücksichtigen: Gibt es in einem effektiven Layout eine Beziehung zwischen dem Index und seinem entsprechenden Wert im Array, also i und list[i]?
Hier setzen wir list[i] = k; list[j] = q (i > j), was die folgenden zwei Bedingungen erfüllt (es ist einfacher zu verstehen, wenn es auf Papier gezeichnet wird):
1. k != q;
2. i - j == k - q oder i - j == q -k (erhalten aus der Frage)
Um sicherzustellen, dass k != q ist, wird hier die Array-Liste so deklariert und initialisiert, dass list[i] = i ist. Mischen Sie dann das Array nach dem Zufallsprinzip und prüfen Sie, ob Bedingung 2 erfüllt ist
Kopieren Sie den Codecode wie folgt:
// Array erstellen und initialisieren
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
list[i] = i;
// Das Array zufällig mischen
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;
}
}
}
Der Codekörper von 6.20 lautet wie folgt
Kopieren Sie den Codecode wie folgt:
// 6.20 Spiel: Acht Damen
public voidsolveEightQueens(){
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])){ // Prüfen, ob die Bedingung erfüllt ist
notValid = true;
brechen;
}
}
if(notValid) break;
} // Ende der äußeren for-Schleife
} // Ende der Weile
// das Ergebnis ausgeben
int i;
System.out.println("O(∩_∩)Ohaha~, ich habe es " + count + " Mal versucht und hatte schließlich Erfolg.");
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
Teil 2 Finden Sie alle gültigen Layouts
Da 6.22 das Finden aller gültigen Acht-Damen-Layouts erfordert, ist die Methode des zufälligen Mischens des Arrays nicht mehr anwendbar, wir müssen also eine Methode finden, die alle möglichen Arrays durchlaufen kann. Eine der direktesten Methoden ist die Verwendung einer for-Schleife mit acht Ebenen, aber die Codemenge ist zu groß und der Kopf kann leicht in Ohnmacht fallen, sodass diese Methode nicht verwendet wird.
Wenn Sie die Werte des Arrays in Teil 1 sorgfältig beobachten, können Sie feststellen, dass sie alle zwischen 0 und 7 liegen. Durch das Durchlaufen mit oktalen int-Zahlen kann also sichergestellt werden, dass jede Permutation enthalten ist. Da die achtstelligen Zahlen unterschiedlich sind, gibt es 8! = 40320 mögliche Permutationen und die Gesamtzahl der Oktalzahlen beträgt 8^8 = 16777216, sodass das mögliche Verhältnis 40320/16777216 = 1/416 beträgt, was zu diesen 40320 führt Permutationen Es gibt auch Prüfungen, um das endgültige gültige Layout herauszufiltern. Diese Methode ist immer noch etwas ineffizient, aber ich habe noch keine effizientere gefunden.
Kopieren Sie den Codecode wie folgt:
// 6.22 Spiel: Verschiedene Lösungen für das Acht-Damen-Problem (Erhöhen des int-Werts, anschließendes Konvertieren in einen Oktalstring und anschließende Überprüfung)
öffentliches statisches void lösenEightQueensMethod(){
int start = 001234567; // Oktal
int end = 076543210; // Oktal
int count = 0; // Berechnen Sie die Anzahl der gültigen 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); // Anzahl der gültigen Layouts ausgeben
}
// Prüfen, ob Nummer ein gültiges Layout ist
öffentlicher statischer boolescher Wert isValid(int number){
String numOct = Integer.toOctalString(number);
int arrSize = numOct.length();
if(arrSize==7) { // Wenn die erste Ziffer der Zahl 0 ist, hat die generierte Zeichenfolge nur sieben Zeichen
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; // gleiche Spalte
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false; //Gleiche Diagonale
}
}
return true;
}
Teil 3 Erweiterung: Das Problem der Kombinationsgenerierung
Eine solche Frage gab es letztes Jahr in einem schriftlichen Test. Geben Sie bei gegebener Sequenz alle Kombinationen aus. Zum Beispiel,
Ausgabe von „123“: 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Ausgabe von „abcd“: a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., abcd, ...
In 6.22 besteht die Methode zum Auffinden aller Acht-Königinnen-Layouts darin, die int-Typnummer zu erhöhen und sie dann einzeln zu überprüfen. Das obige Problem kann auf ähnliche Weise gelöst werden. Allerdings ist die Effizienz etwas gering. Wenn es einen effizienteren Weg gibt, fragen Sie bitte einen Experten um Rat.