Description du problème : placez huit reines sur l'échiquier. Deux reines ne peuvent pas s'attaquer (c'est-à-dire qu'il n'y a pas deux reines dans la même rangée, colonne ou diagonale) comme indiqué sur l'image.
Dans cet article, des solutions légèrement différentes sont utilisées pour les deux problèmes, mais les deux utilisent des tableaux unidimensionnels. En 6.20, il est nécessaire de trouver une disposition efficace. J'ai établi un tableau d'un bit avec huit éléments, en mélangeant aléatoirement les valeurs du tableau et en comparant la valeur avec l'indice jusqu'à ce qu'une disposition efficace soit obtenue en 6.22, c'est obligatoire Trouver tout Disposition efficace, ici j'utilise des nombres octaux, traverse tous les nombres de 001234567 à 076543210, les convertis en chaînes octales, compare chaque bit avec son indice et génère la disposition qui répond aux conditions. Les principes et méthodes de mise en œuvre seront présentés en détail ci-dessous.
Partie 1 Comment juger s'il s'agit d'une mise en page valide
Nous traitons l'échiquier comme une matrice 8*8, allant de 0 à 7. En observant l'image de gauche, vous constaterez que sa disposition peut être représentée par un ensemble de paires de nombres (de haut en bas), à savoir (0, 0), (1, 6), (2, 3), (3). , 5), (4, 7), (5, 1), (6, 4), (7, 2). Représenté par un tableau, c'est-à-dire int []list = {0, 6, 3, 5, 7, 1, 4, 2};
De toute évidence, il s’agit d’une mise en page valide. Ensuite, nous devons considérer une question : dans une mise en page efficace, existe-t-il une relation entre l'indice et sa valeur correspondante dans le tableau, c'est-à-dire i et list[i] ?
Ici, nous définissons list[i] = k; list[j] = q; (i > j), qui satisfont aux deux conditions suivantes (c'est plus facile à comprendre lorsqu'il est dessiné sur papier) :
1.k !=q;
2. i - j == k - q ou i - j == q -k (obtenu à partir de la question)
Afin de garantir que k != q, la liste de tableaux est déclarée et initialisée ici pour que list[i] = i. Mélangez ensuite le tableau au hasard, puis vérifiez si la condition 2 est remplie.
Copiez le code comme suit :
//Créer et initialiser le tableau
int [] liste = nouveau int [arrSize];
pour(int i = 0; i < arrSize; i++)
liste[je] = je;
// Mélange aléatoirement le tableau
public static void randomizeArray (liste int []) {
int arrSize = liste.longueur;
int ranIndex ;
pour(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
si(ranIndex != i){
int temp = liste[i];
liste[i] = liste[ranIndex];
liste[ranIndex] = temp;
}
}
}
Le corps du code de 6.20 est le suivant
Copiez le code comme suit :
// 6.20 Jeu : Huit Dames
public void solveEightQueens(){
int arrTaille = 8;
int [] liste = nouveau int [arrSize];
pour(int i = 0; i < arrSize; i++)
liste[je] = je;
nombre entier = 0 ;
booléen notValid = vrai ;
pendant que (non valide) {
compte++;
notValid = faux ;
randomizeArray(liste);
pour(int i = 0; i < arrSize; i++){
pour(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Vérifiez si la condition est remplie
notValid = vrai ;
casser;
}
}
if(notValid) pause ;
} // fin de la boucle for externe
} // fin de temps
// affiche le résultat
int je;
System.out.println("O(∩_∩)Ohaha~, j'ai essayé " + count + " fois et j'ai finalement réussi. ");
pour(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
Partie 2 Trouver toutes les mises en page valides
Puisque la version 6.22 nécessite de trouver toutes les dispositions valides à huit reines, la méthode de mélange aléatoire du tableau n'est plus applicable, nous devons donc trouver une méthode capable de parcourir tous les tableaux possibles. L'une des méthodes les plus directes consiste à utiliser une boucle for à huit couches, mais la quantité de code est trop grande et la tête est facile à s'évanouir, cette méthode n'est donc pas utilisée.
En observant attentivement les valeurs du tableau dans la partie 1, vous constaterez qu'elles sont toutes comprises entre 0 et 7, donc le parcours à l'aide de nombres entiers octaux peut garantir que chaque permutation est incluse. Puisque les nombres à huit chiffres sont différents, il y a 8 ! = 40 320 permutations possibles, et le nombre total de nombres octaux est 8^8 = 16777216, donc le rapport possible représente 40320/16777216 = 1/416, ce qui donne ces 40320. permutations Il existe également des contrôles pour filtrer la mise en page finale valide. Cette méthode est encore un peu inefficace, mais je n’en ai pas encore trouvé de plus efficace.
Copiez le code comme suit :
// 6.22 Jeu : Diverses solutions au problème des huit reines (incrémenter la valeur int, puis la convertir en chaîne octale, puis vérifier)
public static void solveEightQueensMethod(){
int start = 001234567; // Octal
int fin = 076543210; // octal
int count = 0; // Calcule le nombre de mises en page valides
pour(int i = début; i < fin; i++){
booléen isValid = isValid(i);
si(estValide){
si(++compte % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Affiche le nombre de mises en page valides
}
// Vérifiez si le numéro est une mise en page valide
public static boolean isValid(int number){
String numOct = Integer.toOctalString(nombre);
int arrSize = numOct.length();
if(arrSize==7) { // Si le premier chiffre du nombre est 0, la chaîne générée ne comporte que sept caractères
numOct = '0' + numOct;
arrTaille++;
}
pour(int je = 1; je < arrSize; je ++){
pour(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false // même colonne ;
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false //Même diagonale ;
}
}
renvoie vrai ;
}
Extension de la partie 3 : le problème de la génération de combinaisons
Il y avait une telle question lors d’un test écrit l’année dernière. Étant donné une séquence, affichez toutes les combinaisons. Par exemple,
Sortie de "123" : 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Sortie de "abcd": a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., abcd, ...
Dans la version 6.22, la méthode utilisée pour trouver toutes les dispositions à huit reines consiste à incrémenter le numéro de type int, puis à vérifier une par une. Le problème ci-dessus peut être résolu de la même manière. Cependant, l'efficacité est un peu faible. S'il existe un moyen plus efficace, veuillez demander conseil à un expert.