Huit reines avec Java

Le code suivant fonctionne très bien mais prend trop de temps. placeQueens nécessite également beaucoup de temps. Le programme prend 5 à 10 secondes.

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; } } 

Commentaires

  • Vous pouvez éventuellement utiliser une méthode de recherche avec retour en arrière. Répétez simplement en plaçant les reines une par une, en choisissant à chaque fois une première position libre (non occupée et non attaquée). Sil ny a pas de position libre pour une n -ème reine, reculez et déplacez la reine non. ( n -1) de la place courante à la prochaine position libre. Sil ny a ‘ aucune position libre, supprimez ( n -1) et revenez en arrière. Si vous revenez au plateau vide, il ny a plus darrangements de reine possibles. Si vous avez réussi à déplacer une reine ( n -1) à l’étape ‘ back ‘, procédez au placement le n -ième. Le placement aléatoire est tout simplement trop inefficace.
  • Où ‘ est la fonction main()?
  • @CiaPan merci, mais je pense quil existe une meilleure solution.
  • @TobySpeight appelle simplement la classe dans le main() !!
  • Vous pouvez ‘ t invoquer une classe – vous pouvez en construire une instance ou en invoquer les méthodes statiques. startSimulation() est-il censé être la fonction principale? Si tel est le cas, vous pouvez lappeler main() à la place.

Réponse

Tout comme bogosort ne sera jamais un algorithme de tri rapide. Votre solution « jeter le tableau et placer au hasard N nouvelles reines » ne sera jamais vraiment plus rapide que ces 5 à 10 secondes.

Néanmoins, cela ma fait plaisir de voir quelle trouve effectivement une solution de manière assez cohérente. Et la question elle-même est bien composée aussi, donc je pense quelle mérite une réponse.

Comme CiaPan la déjà suggéré dans un commentaire, une bien meilleure façon de résoudre le problème des n-reines est le retour en arrière. Mon programme de test rapide avec cette approche résout les 8-reines en 1 milliseconde (ou moins). (Et les 20 reines en 50 ms).

Cependant, lapproche « réinitialiser et placer au hasard n nouvelles reines » est intéressante à voir, alors ajoutons une amélioration majeure pour accélérer la recherche dun solution.

/** 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); } 

Ce petit changement ici a réduit le temps jusquà la solution à moins de 100 ms de manière cohérente. Pourquoi? Parce que cela réduit lespace de recherche de O (n³) à O (n²). La raison pour laquelle cela fonctionne, cest que dans toutes les solutions, il y a exactement 1 reine sur chaque ligne. Donc jen génère une au hasard pour chaque ligne, au lieu de sur tout le tableau.

Commentaires

  • Merci pour la bonne réponse, mais il semble ‘ que jai déjà terminé rapidement mais que jai toujours un problème avec set random queen .
  • Il y a un autre point à considérer: @IbrahimAli na pas ‘ dire quel est réellement son objectif, trouvant tout arrangement valide ou tous arrangements valides de 8 Queens. Une recherche systématique enfermée dans une boucle fera le dernier (retour n toutes les solutions possibles, et chacune exactement une fois), alors que la génération aléatoire ne peut pas (peut bien répéter les réponses et on ne sait jamais si elle a trouvé toutes les possibilités; avec une qualité RNG médiocre, il peut même être incapable den trouver).
  • @CiaPan Je ‘ je pense à n position pour n booléen simplement je crée un tableau booléen et lutilise ‘ s index en fonction du hasard reines, toutes les reines générées, jai défini un index illégal sur false dans le tableau booléen, ce qui sera très court.
  • @Imus Vous navez ‘ pas besoin de do – while, car chaque placeQueens(i) invoqué par la boucle for (int i = 0; i < 8; i++) attribue une position sur une ligne distincte, donc les collisions sont impossibles et les tester est une perte de temps.
  • Aha true CiaPan. Bien repéré. Jai seulement fait le changement minimal pour en générer un sur chaque ligne dans le code dorigine. Cest ‘ pourquoi je viens de passer ce i à la méthode. Jai également remarqué la vérification désormais redondante, mais cela ne vous fait gagner que moins dune milliseconde pour trouver la solution. Vous ne pouvez donc ‘ t vraiment faire la différence de toute façon.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *