W dzisiejszym wywiadzie zadano mi następujące pytanie i odtąd o tym myślę. Nie byłem w stanie odpowiedzieć na to pytanie i nie byłem w stanie znaleźć rozwiązania online.
Biorąc pod uwagę szachownicę o wymiarach X według królowych Y i N, ustal, czy możliwe jest ułożenie tych królowych na planszy tak, aby nie mogły się nawzajem atakować.
Płyta 2 x 3 z 2 królowymi ma rozwiązanie, więc algorytm zwróciłby prawdę:
Q . .
. . Q
Szukam podejścia programowego do tej układanki, a nie tylko na przykład rozwiązania na papierze.
algorithms
puzzles
chess
Rozmówca
źródło
źródło
Odpowiedzi:
To nie jest (IMO) bardzo interesujący problem z punktu widzenia programowania. Możesz wymyślić algorytm rekurencyjny, który wypróbuje każde ustawienie, coś takiego:
Jeśli zastanowisz się trochę nad tym problemem, zdasz sobie sprawę, że nie ma sposobu, aby dopasować N królowych na planszy, gdzie X <N lub Y <N, ponieważ wymagałoby to, aby co najmniej dwie królowe znalazły się w tym samym rankingu lub pliku, i dlatego atakują się nawzajem. Jeśli przeczytasz o problemie n-królowych, szybko dowiesz się, że zawsze można umieścić N królowych na tablicy NxN dla N> 3. Teraz wiemy, że odpowiedź brzmi NIE dla (X <N lub Y <N) i TAK dla (X> = N i Y> = N, N> 3). Pozostały tylko specjalne przypadki:
Więc teraz nasza ładna funkcja rekurencyjna staje się prostą funkcją, która po prostu porównuje N z X i Y i zwraca wynik standardowy. To świetne z punktu widzenia wydajności, ponieważ możesz uzyskać odpowiedź w stałym czasie. Z punktu widzenia programowania nie jest to takie wspaniałe, ponieważ zdajesz sobie sprawę, że w tym momencie chodzi o to, jak dobrze rozwiązywać zagadki, niż o umiejętność pisania funkcji rekurencyjnej.
(A chłopcze, och chłopcze, naprawdę mam nadzieję, że nie popełniłem głupiego błędu w odpowiedzi na smarty-spodnie. ;-)
źródło
That's great from a performance point of view, since you can get an answer in constant time. It's not so great from a programming point of view because you realize, at this point, that the question is really more about how well you can solve puzzles than it is about your ability to write a recursive function.
Myślę, że ankieter czekał na to rozwiązanie O (1), ponieważ jest ono ostatecznie lepsze i nie jest oczywiste dla wielu osób. Problem królowej nxn występuje we wszystkich kursach programistycznych jako ćwiczenie rekurencyjne - wiele osób nie pomyśli głębiej, widząc ten problem ponownie.Jeśli ankieter poprosił cię o napisanie kodu problemu, myślę, że to niesprawiedliwe. Algorytm wymaga pracy. Jeśli jednak chodziło o pokazanie ankieterowi klas, metod lub niektórych pojęć, których należy użyć lub czegoś podobnego, może to być uczciwe pytanie.
Problem jest klasycznym problemem informatycznym i jest omawiany w wielu takich książkach. Doskonałe wyjaśnienie, z animacją i 12 różnymi rozwiązaniami wraz z pewnym kodem można znaleźć tutaj:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
Również kod można znaleźć tutaj: http://www.codeproject.com/KB/java/EightQueen.aspx
Nie przejmuj się tym, jak powiedziałem, nie jest to łatwe.
źródło
To naprawdę jest komentarz, ale nie pasuje ...
Szachownica ma kwadraty 8x8, nie mniej więcej (te pytania zawsze mnie denerwują podejściem do niestandardowej szachownicy).
Ale tak czy inaczej, jeśli masz szachownicę x * y, n królowe i biorąc pod uwagę, że królowa „bierze” te pola
czy możesz po prostu stworzyć dwuwymiarową tablicę i „oznaczyć” wszystkie pola atakowane przez jedną królową. Następnie umieść drugie (ze środka planszy), oflaguj pozostałe pola i tak dalej ... aż uruchomisz jedno z pól lub królowych.
Jest to oczywiście bardzo uproszczone podejście, ponieważ przy złym ustawieniu, uznaję, że maksymalna liczba królowych byłaby różna.
Hmm, właśnie to znalazłem - problem 8 królowych.
źródło
Zasadniczo algorytm cofania działa w następujący sposób:
Utwórz tablicę X według Y. Ustaw wszystkie kwadraty na puste.
Ustaw liczbę królowej na zero.
Ustaw swoją bieżącą pozycję na (1,1)
Sprawdź, czy umieścisz królową na aktualnej pozycji.
Jeśli możesz, ustaw Array (X, Y) na queen, zwiększ liczbę królów. Jeśli umieściłeś całą królową, przestań , masz rozwiązanie.
Jeśli bieżąca pozycja nie jest (X, Y), zwiększ aktualną pozycję i przejdź do kroku 4.
Znajdź królową na ostatniej pozycji (tej, która jest ostatnia w kolejności, w której zwiększasz pozycje). Ustaw bieżącą pozycję na pozycję tej królowej, usuń ją i zmniejsz liczbę królów.
Jeśli liczba królowych wynosi zero, przestań , nie ma rozwiązania.
Zwiększ bieżącą pozycję.
Przejdź do kroku 4.
źródło
Dodanie do innych odpowiedzi: utworzenie dwuwymiarowej tablicy tylko komplikuje kod.
Potrzebujesz zwykłego wektora o rozmiarze 8 do zwykłej szachownicy. Lub 8 + 1, jeśli podobnie jak C 1. pozycja wynosi 0, tylko w celu uproszczenia kodu i radzenia sobie z 1-8, a nie 0-7.
Jeśli myślisz, że x jest twoją pozycją w tablicy, ay jest treścią pozycji. np. tablica [1] = 8 oznacza, że pierwsza królowa jest w [1,8].
W ten sposób wystarczy sprawdzić poprawność kolumn.
Na wydziale natknąłem się na bardzo starą książkę (lata 60.?), Dotyczącą algorytmów zaimplementowanych w Dartmouth BASIC, która implementowała problem 8 królowych przy użyciu mniejszej możliwej pamięci (jest tak stara, że ma sens).
O ile pamiętam, wykorzystał pomysł wektorowy i zasadniczo brutalnie zmusił wszystkie pozycje na planszy za pomocą dwóch cykli FOR. Aby sprawdzić ważność pozycji, wykorzystano trzecią pętlę, cykl WHILE w każdej pozycji wraca do wektora i sprawdza, czy jest równa liczba, lub formułę używającą operacji stycznej do sprawdzenia przekątnych.
Niestety zgubiłem tę książkę ...
Wspomniany algorytm znalazł wszystkie rozwiązania problemu n-królowej.
źródło
Jeśli po prostu musisz napisać algorytm, aby ustalić, czy taki układ istnieje, spójrz na istniejące badania:
Układanka Osiem królowych na Wikipedii .
Możesz trywialnie zwrócić false, jeśli N> min (X, Y).
Po przeczytaniu tej strony wiadomo, że należy zwrócić wartość true, jeśli N <= min (X, Y) i 2, 3! = Min (X, Y).
Który pozostawia 2, 3 == min (X, Y) i N <= min (X, Y).
Cóż, jeśli N <min (X, Y), znalezienie rozwiązania jest banalne.
Jeśli N == min (X, Y), istnieje rozwiązanie tylko wtedy, gdy max (X, Y)> N.
źródło
Oczywiście nie ma rozwiązania, jeśli N> min (X, Y). W przeciwnym razie możesz łatwo pokazać, że nie ma rozwiązania dla N = X = Y = 2, N = X = Y = 3. Dla wszystkich innych przypadków wydaje się, że istnieje rozwiązanie. Liczba rozwiązań wydaje się rosnąć wraz ze wzrostem N.
Możesz znaleźć rozwiązanie poprzez wyczerpujące wyszukiwanie z cofaniem się: Umieść królową w pierwszym rzędzie, kolumnie 1. Umieść królową w drugim rzędzie, w pierwszej kolumnie, do której królowa w rzędzie 1 nie może dotrzeć. Umieść królową w drugim rzędzie itp. Jeśli królowej nie można umieścić w rzędzie k, usuń ją i przenieś królową w rzędzie k-1 na następną niezajętą pozycję.
źródło