Il codice seguente funziona alla grande ma richiede troppo tempo. Anche placeQueens
richiede molto tempo. Il programma impiega 5-10 secondi.
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; } }
Commenti
Rispondi
Proprio come bogosort non sarà mai un algoritmo di ordinamento veloce. La tua soluzione “butta via il tabellone e posiziona casualmente N nuove regine” non sarà mai veramente più veloce di quei 5-10 secondi.
Tuttavia mi ha reso felice di vedere che effettivamente trova una soluzione in modo piuttosto coerente. E anche la domanda in sé è composta bene, quindi penso che meriti una risposta.
Come CiaPan ha già suggerito in un commento, un modo molto migliore per risolvere il problema delle n-regine è con il backtracking. Il mio programma di test rapido con questo approccio risolve le 8 regine in 1 millisecondo (o meno). (E le 20 regine in 50 ms).
Tuttavia, lapproccio “reimposta e posiziona casualmente n nuove regine” è interessante da vedere, quindi aggiungiamo un miglioramento importante per velocizzare la ricerca di una soluzione.
/** 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); }
Questo piccolo cambiamento qui ha portato il tempo fino alla soluzione fino a meno di 100 ms in modo coerente. Perché? Perché questo riduce lo spazio di ricerca da O (n³) a O (n²). Il motivo per cui funziona è che in tutte le soluzioni cè esattamente 1 regina su ogni riga. Quindi ne genero una casualmente per ogni riga, invece che sullintero tabellone.
Commenti
- Grazie per lottima risposta, ma ‘ sembra che ne abbia già terminata una veloce ma ho ancora problemi con la regina casuale impostata .
- Cè un altro punto da considerare: @IbrahimAli non ‘ ha detto qual è effettivamente il suo scopo, trovare qualsiasi disposizione valida o tutti gli arrangiamenti validi di 8 regine. La ricerca sistematica racchiusa in un ciclo farà lultima (retur n tutte le possibili soluzioni, e ciascuna esattamente una volta), mentre la generazione casuale non può (potrebbe anche ripetere le risposte e non sappiamo mai se ha trovato tutte le possibilità; con una scarsa qualità RNG potrebbe anche essere impossibile trovarne alcuni).
- @CiaPan I ‘ sto pensando a
n
posizione pern
booleano semplicemente creo un array booleano e lo utilizzo ‘ s index by depend on random regine, per ogni regina generata ho impostato lindice illegale su false nellarray booleano, il che richiederà molto tempo. - @Imus Non ‘ non hai bisogno del
do – while
ciclo, poiché ogniplaceQueens(i)
richiamato dal ciclofor (int i = 0; i < 8; i++)
alloca una posizione in una riga separata, quindi le collisioni sono impossibili e testarle è una perdita di tempo. - Aha true CiaPan. Ben individuato. Ho apportato solo la minima modifica per generarne uno su ogni riga nel codice originale. Ecco ‘ il motivo per cui ho appena passato quel
i
al metodo. Ho anche notato il controllo ora ridondante, ma che ti fa guadagnare solo meno di un millisecondo nel trovare la soluzione. Quindi non puoi ‘ davvero dire la differenza comunque.
main()
?main()
!!startSimulation()
dovrebbe essere la funzione principale? In tal caso, potresti chiamarlomain()
.