Descrição do problema: Coloque oito rainhas no tabuleiro de xadrez. Não há duas rainhas que possam atacar uma à outra (ou seja, não há duas rainhas na mesma linha, coluna ou diagonal), conforme mostrado na imagem.
Neste artigo, soluções ligeiramente diferentes são usadas para os dois problemas, mas ambos usam matrizes unidimensionais. Em 6.20, é necessário encontrar um layout eficaz. Criei um array de um bit com oito elementos. Embaralhando aleatoriamente os valores do array e comparando o valor com o subscrito, finalmente obtenho um layout eficaz; 6.22, é necessário Encontrar tudo Layout eficaz, aqui eu uso números octais, percorro todos os números de 001234567-076543210, converto-os em strings octais, comparo cada bit com seu subscrito e produzo o layout que atende às condições. Os princípios e métodos de implementação serão apresentados em detalhes abaixo.
Parte 1: Como julgar se é um layout válido
Tratamos o tabuleiro de xadrez como uma matriz 8*8, variando de 0 a 7. Observando a imagem à esquerda, você verá que seu layout pode ser representado por um conjunto de pares de números (de cima para baixo), a saber (0, 0), (1, 6), (2, 3), (3). , 5), (4, 7), (5, 1), (6, 4), (7, 2). Representado por um array, ou seja, int []lista = {0, 6, 3, 5, 7, 1, 4, 2};
Claramente, este é um layout válido. A seguir temos que considerar uma questão: Em um layout eficaz, existe alguma relação entre o subscrito e seu valor correspondente no array, ou seja, i e lista[i]?
Aqui definimos list[i] = k; list[j] = q; que satisfazem as duas condições a seguir (é mais fácil de entender quando desenhado no papel):
1. k != q;
2. i - j == k - q ou i - j == q -k (obtido na pergunta)
Para garantir que k != q, a lista do array é declarada e inicializada aqui de forma que list[i] = i. Em seguida, embaralhe aleatoriamente a matriz e verifique se a condição 2 foi atendida
Copie o código do código da seguinte forma:
// Cria e inicializa o array
int [] lista = new int [arrSize];
for(int i = 0; i < arrSize; i++)
lista[i] = eu;
// Embaralha aleatoriamente o array
public static void randomizeArray(int [] lista){
int arrSize = lista.comprimento;
int ranIndex;
for(int i = 0; i <arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
if(ranIndex != i){
temperatura interna = lista[i];
lista[i] = lista[ranIndex];
lista[ranIndex] = temp;
}
}
}
O corpo do código 6.20 é o seguinte
Copie o código do código da seguinte forma:
// Jogo 6.20: Oito Rainhas
public void resolveEightQueens(){
int tamanhoArr = 8;
int [] lista = new int [arrSize];
for(int i = 0; i < arrSize; i++)
lista[i] = eu;
contagem interna = 0;
booleano notValid = verdadeiro;
while(não válido){
contar++;
notValid = falso;
randomizeArray(lista);
for(int i = 0; i <arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Verifica se a condição foi atendida
notValid = verdadeiro;
quebrar;
}
}
if(notValid) pausa;
} // fim do loop for externo
} //fim do while
//imprime o resultado
int eu;
System.out.println("O(∩_∩)Ohaha~, tentei " + count + " vezes e eventualmente consegui.");
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + lista[i] + "), ");
}
System.out.println("(" + i + ", " + lista[i] + ")");
}
Parte 2 Encontre todos os layouts válidos
Como a versão 6.22 exige encontrar todos os layouts válidos de oito rainhas, o método de embaralhar aleatoriamente o array não é mais aplicável, então temos que encontrar um método que possa percorrer todos os arrays possíveis. Um dos métodos mais diretos é usar um loop for de oito camadas, mas a quantidade de código é muito grande e a cabeça é fácil de desmaiar, então esse método não é usado.
Observando cuidadosamente os valores da matriz na Parte 1, você pode descobrir que eles estão todos entre 0 e 7, portanto, percorrer usando números inteiros octais pode garantir que todas as permutações sejam incluídas. Como os números de oito dígitos são diferentes, existem 8 = 40320 permutações possíveis, e o número total de números octais é 8 ^ 8 = 16777216, então a proporção possível é 40320/16777216 = 1/416, resultando nestes 40320. permutações Também existem verificações para filtrar o layout final válido. Este método ainda é um pouco ineficiente, mas ainda não descobri um mais eficiente.
Copie o código do código da seguinte forma:
// 6.22 Jogo: Várias soluções para o problema das oito rainhas (incrementando o valor int, depois convertendo-o para uma string octal e depois verificando)
public static void resolveEightQueensMethod(){
int início = 001234567;
final interno = 076543210;
int count = 0; // Calcula o número de layouts válidos
for(int i = início; i < fim; i++){
booleano isValid = isValid(i);
if(éválido){
if(++contagem % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
senão System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Mostra o número de layouts válidos;
}
// Verifica se o número é um layout válido
public static boolean isValid(int número){
String numOct = Integer.toOctalString(número);
int arrSize = numOct.length();
if(arrSize==7) { // Se o primeiro dígito do número for 0, a string gerada terá apenas sete caracteres
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 // mesma coluna;
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false;
}
}
retornar verdadeiro;
}
Parte 3 Extensão: O problema de gerar combinações
Houve essa pergunta em um teste escrito no ano passado. Dada uma sequência, produza todas as combinações. por exemplo,
Saída de "123": 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Saída 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, ...
Em 6.22, o método usado para encontrar todos os layouts de oito rainhas é incrementar o número do tipo int e então verificar um por um. O problema acima pode ser resolvido de maneira semelhante. No entanto, a eficiência é um pouco baixa. Se houver uma maneira mais eficiente, peça orientação a um especialista.