Åtta drottningar med Java

Följande kod fungerar bra men tar för mycket tid. placeQueens kräver också mycket tid. Programmet tar 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

• Eventuellt kan du använda en sökmetod med backtracking. Bara itera och placera drottningar en efter en, varje gång du väljer en första ledig (inte ockuperad och inte attackerad) position. Om det inte finns någon ledig position för någon n -te drottning, gå tillbaka och flytta drottningen nr. ( n -1) från nuvarande plats till nästa lediga position. Om det inte finns ’ tar du bort ( n -1) och går tillbaka igen. Om du gick tillbaka till tomt ombord finns det inga fler drottningsarrangemang. Om du framgångsrikt flyttat en drottning ( n -1) i steget ’ ’, fortsätt med att placera den n -te. Slumpmässig placering är alldeles för bristfällig.
• Var ’ är main() -funktionen?
• @CiaPan tack, men jag tror att det finns en bättre lösning.
• @TobySpeight åberopar helt enkelt klassen till main() !!
• Du kan ’ inte åberopa en klass – du kan konstruera en instans av en eller åberopa dess statiska metoder. Ska startSimulation() vara huvudfunktionen? Om så är fallet kan du kalla det main() istället.