Ocho reinas con Java

El siguiente código funciona muy bien, pero lleva demasiado tiempo. placeQueens también requiere mucho tiempo. El programa tarda entre 5 y 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; } } 

Comentarios

• Posiblemente pueda utilizar un método de búsqueda con retroceso. Simplemente repita la colocación de las reinas una por una, eligiendo cada vez una primera posición libre (no ocupada ni atacada). Si no hay una posición libre para una n -ésima reina, da un paso atrás y mueve la reina no. ( n -1) desde el lugar actual a la siguiente posición libre. Si ‘ no hay una posición libre, elimine ( n -1) y retroceda de nuevo. Si retrocedió al tablero vacío, no hay más arreglos de reina posibles. Si movió con éxito una reina ( n -1) en el paso ‘ atrás ‘, continúe colocando el n -ésimo. La colocación aleatoria es demasiado ineficaz.
• ¿Dónde ‘ es la main() función?
• @CiaPan gracias, pero creo que hay una solución mejor.
• @TobySpeight simplemente invoca la clase en el main() !!
• Tú puede ‘ t invocar una clase; puede construir una instancia de una o invocar sus métodos estáticos. ¿Se supone que startSimulation() es la función principal? Si es así, puede llamarlo main() en su lugar.