Nyolc királynő Java-val

A következő kód remekül működik, de túl sok időt vesz igénybe. A placeQueens is sok időt igényel. A program 5-10 másodpercet vesz igénybe.

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

Megjegyzések

  • Esetleg használhat keresési módszert is visszalépéssel. Csak ismételd meg a királynék elhelyezését egyesével, minden alkalommal kiválasztva az első szabad (nem elfoglalt és nem megtámadott) pozíciót. Ha nincs szabad pozíció valamely n -edik királynő számára, lépjen hátra, és mozgassa a királynőt. ( n -1) az aktuális helyről a következő szabad pozícióra. Ha ‘ nincs szabad pozíció, távolítsa el ( n -1), és lépjen vissza. Ha visszalépett az üres deszkához, nincs több lehetséges királynői megállapodás. Ha sikeresen áthelyezett egy királynőt ( n -1) a ‘ vissza ‘ lépésben, folytassa a elhelyezéssel a n -ik. A véletlenszerű elhelyezés túl hatástalan.
  • Hol ‘ hol van a main() függvény?
  • @CiaPan köszönöm, de szerintem van jobb megoldás.
  • @TobySpeight egyszerűen meghívja az osztályt a main() !!
  • Ön ‘ nem hívhat meg osztályt – létrehozhat egy példányt, vagy meghívhatja annak statikus metódusait. Állítólag a startSimulation() a fő funkció? Ha igen, hívhatja helyette main().

Válasz

Csakúgy, mint a bogosort , soha nem lesz gyors rendezési algoritmus. A “dobd el a deszkát, és tedd véletlenszerűen N új királynőt” megoldásod soha nem lesz gyorsabb, mint az 5-10 másodperc.

Mindazonáltal örömmel töltött el, amikor láttam, hogy valóban kissé következetesen talál megoldást. És maga a kérdés is rendben van, ezért úgy gondolom, hogy megérdemli a választ.

Mint a CiaPan, már kommentben javasolta, az n-királynők problémájának sokkal jobb megoldása a visszalépés. Gyors tesztprogramom ezzel a megközelítéssel 1 milliszekundum (vagy kevesebb) alatt oldja meg a 8 királynőt. (És a 20 királynő 50 másodperc alatt).

Azonban a “nullázás és véletlenszerű elhelyezés n új királynőt” megközelítés érdekes látni, ezért adjunk hozzá egy jelentős javítást a gyors megtalálás felgyorsításához. megoldás.

/** 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); } 

Ez a kis változás itt állandóan 100 ms alatti időt adott a megoldásig. Miért? Mivel ez csökkenti az O (n³) keresési teret O-ra (n²). Ennek oka az, hogy minden megoldásnál pontosan 1 királynő van minden sorban. Tehát minden sorhoz véletlenszerűen generálok egyet, és nem az egész táblára.

Megjegyzések

  • Köszönöm a remek választ, de úgy tűnik, hogy ‘ s úgy tűnik, hogy már gyorsan végeztem, de még mindig gondom van a véletlenszerű királynővel .
  • Van még egy szempont, amelyet érdemes megfontolni: @ IbrahimAli nem mondta el ‘ azt, hogy valójában mi a célja, bármilyen érvényes megállapodást találva ill. 8 királynő összes érvényes elrendezése. A ciklusba zárt rendszeres keresés utóbbit fogja végrehajtani (retur n az összes lehetséges megoldás, és mindegyik pontosan egyszer), míg a véletlenszerű generálás nem képes (megismételheti a válaszokat, és soha nem tudjuk, hogy minden lehetőséget megtalált-e; gyenge RNG minőség mellett előfordulhat, hogy képtelen megtalálni).
  • @CiaPan I ‘ m n n logikai pozíció egyszerűen létrehozok egy logikai tömböt, és ‘ indexét véletlenszerűségtől függően használom. királynők, minden generált királynő hamisra állítom az illegális indexet a logikai tömbben, ami sokáig rövid lesz.
  • @Imus Önnek nem kell ‘ nem kell a do – while hurok, mivel minden placeQueens(i), amelyet a for (int i = 0; i < 8; i++) hurok meghív, külön sorban oszt ki egy pozíciót, ezért az ütközések lehetetlenek, és a tesztelés számukra időpazarlás.
  • Aha true CiaPan. Jól foltos. Csak azt a minimális változtatást hajtottam végre, hogy az eredeti kód minden sorában előállítottam egyet. ‘ s ezért adtam át ezt a i -t a metódusnak. Észrevettem az immár felesleges ellenőrzést is, de ez csak egy milliszekundumnál kevesebb időt nyer a megoldás megtalálásában. Tehát ‘ így sem lehet igazán különbséget tenni.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük