Acht Königinnen mit Java

Der folgende Code funktioniert hervorragend, nimmt aber zu viel Zeit in Anspruch. placeQueens benötigt ebenfalls viel Zeit. Das Programm dauert 5-10 Sekunden.

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

Kommentare

• Möglicherweise können Sie eine Suchmethode verwenden mit Backtracking. Wiederholen Sie einfach die Platzierung der Königinnen nacheinander und wählen Sie jedes Mal eine erste freie Position (nicht besetzt und nicht angegriffen). Wenn es für eine n -te Königin keine freie Position gibt, treten Sie zurück und bewegen Sie die Königin Nr. ( n -1) vom aktuellen Ort zur nächsten freien Position. Wenn ‚ keine freie Position hat, entfernen Sie ( n -1) und treten Sie erneut zurück. Wenn Sie zurück zum leeren Brett getreten sind, gibt es keine möglichen Königinnenarrangements mehr. Wenn Sie eine Königin ( n -1) im Schritt ‚ zurück ‚ erfolgreich verschoben haben, fahren Sie mit dem Platzieren fort das n -te. Die zufällige Platzierung ist einfach zu unwirksam.
• Wo ‚ ist die Funktion main()?
• @CiaPan danke, aber ich denke, es gibt eine bessere Lösung.
• @TobySpeight ruft einfach die Klasse in das main() !!
• Sie auf ‚ kann eine Klasse nicht aufrufen – Sie können eine Instanz von einer erstellen oder ihre statischen Methoden aufrufen. Soll startSimulation() die Hauptfunktion sein? In diesem Fall können Sie es stattdessen main() nennen.