Descripción del problema: Coloque ocho reinas en el tablero de ajedrez. No hay dos reinas que puedan atacarse entre sí (es decir, no hay dos reinas en la misma fila, columna o diagonal) como se muestra en la imagen.
En este artículo, se utilizan soluciones ligeramente diferentes para los dos problemas, pero ambos utilizan matrices unidimensionales. En 6.20, es necesario encontrar un diseño efectivo. Creé una matriz de un bit con ocho elementos mezclando aleatoriamente los valores de la matriz y comparando el valor con el subíndice, finalmente obtengo un diseño efectivo. 6.22, es obligatorio Buscar todo Diseño efectivo, aquí uso números octales, recorro todos los números desde 001234567-076543210, los convierto en cadenas octales, comparo cada bit con su subíndice y genero el diseño que cumple con las condiciones. Los principios y métodos de implementación se presentarán en detalle a continuación.
Parte 1 Cómo juzgar si es un diseño válido
Tratamos el tablero de ajedrez como una matriz de 8*8, que va de 0 a 7. Al observar la imagen de la izquierda, puede encontrar que su diseño se puede representar mediante un conjunto de pares de números (de arriba a abajo), a saber (0, 0), (1, 6), (2, 3), (3). , 5), (4, 7), (5, 1), (6, 4), (7, 2). Representado por una matriz, es decir, int []list = {0, 6, 3, 5, 7, 1, 4, 2};
Claramente, este es un diseño válido. A continuación debemos considerar una pregunta: en un diseño efectivo, ¿existe alguna relación entre el subíndice y su valor correspondiente en la matriz, es decir, i y lista [i]?
Aquí configuramos list[i] = k; list[j] = q (i > j), que satisface las dos condiciones siguientes (es más fácil de entender cuando se dibuja en papel):
1. k != q;
2. i - j == k - q o i - j == q -k (obtenido de la pregunta)
Para garantizar que k != q, la lista de matriz se declara e inicializa aquí de modo que list[i] = i. Luego mezcle aleatoriamente la matriz y luego verifique si se cumple la condición 2
Copie el código de código de la siguiente manera:
// Crea e inicializa la matriz
int [] lista = nuevo int [arrSize];
para(int i = 0; i < tamañoarr; i++)
lista[i] = yo;
// Mezcla aleatoriamente la matriz
public static void randomizeArray(int [] lista){
int arrSize = lista.longitud;
int ranIndex;
for(int i = 0; i < tamañoarr; i++){
ranIndex = (int)(Math.random() * arrSize);
si(ranIndex!= i){
int temp = lista[i];
lista[i] = lista[ranIndex];
lista[ranIndex] = temporal;
}
}
}
El cuerpo del código de 6.20 es el siguiente
Copie el código de código de la siguiente manera:
// Juego 6.20: Ocho Reinas
resolver el vacío públicoEightQueens(){
int tamañoarr = 8;
int [] lista = nuevo int [arrSize];
para(int i = 0; i < tamañoarr; i++)
lista[i] = yo;
recuento int = 0;
booleano notValid = verdadero;
mientras (no válido) {
contar++;
no válido = falso;
matriz aleatoria(lista);
for(int i = 0; i < tamañoarr; i++){
for(int j = i + 1; j < tamañoarr; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Comprobar si se cumple la condición
no válido = verdadero;
romper;
}
}
si (no válido) descanso;
} // final del bucle for externo
} // fin del tiempo
//imprime el resultado
ent i;
System.out.println("O(∩_∩)Ohaha~, lo he intentado " + count + " veces y finalmente lo he logrado.");
para(i = 0; i < tamañoarr - 1; i++){
System.out.print("(" + i + ", " + lista[i] + "), ");
}
System.out.println("(" + i + ", " + lista[i] + ")");
}
Parte 2 Encuentra todos los diseños válidos
Dado que 6.22 requiere encontrar todos los diseños válidos de ocho reinas, el método de barajar aleatoriamente la matriz ya no es aplicable, por lo que tenemos que encontrar un método que pueda atravesar todas las matrices posibles. Uno de los métodos más directos es utilizar un bucle for de ocho capas, pero la cantidad de código es demasiado grande y es fácil debilitar la cabeza, por lo que no se utiliza este método.
Al observar cuidadosamente los valores de la matriz en la Parte 1, puede encontrar que todos están entre 0 y 7, por lo que atravesar usando números int octales puede garantizar que se incluyan todas las permutaciones. Dado que los números de ocho dígitos son diferentes, hay 8 = 40320 permutaciones posibles, y el número total de números octales es 8^8 = 16777216, por lo que la relación posible representa 40320/16777216 = 1/416, lo que da como resultado estos 40320. permutaciones También hay comprobaciones para filtrar el diseño final válido. Este método todavía es un poco ineficiente, pero todavía no he encontrado uno más eficiente.
Copie el código de código de la siguiente manera:
// Juego 6.22: varias soluciones al problema de las ocho reinas (incrementar el valor int, luego convertirlo en una cadena octal y luego verificar)
vacío estático público resolverEightQueensMethod(){
int inicio = 001234567 // Octal
int final = 076543210; // octal
int count = 0; // Calcula el número de diseños válidos
for(int i = inicio; i < fin; i++){
booleano es válido = es válido (i);
si(es válido){
si(++cuenta % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Muestra el número de diseños válidos.
}
// Comprobar si el número es un diseño válido
booleano estático público es válido (número int) {
Cadena numOct = Integer.toOctalString(número);
int tamañoarr = numOct.length();
if(arrSize==7) { // Si el primer dígito del número es 0, la cadena generada tiene solo siete caracteres
númOct = '0' + númOct;
tamañoarr++;
}
for(int i = 1; i < tamañoarr; i ++){
for(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false // misma columna;
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false //Misma diagonal;
}
}
devolver verdadero;
}
Extensión de la Parte 3: El problema de generar combinaciones
Hubo una pregunta así en una prueba escrita el año pasado. Dada una secuencia, genera todas las combinaciones. Por ejemplo,
Salida de "123": 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Salida 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, ...
En 6.22, el método utilizado para encontrar todos los diseños de ocho reinas es incrementar el número de tipo int y luego verificar uno por uno. El problema anterior se puede resolver de forma similar. Sin embargo, la eficiencia es un poco baja. Si existe una forma más eficiente, solicite orientación a un experto.