Otte dronninger med Java

Følgende kode fungerer godt, men tager for meget tid. placeQueens kræver også meget tid. Programmet tager 5-10 sekunder.

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

Kommentarer

• Eventuelt kan du bruge en søgemetode med backtracking. Bare gentag at placere dronninger en efter en, hver gang du vælger en første fri (ikke besat og ikke angrebet) position. Hvis der ikke er nogen ledig position for en n -te dronning, skal du træde tilbage og flytte dronningen. ( n -1) fra det aktuelle sted til den næste ledige position. Hvis der ‘ ikke er nogen fri position, skal du fjerne ( n -1) og træde tilbage igen. Hvis du trådte tilbage til tomt bord, er der ikke flere mulige dronningsarrangementer. Hvis du med succes flyttede en dronning ( n -1) i ‘ tilbage ‘ trin, fortsæt med placeringen den n -te. Tilfældig placering er bare for ineffektiv.
• Hvor ‘ er main() -funktionen?
• @CiaPan tak, men jeg synes, der er en bedre løsning.
• @TobySpeight påkalder blot klassen i main() !!
• Dig kan ‘ ikke påberåbe sig en klasse – du kan konstruere en forekomst af en eller påberåbe sig dens statiske metoder. Skal startSimulation() være hovedfunktionen? I så fald kan du kalde det main() i stedet.