Poniższy kod działa świetnie, ale zajmuje zbyt dużo czasu. placeQueens
też wymaga dużo czasu. Program trwa 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; } }
Komentarze
Odpowiedź
Podobnie jak bogosort nigdy nie będzie szybkim algorytmem sortowania. Twoje rozwiązanie „wyrzuć planszę i losowo umieść N nowych hetmanów” nigdy tak naprawdę nie będzie szybsze niż te 5 do 10 sekund.
Niemniej jednak ucieszyłem się, widząc, że faktycznie znajduje rozwiązanie dość konsekwentnie. Samo pytanie jest również dobrze skomponowane, więc myślę, że zasługuje na odpowiedź.
Podobnie jak CiaPan zasugerował już w komentarzu, znacznie lepszym sposobem rozwiązania problemu n-damy jest wycofywanie się. Mój program szybkiego testu z takim podejściem rozwiązuje problem 8 królowych w 1 milisekundę (lub mniej). (I 20 hetmanów w 50 ms).
Jednak podejście „zresetuj i losowo umieść n nowych hetmanów” jest interesujące, więc dodajmy jedną zasadniczą poprawę, aby przyspieszyć znajdowanie rozwiązanie.
/** 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); }
Ta niewielka zmiana spowodowała konsekwentne skrócenie czasu do rozwiązania poniżej 100 ms. Dlaczego? Ponieważ zmniejsza to przestrzeń wyszukiwania z O (n³) do O (n²). Powód, dla którego to działa, jest taki, że we wszystkich rozwiązaniach jest dokładnie 1 hetman w każdym rzędzie. Więc generuję jeden losowo dla każdego wiersza, a nie dla całej planszy.
Komentarze
- Dziękuję za świetną odpowiedź, ale wygląda na to, że ' już skończyłem szybko, ale nadal mam problem z ustawieniem losowej hetmana .
- Jest jeszcze jedna kwestia warta rozważenia: @IbrahimAli nie ' nie powiedział, jaki jest jego cel, znajdując jakiekolwiek ważne ustalenia lub wszystkie ważne aranżacje 8 królowych. Systematyczne wyszukiwanie w pętli zrobi to drugie (zwrot n wszystkich możliwych rozwiązań i każde dokładnie raz), podczas gdy generowanie losowe nie może (równie dobrze może powtórzyć odpowiedzi i nigdy nie wiemy, czy znalazło wszystkie możliwości; ze słabą jakością RNG może nawet nie ich znaleźć).
- @CiaPan I ' myślę o
n
pozycja dlan
boolean po prostu tworzę tablicę logiczną i używam jej ' indeksu według zależnie od losowości królowe, każdej wygenerowanej królowej ustawiam niedozwolony indeks na fałsz w tablicy boolowskiej, co zajmie dużo czasu. - @Imus Nie ' nie potrzebujesz
do – while
pętla, ponieważ każdaplaceQueens(i)
wywoływana przez pętlęfor (int i = 0; i < 8; i++)
przydziela pozycję w osobnym wierszu, stąd kolizje są niemożliwe, a ich testowanie to strata czasu. - Aha, prawdziwy CiaPan. Dobrze zauważony. Dokonałem tylko minimalnej zmiany, aby wygenerować jedną w każdym wierszu w oryginalnym kodzie. To ' jest powodem, dla którego właśnie przekazałem
i
do metody. Zauważyłem również zbędny teraz czek, ale zyskujesz tylko mniej niż milisekundę na znalezieniu rozwiązania. Więc możesz ' i tak naprawdę nie dostrzec różnicy.
main()
?main()
!!startSimulation()
ma być główną funkcją? Jeśli tak, możesz to nazwaćmain()
.