Osiem królowych z Javą

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

  • Możliwe, że możesz użyć metody wyszukiwania z cofaniem. Po prostu powtórz umieszczanie hetmanów jedna po drugiej, za każdym razem wybierając pierwszą wolną (niezajętą i nie atakowaną) pozycję. Jeśli nie ma wolnej pozycji dla jakiegoś n -tego hetmana, cofnij się i przesuń hetmana nr. ( n -1) z bieżącego miejsca do następnej wolnej pozycji. Jeśli ' nie ma wolnej pozycji, usuń ( n -1) i cofnij się ponownie. Jeśli cofnąłeś się do pustej planszy, nie ma już możliwości ustawienia hetmana. Jeśli pomyślnie przeniosłeś hetmana ( n -1) w kroku ' wstecz ', kontynuuj umieszczanie n -ty. Losowe umieszczanie jest po prostu zbyt nieefektywne.
  • Gdzie ' jest funkcją main()?
  • @CiaPan dzięki, ale myślę, że jest lepsze rozwiązanie.
  • @TobySpeight po prostu wywołaj klasę w main() !!
  • Ty może ' t wywołać klasę – możesz skonstruować instancję jednej lub wywołać jej metody statyczne. Czy startSimulation() ma być główną funkcją? Jeśli tak, możesz to nazwać main().

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 dla n 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żda placeQueens(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.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *