Následující kód funguje skvěle, ale zabere příliš mnoho času. placeQueens vyžaduje také hodně času. Program trvá 5-10 sekund.
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; } } Komentáře
Odpovědět
Stejně jako bogosort nikdy nebude algoritmus rychlého třídění. Vaše řešení „zahoďte desku a náhodně umístěte N nových královen“ nikdy nebude rychlejší než těch 5 až 10 sekund.
Přesto mě potěšilo, když jsem zjistil, že skutečně najde řešení poněkud důsledně. A samotná otázka je také složená dobře, takže si myslím, že si zaslouží odpověď.
Stejně jako CiaPan již v komentáři navrhl, mnohem lepší způsob, jak vyřešit problém s n-queens, je zpětné sledování. Můj program rychlého testování s tímto přístupem řeší 8 královen za 1 milisekundu (nebo méně). (A 20 královen za 50 ms).
Je však zajímavé vidět přístup „resetovat a náhodně umístit n nových královen“, takže přidejme jedno zásadní vylepšení pro urychlení hledání řešení.
/** 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); } Tato malá změna zde dostala čas, než řešení trvale kleslo pod 100 ms. Proč? Protože to zmenšuje vyhledávací prostor z O (n³) na O (n²). Důvodem je to, že ve všech řešeních je na každém řádku přesně 1 královna. Takže generuji jednu náhodně pro každý řádek, místo na celé desce.
Komentáře
- Děkuji za skvělou odpověď, ale zdá se, že ‚ s jsem již rychle skončil, ale stále mám problém s nastavenou náhodnou královnou .
- Za zvážení stojí ještě jeden bod: @IbrahimAli neřekl ‚, co je vlastně jeho cílem, nalezení jakéhokoli platného uspořádání nebo všechna platná uspořádání 8 královen. Systematické vyhledávání uzavřené ve smyčce provede druhé (opakovat n všechna možná řešení a každé přesně jednou), zatímco náhodné generování nemůže (může dobře opakovat odpovědi a nikdy nevíme, jestli našlo všechny možnosti; se špatnou kvalitou RNG může být i neschopný nějaké najít).
- @CiaPan I ‚ přemýšlím o
npozice pronboolean jednoduše vytvořím booleovské pole a použiji jej ‚ s indexem v závislosti na náhodném královny, každá vygenerovaná královna nastaví v booleovském poli nelegální index na hodnotu false, což bude po velmi krátkou dobu. - @Imus ‚ nepotřebujete
do – whilesmyčka, protože každáplaceQueens(i)vyvolanáfor (int i = 0; i < 8; i++)smyčkou přiděluje pozici v samostatném řádku, z toho důvodu jsou srážky nemožné a jejich testování je ztrátou času. - Aha true CiaPan. Dobře spatřen. Udělal jsem jen minimální změnu, abych vygeneroval jednu na každém řádku v původním kódu. Proto jsem ‚ právě předal metodu
i. Všiml jsem si také nyní nadbytečné kontroly, ale při hledání řešení získáte pouze méně než milisekundu. ‚ Takže i tak ten rozdíl nerozeznáte.
main()?main()!!startSimulation()hlavní funkcí? Pokud ano, můžete jej místo toho nazvatmain().