Otto regine con Java

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

  • Forse puoi usare un metodo di ricerca con backtracking. Basta ripetere il piazzamento delle regine una per una, scegliendo ogni volta una prima posizione libera (non occupata e non attaccata). Se non cè una posizione libera per qualche n esima regina, fai un passo indietro e sposta la regina n. ( n -1) dalla posizione corrente alla successiva posizione libera. Se ‘ non è disponibile alcuna posizione, rimuovi ( n -1) e torna indietro. Se torni indietro alla scacchiera vuota, non ci sono più possibili accordi con la regina. Se hai spostato correttamente una regina ( n -1) nel passaggio ‘ indietro ‘, procedi con il posizionamento il n -esimo. Il posizionamento casuale è semplicemente troppo inefficace.
  • Dove ‘ è la funzione main()?
  • @CiaPan grazie, ma penso che ci sia una soluzione migliore.
  • @TobySpeight semplicemente invoca la classe nel main() !!
  • Tu ‘ t invocare una classe: puoi costruirne unistanza o invocarne i metodi statici. startSimulation() dovrebbe essere la funzione principale? In tal caso, potresti chiamarlo main().

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 per n 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é ogni placeQueens(i) richiamato dal ciclo for (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.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *