Oito rainhas com Java

O código a seguir funciona muito bem, mas leva muito tempo. placeQueens também requer muito tempo. O programa leva de 5 a 10 segundos.

public class EightQueen { public static void startSimulation(){ long startTime = System.currentTimeMillis(); char[] board; // Create an array // Repeat while queens are attacking do { // Generate a board board = getNewBoard(); // Place eight queens placeQueens(board); } while (isAttacking(board)); // Display solution print(board); long endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); } /** placeQueens randomly places eight queens on the board*/ public static void placeQueens(char[] board) { int location; for (int i = 0; i < 8; i++) { do { location = placeQueens(); } while (isOccupied(board[location])); board[location] = "Q"; } } /** placeQueens randomly places one queen on the board */ public static int placeQueens() { return (int)(Math.random() * 64); } /** isAttacking returns true if two queens are attacking each other */ public static boolean isAttacking(char[] board) { return isSameRow(board) || isSameColumn(board) || isSameDiagonal(board); } /** isSameRow returns true if two queens are in the same row */ public static boolean isSameRow(char[] board) { int[] rows = new int[8]; for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { rows[getRow(i)]++; } if (rows[getRow(i)] > 1) return true; } return false; } /** isSameColumn returns true if two queens are in the same column */ public static boolean isSameColumn(char[] board) { int[] columns = new int[8]; for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { columns[getColumn(i)]++; } if (columns[getColumn(i)] > 1) return true; } return false; } /** isSameDiagonal returns true if two queens are on the same diagonal */ public static boolean isSameDiagonal(char[] board) { for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { for (int j = 0; j < board.length; j++) { if (isOccupied(board[j]) && Math.abs(getColumn(j) - getColumn(i)) == Math.abs(getRow(j) - getRow(i)) && j != i) { return true; } } } } return false; } /** isOccupied returns true if the element in x is the char Q */ public static boolean isOccupied(char x) { return x == "Q"; } /** getNewBoard returns a char array filled with blank space */ public static char[] getNewBoard() { char[] board = new char[64]; for (int i = 0; i < board.length; i++) board[i] = " "; return board; } /** print displays the board */ public static void print(char[] board) { for (int i = 0; i < board.length; i++) { System.out.print( "|" + ((getRow(i + 1) == 0) ? board[i] + "|\n" : board[i])); } } /** getRow returns the row number that corresponds to the given index */ public static int getRow(int index) { return index % 8; } /** getColumn returns the column number that corresponds to the given index */ public static int getColumn(int index) { return index / 8; } } 

Comentários

  • Possivelmente, você pode usar um método de pesquisa com retrocesso. Apenas repita a colocação das rainhas uma a uma, escolhendo a cada vez uma primeira posição livre (não ocupada e não atacada). Se não houver posição livre para alguma n -ésima rainha, dê um passo para trás e mova a rainha no. ( n -1) do local atual para a próxima posição livre. Se ‘ não houver uma posição livre, remova ( n -1) e dê um passo atrás novamente. Se você voltou para o tabuleiro vazio, não há mais arranjos de rainha possíveis. Se você moveu com sucesso uma rainha ( n -1) na etapa ‘ voltar ‘, prossiga com a colocação o n -ésimo. A colocação aleatória é muito ineficaz.
  • Onde ‘ é a função main()?
  • @CiaPan obrigado, mas acho que existe uma solução melhor.
  • @TobySpeight simplesmente invoque a classe no main() !!
  • Você não pode ‘ invocar uma classe – você pode construir uma instância de uma ou invocar seus métodos estáticos. startSimulation() deveria ser a função principal? Nesse caso, você poderia chamá-lo de main().

Resposta

Assim como bogosort nunca será um algoritmo de classificação rápido. Sua solução “jogue fora o tabuleiro e coloque N novas rainhas aleatoriamente” nunca será realmente mais rápida do que esses 5 a 10 segundos.

No entanto, fiquei feliz em ver que ela realmente encontra uma solução de forma consistente. E a pergunta em si também está bem composta, então acho que ela merece uma resposta.

Como o CiaPan já sugeriu em um comentário, uma maneira muito melhor de resolver o problema das n-rainhas é retroceder. Meu programa de teste rápido com essa abordagem resolve as 8 rainhas em 1 milissegundo (ou menos). (E as 20 rainhas em 50 ms).

No entanto, a abordagem “redefinir e colocar aleatoriamente n novas rainhas” é interessante de ver, então vamos adicionar uma grande melhoria para acelerar a localização de um solução.

/** placeQueens randomly places eight queens on the board*/ public static void placeQueens(char[] board) { int location; for (int i = 0; i < 8; i++) { do { location = placeQueens(i); } while (isOccupied(board[location])); board[location] = "Q"; } } /** placeQueens randomly places one queen on the board */ public static int placeQueens(int row) { return row * 8 + (int)(Math.random() * 8); } 

Esta pequena mudança aqui reduziu o tempo até a solução para menos de 100 ms de forma consistente. Por quê? Porque isso reduz o espaço de pesquisa de O (n³) para O (n²). O motivo pelo qual isso funciona, é que em todas as soluções há exatamente 1 rainha em cada linha. Então, eu gerei uma aleatoriamente para cada linha, em vez de em todo o tabuleiro.

Comentários

  • Obrigado pela ótima resposta, mas ‘ s parece que já terminei um rápido, mas ainda tenho problemas com definir rainha aleatória .
  • Há outro ponto que vale a pena considerar: @IbrahimAli não ‘ não disse qual é realmente o seu objetivo, encontrar qualquer acordo válido ou todos arranjos válidos de 8 Rainhas. A pesquisa sistemática encerrada em um loop fará o último (retur n todas as soluções possíveis, e cada uma exatamente uma vez), enquanto a geração aleatória não pode (pode muito bem repetir as respostas e nunca sabemos se encontrou todas as possibilidades; com baixa qualidade de RNG, pode ser até incapaz de encontrar alguns).
  • @CiaPan I ‘ estou pensando em n posição para n booleano simplesmente crio uma matriz booleana e a uso ‘ índice por depender aleatoriamente rainhas, todas as rainhas geradas eu defino o índice ilegal como falso na matriz booleana, o que levará muito tempo.
  • @Imus Você não ‘ não precisa do do – while loop, pois cada placeQueens(i) invocado pelo loop for (int i = 0; i < 8; i++) aloca uma posição em uma linha separada, portanto, as colisões são impossíveis e testá-las é uma perda de tempo.
  • Aha verdadeiro CiaPan. Bem localizado. Eu apenas fiz a mudança mínima para gerar um em cada linha do código original. É por isso ‘ que acabei de passar esse i para o método. Também notei a verificação agora redundante, mas isso só faz com que você ganhe menos de um milissegundo para encontrar a solução. Portanto, você não pode ‘ realmente dizer a diferença de qualquer maneira.

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *